Ramazan Gokberk Cinbis

Jakob Verbeek

Cordelia Schmid

Segmentation Driven Object Detection with Fisher Vectors

We present an object detection system based on the Fisher vector (FV) image representation computed over SIFT and color descriptors. For computational and storage efficiency, we use a recent segmentation-based method to generate class-independent object detection hypotheses, in combination with data compression techniques. Our main contribution is a method to produce tentative object segmentation masks to suppress background clutter in the features. Re-weighting the local image features based on these masks is shown to improve object detection significantly. We also exploit contextual features in the form of a full-image FV descriptor, and an inter-category rescoring mechanism. Our experiments on the PASCAL VOC 2007 and 2010 datasets show that our detector improves over the current state-of-the-art detection results.

Introduction

Object detection is an important computer vision problem, where the goal is to report both the location in terms of a bounding box, and the category of objects in an image. Significant progress has been made over the past decade, as witnessed by the PASCAL VOC challenges [START_REF] Everingham | The Pascal Visual Object Classes (VOC) challenge[END_REF]. Most of the existing work, see e.g. [START_REF] Dalal | Histograms of oriented gradients for human detection[END_REF][START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], is based on the sliding window approach, where detection windows of various scales and aspect ratios are evaluated at many positions across the image. This approach becomes computationally very expensive when rich representations are used. To alleviate this problem, the seminal approach of Viola and Jones [START_REF] Viola | Robust real-time object detection[END_REF] implements a cascade, which iteratively reduces the number of windows to be examined. In a similar spirit, two or three-stage approaches have been explored [START_REF] Harzallah | Combining efficient object localization and image classification[END_REF][START_REF] Vedaldi | Multiple kernels for object detection[END_REF], where windows are discarded at each stage, while progressively using richer features. It is also possible to implement non-exhaustive search with a branch and bound scheme [START_REF] Lampert | Efficient subwindow search: a branch and bound framework for object localization[END_REF]. A recent alternative is to prune the set of can-didate windows without using class specific information, by relying on low-level contours and image segmentation, see e.g. [START_REF] Alexe | Measuring the objectness of image windows[END_REF][START_REF] Endres | Category independent object proposals[END_REF][START_REF] Gu | Multicomponent models for object detection[END_REF][START_REF] Van De Sande | Segmentation as selective search for object recognition[END_REF]. In our work we use the method of [START_REF] Van De Sande | Segmentation as selective search for object recognition[END_REF].

Our first contribution is to explore the improved Fisher vector representation of [START_REF] Sánchez | Image classification with the Fisher vector: Theory and practice[END_REF] for object detection. This representation was recently shown to yield state-of-the-results for image and video categorization [START_REF] Chatfield | The devil is in the details: an evaluation of recent feature encoding methods[END_REF][START_REF] Oneata | Action and event recognition with Fisher vectors on a compact feature set[END_REF]. Chen et al . [START_REF] Chen | Efcient maximum appearance search for large-scale object detection[END_REF] recently also explored Fisher vectors (FV) for detection, and proposed an efficient detection mechanism based on integral images to find the best scoring window per image. Their approach, however, does not allow the use of power and 2 normalization of the FVs. We show that this is a significant drawback, since these normalizations lead to substantially better detection performance when included.

Our second contribution is that we show that the image segmentation that drives the object hypotheses generation, can also be used to improve the appearance features computed over the windows. To this end, we compute a mask for each candidate window which counts for each pixel how many superpixels that cover that pixel are fully contained in the window, and weight the contribution of local descriptors in the Fisher vector representation accordingly. This local feature weighting process is class-independent, completely unsupervised, and suppresses background clutter on superpixels that traverse the window boundary.

Related work in the literature has used segmentation for object detection in different ways. Part of it, see e.g. [START_REF] Dai | Learning to localize detected objects[END_REF][START_REF] Parkhi | The truth about cats and dogs[END_REF][START_REF] Ramanan | Using segmentation to verify object hypotheses[END_REF][START_REF] Wang | Object detection combining recognition and segmentation[END_REF], extracts explicit segmentation for each object detection hypothesis as a post-processing step. Placing a bounding box over the obtained segmentation, however, can be sensitive to small defects in the segmentation. Moreover, if the supervision is limited to bounding box annotations, it is difficult to learn accurate object segmentation models. Other approaches, such as [START_REF] Gu | Recognition using regions[END_REF], instead rely on a bottom-up process which scores superpixels individually, and then assembles them into object detections. This approach has the drawback that the recognition of object fragments is much harder than recognizing complete objects. Recently, Fidler et al . [START_REF] Fidler | Bottom-up segmentation for top-down detection[END_REF] improve object detection using the output from the semantic segmentation of [START_REF] Carreira | Semantic segmentation with second-order pooling[END_REF]. The semantic segmentation is used to extract additional features encoding spatial relationships between the associated segments and object detection windows. This approach, however, requires groundtruth segmentations to train the semantic segmentation model.

Our work is different in the sense that we incorporate segmentation into the feature extraction step for object detection, and remain in the training-from-bounding-boxes paradigm. Even if the segmentation step fails in accurately delineating the object, our detector still benefits from the approximate segmentation since still part of the background clutter can be suppressed. Note that segmentation based post-processing may still be applied on top of our approach.

Our work is also related to recent work on weighting local features in representations for image classification. Khan et al . [START_REF] Khan | Top-down color attention for object recognition[END_REF] use class-specific attention maps to weight local descriptors, and concatenate the class-specific bag-ofword histograms in their final representation. Sánchez et al . [START_REF] Sánchez | Modeling the spatial layout of images beyond spatial pyramids[END_REF] sample 1,000 windows per image using the objectness measure of [START_REF] Alexe | Measuring the objectness of image windows[END_REF], and weight local features proportional to the number of windows that overlap them when computing a Fisher vector representation. We evaluate our system using the PASCAL VOC 2007 and 2010 datasets, and compare it to results reported in the literature. To the best of our knowledge, our results are the best so far reported on these datasets, when considering the average performance across classes. With a gain of around 2 mAP points, our approximate segmentation masks significantly contribute to the success of our method.

In the next section we describe our method in detail, followed by the results of our experimental evaluation in Section 3. Finally, we present our conclusions in Section 4.

Segmentation driven object detection

In this section we describe how we generate our approximate segmentation masks, the feature extraction and compression processes, and the detector training procedure.

Segmentation mask generation

Hierarchical segmentation was proposed in [START_REF] Van De Sande | Segmentation as selective search for object recognition[END_REF] to generate class-independent candidate detection windows. The image is first partitioned into superpixels, which are then hierarchically grouped into a segmentation tree by merging neighboring and visually similar segments. This step is repeated using eight different sets of superpixels; obtained using four different color spaces and two different scale parameters for the superpixel generation. In this manner, a rich set of segments of varying sizes and shapes is obtained, and the bounding boxes of the segments are used as candidate detection windows. When producing around 1,500 object windows per image, more than 95% of the ground truth object windows are matched in the sense that they have an intersection/union measure of over 50%, as measured on the VOC'07 dataset. In this manner more computationally expensive classifiers and features can be used since far less windows need to be evaluated than in a sliding window approach. Examples of candidate windows together with their generating segments can be found in Figure 1.

In general, however, the segments used to generate these candidate windows do not provide good object segmentations. To obtain masks that are more suitable to improve object localization, we exploit the idea that background clutter is likely to be represented by superpixels that traverse the window boundary. Therefore, we produce a binary mask based on each of the eight segmentations by retaining the superpixels that lie completely inside the window, and suppressing the other ones. We average the eight binary masks to produce the weighted mask, which we use to weight the contribution of local features in the window descriptor. The procedure is illustrated in Figure 1. The segmentation quality varies across the eight segmentations from one image to another, but the average mask produces a relatively high quality segmentation for the correct object hypotheses shown in the first two rows, in particular considering that the method is completely unsupervised and class-independent.

It is important to consider the segmentation masks produced for incorrect candidate windows too, since these represent the vast majority of the candidate windows. For example, in the VOC 2007 dataset there are on average 2.5 objects per image, while we use on the order of 1,000 to 2,000 candidate windows per image. The first incorrect candidate window in Figure 1 shows a case where a partially visible horse is largely suppressed, since the superpixels on the object straddle outside the window. As a result this window gets a lower score than the correct one containing the entire horse. The second incorrect window shows a case where the car features are retained, and background is suppressed. Since the window does not accurately cover the object, this might be detrimental to the detector performance. It is, therefore, important to also take into account the features of the entire window as shown experimentally in Section 3.

Feature extraction

To represent the candidate object windows we use two local features: SIFT and the local color descriptor of [START_REF] Clinchant | XRCE's participation to ImagEval[END_REF]. Both descriptors are extracted on a dense multi-scale grid, with step size equal to 25% of the patch width, and on 16 scales separated by a factor 1.2, with 12 × 12 patches at the smallest scale. We project both features to D = 64 dimensions using PCA.

We aggregate the local feature vectors using the Fisher vector (FV) representation [START_REF] Sánchez | Image classification with the Fisher vector: Theory and practice[END_REF]. This representation extends the well-known bag-of-words representation by extracting first-order and second-order moments from the descriptors assigned to a visual word in addition to the number Figure 1: Segmentation masks for two correct (top) and two incorrect (bottom) candidate windows. The first four columns show the window, the merged segment that produced that window, our weighted mask, and the masked window. The eight images on the right show the binary masks of superpixels lying fully inside the window, for each of the eight segmentations. of assigned descriptors. Formally, the FV is defined as the gradient of the log-likelihood of the data under a generative model, normalized by the inverse square-root of the Fisher information matrix. We learn a mixture of Gaussian (MoG) distribution p(x) with diagonal covariance matrices from a large collection of 10 6 local descriptors off-line. The normalized gradients with respect to µ kd , and σ kd -the mean and standard deviation of the k-th Gaussian in dimension dfor a single local descriptor x are given by:

∂ ln p(x) ∂µ kd = p(k|x) √ π k x d -µ kd σ kd , (1)
∂ ln p(x) ∂σ kd = p(k|x) √ π k (x d -µ kd ) 2 σ 2 kd -1 , (2)
where π k is the mixing weight of the k-th Gaussian, and p(k|x) is the soft-assignment of x to the k-th Gaussian. In practice we use a hard-assignment instead of the posterior to speed-up feature calculation for many candidate windows.

To represent a candidate window we sum up these normalized gradients, and weight the contribution of local descriptors by the averaged segmentation masks when we use them. After aggregating the local gradient vectors, we obtain a K(2D + 1) dimensional feature vector to which we apply the power and 2 normalization [START_REF] Sánchez | Image classification with the Fisher vector: Theory and practice[END_REF]. The power normalization consists in taking a "signed square-root", z ← sign(z) abs(z), on each dimension separately. In [START_REF] Cinbis | Image categorization using Fisher kernels of non-iid image models[END_REF], power normalization was shown to provide an approximation to the fisher vectors w.r.t. an improved MoG-like model incorporating dependencies across image patches.

To obtain the final window descriptor we concatenate the FVs obtained over the color and SIFT features. We also employ a form of rigid spatial layout [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF], and compute FVs over cells in a 4 × 4 grid over the window; we also do this in combination with our masks. To capture global scene context, we compute a FV over the full image. In our experiments we assess their relative importance of these features.

Feature compression

During training we apply our detectors several times to the training images to retrieve hard negative examples. Reextracting descriptors at each hard negative mining iteration would be very costly. For example, the PASCAL VOC 2007 dataset contains about 5,000 training images and we have between 1,000 and 2,000 candidate windows per image, thus we have to assess in the order of 5 to 10 million candidate windows in each iteration. On the other hand, storing all window descriptors in memory is also problematic. In our experiments we use K = 64 Gaussians, which leads to K(2D + 1) = 8, 256 dimensional FVs, which for 5 million candidate windows represents about 160 GB when using 4byte floating point encoding. When using more elaborate descriptors, e.g. when including color, spatial pyramids, or masks, the memory usage becomes quickly prohibitive.

To overcome this problem, we compress the feature vectors using product quantization (PQ), which was recently proposed for large-scale image retrieval and classification [START_REF] Jégou | Product quantization for nearest neighbor search[END_REF][START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF]. In product quantization, the large H dimensional feature vector is split into B subvectors, and a separate kmeans quantizer with 2 M centers is learned for each subvector. A high dimensional vector can then be compressed to B × M bits, by encoding for each subvector the index of the nearest k-means center. In practice we use M = 8, and H/B = 8 dimensional subvectors, which leads to a compression factor of 32 as compared to a 4-byte floating point encoding of the original vector. To reduce the memory requirements even further, we use Blosc compression [2] on the PQ codes per image. Blosc is a highly-optimized lossless data compression algorithm with low computational overhead, which exploits regularities across the descriptor PQ codes. 1 Note that PQ compression was used for object detection before in [START_REF] Vedaldi | Sparse kernel approximations for efficient classification and detection[END_REF], but for a HOG feature based system which is far less demanding in terms of storage. We compare to their results in our experimental evaluation.

One can choose not to compress the data during test time, and apply the detector in an online manner computing the features for one image at the time. In our experimental setup, however, we have used the same compression approach on the test images; in [START_REF] Sánchez | High-dimensional signature compression for large-scale image classification[END_REF] it was shown that this only has a small impact on performance. Using PQ codes, all window descriptors for the whole dataset take 580 GB of disk space. Blosc compression further reduces the data size roughly by a factor 4, down to 137 GB.

In order to apply a detector (for hard negative mining or evaluation), we only need to decompress Blosc-compressed data on-the-fly back to PQ codes. The PQ codes can be used directly to score windows efficiently using lookup tables [START_REF] Vedaldi | Sparse kernel approximations for efficient classification and detection[END_REF]. Once data is loaded into memory, applying a detector on 5,000 images takes around 5 minutes using 35 cores for a single category and around 20 minutes for all 20 categories. Since most time is spent reading data from memory and decompressing the Blosc codes, the detection time scales sub-linearly with the number of categories.

Training the detector

For each category we train a linear SVM classifier on the concatenated FV representation of the windows. As positive training examples, we use the windows given by the ground-truth annotation. We initialize the set of negative training examples by randomly sampling candidate boxes around ground-truth windows, and retaining those windows that have an overlap between 20% and 30% with a positive example in terms of intersection over union.

After the initial training stage, we add hard negative examples by applying the detector on the training set. At each hard negative mining iteration, we select the top two detections per image, with less than 30% overlap with any ground-truth window. To avoid redundancy in negative samples, we do not allow two negative windows to have more than 60% overlap.

Using our development dataset, described in the next section, we observed that the detector performance significantly increases after the first hard negative mining itera- 1 We use the public code from http://blosc.pytables.org. tion, and usually stabilizes after a few iterations. Based on this observation we fixed the number of hard negative mining iterations to four in all our experiments.

To learn the classifiers from the PQ compressed data, we use the dual coordinate descent algorithm of LibLinear [START_REF] Fan | LIBLINEAR: a library for large linear classification[END_REF] which updates the classifier after accessing a single example at a time. We modified the code to decompress examples on-the-fly as they are accessed by the training algorithm.

Experimental evaluation

We conduct experiments on the PASCAL VOC datasets of 2007 and 2010 [START_REF] Everingham | The Pascal Visual Object Classes (VOC) challenge[END_REF]. To develop our approach and to evaluate the different variants of the approach, we use a subset of 1,000 images of the classes bus, cat, motorbike, and sheep from the "train+val" part of the 2007 dataset. These 1,000 images are again split into equal train and test sets; experiments on this development set do not use any images of the "test" set of the 2007 dataset.

For SVM training, there are two important hyperparameters to set. The first one determines the balance between positive and negative examples, and the second one is the weight of the regularization term. On the development dataset, we have observed that using a fixed set of parameters performed as well as cross-validating these parameters per class. Therefore, in all experiments below, we have set the total weight of negative examples to be 100 times larger than the total weight of all positive examples, and set the weight of the SVM's 2 regularization term to 10 -2 .

Parameter evaluation on the development set

We evaluated different versions of our detector on the development set, the results of which can be found in Table 1.

In our first three experiments we consider different detectors that only rely on the candidate windows, and do not make use of segmentation masks. We start with a basic detector that computes a single (power and 2 normalized) Fisher vector (FV) over the SIFT descriptors in each window , which leads to an mAP of 25.2%. When adding a 4 × 4 SPM grid, and concatenating the 1 + 4 × 4 = 17 FVs, the detection mAP value improves to 44.2%, underlining the importance to take spatial information into account. Next, we consider applying the 2 normalization per spatial cell instead of on the concatenated vector. We observe a small improvement to 45.0% mAP.

In order to evaluate the importance of descriptor normalization, we removed the power normalization and test three versions: (i) no normalization (i.e., just summing the perdescriptor Fisher vectors), (ii) normalize (i.e. divide) by the number of local descriptors, (iii) using 2 normalization. This results in 3.4%, 6.9%, and 42.7% mAP, respectively (not shown in Table 1). Compared to the version with power and 2 normalizations, 45.0% mAP, it is clear than both normalization techniques are important for the detection task. The next four experiments in Table 1 assess the performance when using segmentation masks. First, we use for each window the generating segment used to produce it, i.e. the segments shown in the second column of Figure 1. In this case we suppress all descriptors within the bounding box that do not lie inside the segment, except for the groundtruth object windows during training, for which there are no generating segments. This leads to a detection mAP of 35.5%. Although this result is 10 mAP points below that using the window itself, it is still surprisingly good considering that the generating segments often poorly capture the object shape. Second, we repeat this experiment when using the weighted masks (see Figure 1 third column), which improves mAP by about five points to 40.2%. Third, we also use the weighted masks on the ground-truth object windows during training. This improves the detector to 43.8% mAP, due to a better match between training and test data. This is, however, slightly lower than the results obtained from the windows. This might be due to the fact that useful contextual background descriptors tend to be suppressed. Our last experiment in this set considers combining the mask and window descriptors, so as to benefit from both local context, and crisper object-centered features. This combination outperforms the window-only detector on all four classes and leads to 46.4% mAP.

In the last three experiments, we examine the added value of additional color and full-image features. For both of these we do not apply SPM grids. First, we consider adding color to both the window-only detector and the win-dow+mask detector. The window-only SIFT+color detector performs very similar to the window+mask SIFT-only detector at 46.4% mAP. When adding color to the win-dow+mask detector performance rises to 48.7%, clearly showing the complementarity of the mask and color features. Finally, we add a contextual feature by means of a FV computed over the full image, which further increases the mAP score to 49.6%.

Evaluation and comparison to existing work

We now turn to evaluations on the full PASCAL VOC 2007 and 2010 datasets. Based on the above experiments we use SPM, power and cell-level 2 normalization.

In Table 2 we present results obtained for various versions of our detector on the 2007 dataset. First, we consider the window-only version, which obtains 34.0% mAP. Second, we consider the combined window+mask version, which obtains an mAP of 35.8%. In the following two rows, we repeat the first two experiments with additional color features, which score 35.2% and 37.6% mAP, respectively. These relative performances are consistent with observations made on the development set. When we add the full-image FV to window+mask descriptors, mAP score is increased from 37.6% to 38.5%. To confirm the gain due to use of masks, we also report results for (SIFT+color, win-dow+full), which is 36.6% mAP. Thus, the gain by adding masked features is consistently around 2 mAP points. Finally, we implement the contextual rescoring mechanism proposed in [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF], which further increases the score from 38.5% to 40.5% mAP (last row).

To gain insight in the effect of the masked features, we present top detections in example images with our best detector (SIFT+color, window+full+context) with and without masks in Figure 2. Images in the top row illustrate cases where the detector benefits from the masked features. Our approximate object segmentation suppresses background clutter, which is particularly important when the object does not fill the bounding box (columns 1-4). The bus example shows a case where a too small detection is suppressed since superpixels extend over the full bus, using the mask leads to the full bus being detected. The bottom row shows examples where the use of masks degrades the top detection, typically the detection window is too large, since included background features are suppressed by the masks.

In Table 3 we compare our results to those of eight representative state-of-the-art detectors. We divide them in two groups depending on whether they exploit inter-class contextual features, which we refer shortly as contextual detectors, or score windows independently. We can observe that our detector without contextual rescoring obtains 38.5% mAP, which is significantly better than the highest mAP (34.8%) among the competing non-contextual detectors, and very similar to the highest mAP (38.7%) among the competing contextual detectors. With contextual rescoring, our detector obtains 40.5% mAP, which is the highest reported result on this dataset to the best of our knowledge.

Since we use the candidate window method of Van de Sande et al . [START_REF] Van De Sande | Segmentation as selective search for object recognition[END_REF], the detectors can be directly compared. In their work they used intersection-kernel SVM classifiers on bag-of-word representations with a 4-level spatial pyramid, computed over SIFT, and two color features (opponent-SIFT, and RGB-SIFT). Our detector without contextual rescoring outperforms theirs on 17 of the 20 categories, as well as on average, 38.5% vs. 33.7% mAP. Among the methods without context best results are obtained with [START_REF] Khan | Color attributes for object detection[END_REF], which introduces high-level color-name features in the deformable part-based model (DPM) of [START_REF] Felzenszwalb | Object detection with discriminatively trained part based models[END_REF]. Our detector mAP compares favorably to theirs on average, 38.5% vs. 34.8% mAP, as well as on 13 of the 20 classes.

Chen et al . [START_REF] Chen | Detection evolution with multi-order contextual co-occurrence[END_REF] propose a technique for exploiting contextual information from a single-category detector output. Although the method itself does not directly use inter-class information, they utilize the detections given by the contextual rescoring approach of [START_REF] Girshick | Discriminatively trained deformable part models[END_REF]. Our non-contextual detector performs comparably at 38.5% mAP, and our contextual detector performs significantly better at 40.5% mAP compared to their 38.7%. In principle their method is generic, therefore, potentially additional gains may be achieved by applying their method on the top of our object detector.

Finally, in Table 4 we compare our performance on the PASCAL VOC 2010 dataset to earlier results, again dividing existing methods based on whether or not they use inter-class contextual features. For completeness, we also report the non-contextual and contextual detection results of [START_REF] Fidler | Bottom-up segmentation for top-down detection[END_REF], which are incomparable to the other results in the table, since their method is based on a semantic segmentation model trained using manual segmentation annotations for the training images of both the detection and the seg-mentation challenges of PASCAL VOC 2010.

On the PASCAL VOC 2010 dataset, we obtain an mAP score of 35.8% without contextual rescoring. Our noncontextual detector outperforms all other non-contextual detectors in terms of mAP, and performs comparable to other contextual object detectors. When contextual rescoring is used, detection performance of our method increases to 38.4% mAP, which to the best of our knowledge is 1.6% mAP points above the highest reported result (36.8% mAP) on the PASCAL VOC 2010 dataset.

Compared to the results of Van de Sande et al . [START_REF] Van De Sande | Segmentation as selective search for object recognition[END_REF], which are based on the same candidate windows, our noncontextual detection results are better than theirs on 12 of the 20 categories, as well as on average: 35.8% vs. 34.1%.

Compared to the two best previous methods, NLPR and those of Song et al . [START_REF] Song | Contextualizing object detection and classification[END_REF], which include inter-class context, our mAP score of 38.4% is significantly higher than their 36.8%. In a per-class comparison our system is best on 11 of the 20 categories, NLPR on 3, and Song et al . [START_REF] Song | Contextualizing object detection and classification[END_REF] on 4.

Conclusions

We presented an object detection approach that exploits the powerful high dimensional Fisher vector representation. We use a selective search strategy and data compression to efficiently train and test our detector. We have shown that the same superpixels that drive the selective search can be used to obtain approximate object segmentation masks, which allow us to compute object-centric features that are complementary to full-window features. Our detector also exploits contextual features in the form of a full-image FV descriptor, and an inter-category rescoring mechanism. 2 To the best of our knowledge, our detection results on the PASCAL VOC 2007 and 2010 datasets are the best so far reported on these datasets, when considering the average performance across classes. With a gain of around 2 mAP points, our approximate segmentation masks significantly contribute to the success of our method.

In future work we want to explore the effectiveness of our approximate object detection masks for tasks such as semantic segmentation, by using them as a strongly semantic and spatially detailed prior.

Figure 2 :

 2 Figure 2: Example images where the top scoring detection improves (top row) or degrades (bottom row) with inclusion of the masked window descriptors. Correct detections are shown in yellow, incorrect ones in magenta. See text for details.

Table 1 :

 1 Performance on the development set with different descriptors (S: SIFT, C: color), regions (W: window, G: generating segment, M: mask), and with / without SPM.

	Desc.	Regions	Norm. SPM bus cat mbike sheep mAP
	S	W	object no 22.2 35.8 26.3 16.6 25.2
	S	W	object yes 47.6 45.0 54.2 30.0 44.2
	S	W	cell yes 48.0 47.2 53.0 32.0 45.0
	S G (train on W) cell yes 35.7 46.3 43.2 17.0 35.5
	S M (train on W) cell yes 41.1 47.8 52.7 19.2 40.2
	S	M	cell yes 44.0 48.8 51.4 30.8 43.8
	S	W+M	cell yes 48.5 49.2 54.3 33.8 46.4
	S+C	W	cell yes 47.3 48.2 54.4 35.8 46.4
	S+C	W+M	cell yes 48.1 51.1 55.5 40.0 48.7
	S+C	W+M+F	cell yes 50.3 51.6 54.8 41.9 49.6

Table 2 :

 2 Performance on VOC'07 with different descriptors (S: SIFT, C: color), regions (W: window, M: mask, F: full image). aero bicy bird boa bot bus car cat cha cow dtab dog hors mbik pers plnt she sofa trai tv mAP S W 46.7 48.7 14.1 19.4 15.7 45.0 54.6 36.3 11.4 36.2 37.4 24.3 37.1 52.4 25.8 14.7 35.3 30.4 47.2 48.2 34.0 S W+M 50.2 49.4 16.6 21.3 15.7 45.5 55.3 39.8 14.8 36.3 39.5 25.4 42.4 50.4 30.6 15.8 34.3 35.5 48.3 49.7 35.8 S+C W 47.7 50.1 16.5 19.2 15.9 45.1 55.1 37.2 13.0 37.3 40.8 25.5 40.7 51.8 26.4 18.2 35.5 30.6 47.7 49.6 35.2

	S+C	W+M	50.5 51.2 18.8 23.8 17.8 47.2 56.4 41.6 14.7 38.6 40.7 27.1 47.3 52.4 29.7 19.6 38.3 35.0 49.3 52.8 37.6
	S+C	W+F	49.9 51.6 16.4 21.7 16.5 45.9 55.6 38.4 15.3 42.1 42.0 25.3 41.2 52.2 26.8 18.8 36.2 35.8 48.5 51.6 36.6
	S+C	W+M+F	52.6 52.6 19.2 25.4 18.7 47.3 56.9 42.1 16.6 41.4 41.9 27.7 47.9 51.5 29.9 20.0 41.1 36.4 48.6 53.2 38.5
	S+C W+M+F+Context 56.1 56.4 21.8 26.8 19.9 49.5 57.9 46.2 16.4 41.4 47.1 29.2 51.3 53.6 28.6 20.3 40.5 39.6 53.5 54.3 40.5

Table 3 :

 3 Comparison of our detector with and without context with the state-of-the-art object detectors on VOC 2007. 29.5 53 57.1 49.9 48.5 11 23 27.7 13.1 58.9 22.4 41.4 16 22.9 28.6 37.2 42.4 34.7 Ours, without context 52.6 52.6 19.2 25.4 18.7 47.3 56.9 42.1 16.6 41.4 41.9 27.7 47.9 51.5 29.9 20.0 41.1 36.4 48.6 53.2 38.5 methods using inter-class contextual cues GFM'12 context [16] 36.6 62.2 12.1 17.6 28.7 54.6 60.4 25.5 21.1 25.6 26.6 14.6 60.9 50.7 44.7 14.3 21.5 38.2 49.3 43.6 35.4 CDXH'13 [5] 41.0 64.3 15.1 19.5 33.0 57.9 63.2 27.8 23.2 28.2 29.1 16.9 63.7 53.8 47.1 18.3 28.1 42.2 53.1 49.3 38.7 Ours, with context 56.1 56.4 21.8 26.8 19.9 49.5 57.9 46.2 16.4 41.4 47.1 29.2 51.3 53.6 28.7 20.3 40.5 39.6 53.5 54.3 40.5

		aero bicy bird boa bot bus car cat cha cow dtab dog hors mbik pers plnt she sofa trai tv mAP
		methods without inter-class contextual cues
	SUGS'11 [34]	43.3 46.4 11.2 11.9 9.3 49.3 53.7 39.2 12.5 36.8 42.0 26.4 47.0 52.1 23.5 11.9 29.7 36.1 42.0 48.7 33.7
	HMR'12 [19]	23.3 41.0 9.9 11.0 17.0 37.8 38.4 11.5 11.8 14.5 12.2 10.2 44.8 27.9 22.4 3.1 16.3 8.9 30.3 28.8 21.0
	VZ'12 [36]	27.9 55.2 9.5 10.4 16.4 47.6 52.0 16.0 13.5 18.6 20.7 10.7 53.4 39.7 37.3 10.4 12.7 19.7 41.7 40.9 27.7
	GFM'12 [16]	33.2 60.3 10.2 16.1 27.3 54.3 58.2 23.0 20.0 24.1 26.7 12.7 58.1 48.2 43.2 12.0 21.1 36.1 46.0 43.5 33.7
	KAWBVL'12 [22]	34.5 61.1 11.5 19.0 22.2 46.5 58.9 24.7 21.7 25.1 27.1 13.0 59.7 51.6 44.0 19.2 24.4 33.1 48.4 49.7 34.8
	SWJZ'13 [32]	35.3 60.2 16.6

Table 4 :

 4 Comparison of our detector with and without context with the state-of-the-art object detectors on VOC 2010. aero bicy bird boa bot bus car cat cha cow dtab dog hors mbik pers plnt she sofa trai tv mAP methods without inter-class contextual cues SUGS'11 [34] 58.2 41.9 19.2 14.0 14.3 44.8 36.7 48.8 12.9 28.1 28.7 39.4 44.1 52.5 25.8 14.1 38.8 34.2 43.1 42.6 34.1 GFM'12 [16] 45.6 49.0 11.0 11.6 27.2 50.5 43.1 23.6 17.2 23.2 10.7 20.5 42.5 44.5 41.3 8.7 29.0 18.7 40.0 34.5 29.6 SWJZ'13 [32] 44.6 48.5 12.9 26.3 47.5 41.6 45.3 39 10.8 21.6 23.6 22.9 40.9 30.4 37.9 9.6 17.3 11.5 25.3 31.2 29.4 Ours, without context 61.3 46.4 21.1 21.0 18.1 49.3 45.0 46.9 12.8 29.2 26.1 38.9 40.4 53.1 31.9 13.3 39.9 33.4 43.0 45.3 35.8 methods using inter-class contextual cues NLPR 2010 * 53.3 55.3 19.2 21.0 30.0 54.4 46.7 41.2 20.0 31.5 20.7 30.3 48.6 55.3 46.5 10.2 34.4 26.5 50.3 40.3 36.8 SCHHY'11 [33] 53.1 52.7 18.1 13.5 30.7 53.9 43.5 40.3 17.7 31.9 28.0 29.5 52.9 56.6 44.2 12.6 36.2 28.7 50.5 40.7 36.8 GFM'12 context [16] 48.2 52.2 14.8 13.8 28.7 53.2 44.9 26.0 18.4 24.4 13.7 23.1 45.8 50.5 43.7 9.8 31.1 21.5 44.4 35.7 32.2 Ours, with context 65.9 50.1 23.7 24.1 20.4 52.6 47.1 50.9 13.2 32.8 31.8 41.4 43.9 55.3 29.8 14.1 41.7 35.6 46.7 46.9 38.4 uncomparable methods using additional training data FMYU'13 [15] * * 56.4 48.0 24.3 21.8 31.3 51.3 47.3 48.2 16.1 29.4 19.0 37.5 44.1 51.5 44.4 12.6 32.1 28.8 48.9 39.1 36.6 FMYU'13 context [15] * * 61.4 53.4 25.6 25.2 35.5 51.7 50.6 50.8 19.3 33.8 26.8 40.4 48.3 54.4 47.1 14.8 38.7 35.0 52.8 43.1 40.4 * These results do not directly correspond to papers and are taken directly from the PASCAL VOC 2010 website instead.

* * Utilizes groundtruth segmentation annotations and extra training images.

Acknowledgements. This work was supported by Quaero (funded by OSEO, French State agency for innovation), the European integrated project AXES, and the ERC advanced grant ALLEGRO.


Roland Hildebrand
email: roland.hildebrand@imag.fr

The extreme rays of the 5 × 5 copositive cone

Keywords: copositive cone, extremal rays 2000 MSC: 15A48, 15A21

We give an explicit characterization of all extreme rays of the cone C 5 of 5 × 5 copositive matrices. We show that the extreme rays which are not positive semi-definite or nonnegative form a 10-dimensional variety, which can be parameterized in a semi-trigonometric way.

Introduction

A real symmetric n × n matrix A is called copositive if x T Ax ≥ 0 for all x ∈ R n + . The set of copositive matrices forms a convex cone C n , the copositive cone. Clearly A is copositive if it is either positive semi-definite or if all its elements are nonnegative. Hence both the cone S + (n) of all n×n real symmetric positive semi-definite matrices and the cone N n of all n × n real symmetric nonnegative matrices are contained in C n . It is a classical result by Diananda [START_REF] Diananda | On nonnegative forms in real variables some or all of which are nonnegative[END_REF] that for n ≤ 4 the cone C n equals the sum S + (n) + N n . For n ≥ 5 there exist matrices in C n which cannot be represented as a sum of a positive semi-definite matrix and a nonnegative matrix. An example of such a matrix is the Horn form [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF]

H =       1 -1 1 1 -1 -1 1 -1 1 1 1 -1 1 -1 1 1 1 -1 1 -1 -1 1 1 -1 1       . (1)
While the sum S + (n)+N n can easily be handled algorithmically, problems involving the copositive cone are in general difficult. Of particular help in the description of the copositive cone is any information on its extreme rays. Since deciding inclusion of an integer matrix into the copositive cone is NPcomplete [START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF], a general explicit characterization of the extreme rays of C n is unlikely to be found. However, those extreme rays which belong to the sum S + (n) + N n have been characterized completely, and the Horn form [START_REF] Diananda | On nonnegative forms in real variables some or all of which are nonnegative[END_REF] has been characterized as an extreme ray of C 5 which does not belong to this sum [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF]. It follows that all forms that can be obtained from the Horn form by a permutation of the indices and a scaling with a positive diagonal matrix are also extreme rays of C 5 which do not belong to S + (5) + N 5 .

In [START_REF] Baumert | Extreme copositive quadratic forms[END_REF]Theorem 3.8] a procedure is presented how to construct an extreme ray of C n+1 from an extreme ray of C n . Those extreme rays of C n with elements only from the set {-1, 0, +1} have been characterized in [START_REF] Hoffman | On copositive matrices with -1,0,1 entries[END_REF]. In [START_REF] Dickinson | Geometry of the copositive and completely positive cones[END_REF] the dimensions of the maximal faces of the copositive and completely positive cones are studied as well as exposedness of their extreme rays. Much work has also been devoted to characterize the difference between the completely positive cone C * n and the intersection S + (n) ∩ N n , which are the dual cones to C n and S + (n) + N n , respectively. Special emphasis has been made on the 5 × 5 case. In [START_REF] Ycart | Extrémales du cône des matrices de type non négatif, à coefficients positifs ou nuls[END_REF] the extreme rays of S + (n) ∩ N n for n = 5, 6 are characterized, and a procedure for general n is given. An earlier paper with a partial characterization of the 5 × 5 completely positive cone is [START_REF] Xu | Completely positive matrices of order five[END_REF]. In [START_REF] Burer | The difference between 5 × 5 doubly nonnegative and completely positive matrices[END_REF] extreme rays of S + (5) ∩ N 5 which do not belong to C * 5 are characterized and it is shown how to separate them from C * 5 by a copositive matrix. In this note we focus on the extreme rays of the cone C 5 . Baumert [START_REF] Baumert | Extreme copositive quadratic forms. II[END_REF] has shown that there exist extreme rays of C 5 which are not in the sum S + (5) + N 5 and are not equivalent to the Horn form in the above-mentioned sense. We use results of [START_REF] Baumert | Extreme copositive quadratic forms. II[END_REF] and [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF] to obtain a simple semi-trigonometric parametrization of these extreme rays, thus providing an exhaustive explicit description of all extreme rays of the cone C 5 .

Notations

For a given n ≥ 1, denote by e ij = e ji , i, j = 1, . . . , n, the generators of the extreme rays of the cone N n , normalized such that their elements are from the set {0, 1}. Let e i , i = 1, . . . , n be the canonical basis vectors of R n , and let ∆ n = {x ∈ R n + | n j=1 x j = 1} be their convex hull. Let Aut(R n + ) be the automorphism group of the positive orthant. It is generated by all n × n permutation matrices and by all n × n diagonal matrices with positive diagonal elements. This group generates a group G n of automorphisms of C n by A → GAG T , G ∈ Aut(R n + ). For any nonzero x ∈ R n + , the pattern of x will be the vector sgn(x) T , where the sign function is applied elementwise.

We will work a lot with systems of equations that can be obtained from each other by a cyclical shift of indices. To simplify notation, we introduce the following index convention. The notation k|n means that the index k, which can be any integer, has to be shifted modulo n into the range 1, . . . , n. With this convention, e.g., ψ 6|5 := ψ 1 .

Let A be an n × n matrix, v ∈ R n a vector, and I ⊂ {1, . . . , n} a subset of indices. By A I we denote the principal submatrix of A whose elements have row and column indices in I, and by v I the subvector of v whose elements have indices in I. In the case n = 5, we define the special index sets I 4 j = {1, . . . , n} \ {j} and I 3 j = {j -1|5, j, j + 1|5}, j = 1, . . . , 5. Finally, we define the 5-parametric family of matrices

T (ψ) =       1 -cos ψ 4 cos(ψ 4 +ψ 5 ) cos(ψ 2 +ψ 3 ) -cos ψ 3 -cos ψ 4 1 -cos ψ 5 cos(ψ 5 +ψ 1 ) cos(ψ 3 +ψ 4 ) cos(ψ 4 +ψ 5 ) -cos ψ 5 1 -cos ψ 1 cos(ψ 1 +ψ 2 ) cos(ψ 2 +ψ 3 ) cos(ψ 5 +ψ 1 ) -cos ψ 1 1 -cos ψ 2 -cos ψ 3 cos(ψ 3 +ψ 4 ) cos(ψ 1 +ψ 2 ) -cos ψ 2 1      
, where ψ = (ψ 1 , . . . , ψ 5 ) T is a quintuple of angles. In various settings in the paper, these angles will satisfy one or more of the inequalities

ψ j > 0 ∀ j = 1, . . . , 5, (2)
ψ j + ψ j+1|5 < π ∀ j = 1, . . . , 5, (3) 5 j=1 ψ j < π, (4)
t j = cos(ψ j-1|5 +ψ j +ψ j+1|5 )+cos(ψ j-2|5 +ψ j+2|5 ) > 0, ∀ j = 1, . . . , 5.(5)

Known results

In this section we collect known results on the structure of the cone C n and its extreme rays, in particular for the value n = 5, which will be used later.

Theorem 2.1. [2, Theorem 3.2] The extreme rays of C n which belong to S + (n) + N n are generated by e ij , i, j = 1, . . . , n, and by matrices of the form aa T , where the vectors a ∈ R n contain both positive and negative elements. Lemma 7,(i)] Let A ∈ C n be a copositive matrix, and let

Lemma 2.2. [1,
x ∈ R n + be such that x T Ax = 0. Let further I = {i ∈ {1, . . . , n} | x i > 0}. Then A I is positive semi-definite.
The following slight reformulation of [10, Lemma 4.5] will be the departure point for the proof of our main result.

Lemma 2.3. Let A ∈ C 5 generate an extreme ray, and suppose that A is neither an element of the sum S + (5) + N 5 nor in the orbit of the Horn form [START_REF] Diananda | On nonnegative forms in real variables some or all of which are nonnegative[END_REF] under the action of G 5 . Suppose further that for every pair of indices (i, j), i, j = 1, . . . , 5 there exists a zero u ∈ R 5 + of A with u i u j > 0. Then there exists a permutation matrix P1 such that the set {x ∈ ∆ 5 | x T P T AP x = 0} consists of 5 isolated points with patterns (11001), ( 11100), ( 01110), ( 00111), (10011). Now Theorems 5.5 and 3.1 in [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF] yield the following result.

Lemma 2.4. Let A ∈ C 5 generate an extreme ray, and suppose that A is neither an element of the sum S + (5) + N 5 . Then for every pair of indices (i, j), i, j = 1, . . . , 5 there exists a zero u ∈ R 5 + of A with u i u j > 0. Hence the condition on the existence for every pair (i, j) of a zero u with u i u j > 0 can be omitted from Lemma 2.3, yielding the following theorem.

Theorem 2.5. Let A ∈ C 5 generate an extreme ray, and suppose that A is neither an element of the sum S + (5) + N 5 nor in the orbit of the Horn form [START_REF] Diananda | On nonnegative forms in real variables some or all of which are nonnegative[END_REF] under the action of G 5 . Then there exists a permutation matrix P such that the set {x ∈ ∆ 5 | x T P T AP x = 0} consists of 5 isolated points with patterns (11001), (11100), (01110), (00111), (10011).

Main result

In this section we prove the following result. Theorem 3.1. Let A ∈ C 5 generate an extreme ray, and suppose that A is neither an element of the sum S + (5) + N 5 nor in the orbit of the Horn form [START_REF] Diananda | On nonnegative forms in real variables some or all of which are nonnegative[END_REF] under the action of G 5 . Then A is of the form

A = P • D • T (ψ) • D • P T , ( 6
)
where P is a permutation matrix,

D = diag(d 1 , d 2 , d 3 , d 4 , d 5
) with d j > 0, j = 1, . . . , 5, and the quintuple ψ is an element of the set

Φ = {ψ ∈ R 5 | ψ satisfies (2,4)}. ( 7
)
Conversely, for every permutation matrix P , every diagonal matrix D with positive diagonal entries, and every quintuple of angles ψ ∈ Φ, the matrix A given by ( 6) generates an extreme ray of C 5 with the above exclusion properties.

We postpone the proof of the theorem and first provide the following technical lemmas.

Lemma 3.2. Let C ∈ S + (3) be such that the set {x ∈ ∆ 3 | x T Cx = 0} consists of an isolated point in the interior of ∆ 3 . Then C can be represented in the form C = D   1 -cos ψ 1 cos(ψ 1 + ψ 2 ) -cos ψ 1 1 -cos ψ 2 cos(ψ 1 + ψ 2 ) -cos ψ 2 1   D, (8)
where D = diag(d 1 , d 2 , d 3 ) with d j > 0, j = 1, 2, 3, and ψ 1 , ψ 2 satisfy the inequalities

ψ j > 0, j = 1, 2, (9)
ψ 1 + ψ 2 < π. ( 10
)
Conversely, for every matrix D = diag(d 1 , d 2 , d 3 ) with d j > 0, j = 1, 2, 3, and angles ψ 1 , ψ 2 satisfying (9,10) the matrix C given by [START_REF] Xu | Completely positive matrices of order five[END_REF]

is in S + (3) and the set {x ∈ ∆ 3 | x T Cx = 0} consists of an isolated point in the interior of ∆ 3 , which is proportional to D -1 (sin ψ 2 , sin(ψ 1 + ψ 2 ), sin ψ 1 ) T .
Proof. Assume the conditions of the first part of the lemma. If C has a zero diagonal entry, say C 11 = 0, then e T 1 Ce 1 = 0, which leads to a contradiction with the assumption that the zero of C is in the interior of ∆ 3 . Hence the diagonal elements of C are positive. Put d j = C jj , j = 1, 2, 3, and

D = diag(d 1 , d 2 , d 3 ). If an off-diagonal element of C ′ = D -1 CD -1 equals -1, say C ′
12 , then (e 1 + e 2 ) T C ′ (e 1 + e 2 ) = 0, and D -1 (e 1 + e 2 ) is a zero of C in ∂∆ 3 , again leading to a contradiction. Therefore the off-diagonal elements of C ′ are in the interval (-1, 1], and we find angles ψ 1 , ψ 2 ∈ (0, π] (and hence satisfying [START_REF] Burer | The difference between 5 × 5 doubly nonnegative and completely positive matrices[END_REF]) such that

C ′ 12 = -cos ψ 1 , C ′ 23 = -cos ψ 2 . We then have det C ′ = 1 + 2C ′ 13 cos ψ 1 cos ψ 2 -cos 2 ψ 1 -cos 2 ψ 2 -(C ′ 13 ) 2 = 0, which yields C ′ 13 = cos ψ 1 cos ψ 2 + σ sin ψ 1 sin ψ 2 , where σ = ±1. If C ′ is of rank 1, then ψ 1 = ψ 2 = π
and hence C ′ is the all-ones matrix, which contradicts the presence of a kernel vector with positive elements. Hence the rank of C ′ is 2 and C ′ has a 1-dimensional kernel, which by virtue of

  1 -cos ψ 1 cos ψ 1 cos ψ 2 +σ sin ψ 1 sin ψ 2 -cos ψ 1 1 -cos ψ 2 cos ψ 1 cos ψ 2 +σ sin ψ 1 sin ψ 2 -cos ψ 2 1     sin ψ 2 cos(σ(ψ 2 -π 2 )-ψ 1 ) -σ sin ψ 1   = 0 (11) is proportional to v σ = (sin ψ 2 , cos(σ(ψ 2 -π/2) -ψ 1 )
, -σ sin ψ 1 ) T . Note that v σ = 0, since ψ 1 , ψ 2 are not both equal to π. Hence v σ has to have positive elements, which discards the choice σ = 1 and implies [START_REF] Baumert | Extreme copositive quadratic forms. II[END_REF]. This proves the first part of the lemma.

Let us pass to the second part. By virtue of [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF] it is sufficient to show that C ′ = D -1 CD -1 is positive semi-definite and of rank 2. This is easily seen by virtue of the factorization

  1 -cos ψ 1 cos(ψ 1 +ψ 2 ) -cos ψ 1 1 -cos ψ 2 cos(ψ 1 +ψ 2 ) -cos ψ 2 1   =   sin ψ 1 -cos ψ 1 0 1 -sin ψ 2 -cos ψ 2     sin ψ 1 -cos ψ 1 0 1 -sin ψ 2 -cos ψ 2   T .
(12) This completes the proof.

Lemma 3.3. The following implications hold. i) [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF][START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF][START_REF] Hoffman | On copositive matrices with -1,0,1 entries[END_REF] imply (4); ii) (2,4) imply (3); iii) (2-4) imply [START_REF] Hoffman | On copositive matrices with -1,0,1 entries[END_REF].

Proof. i) By ( 5) we have

cos(ψ j-1|5 + ψ j + ψ j+1|5 ) = -cos ψ j-1|5 + ψ j + ψ j+1|5 -π > -cos(ψ j-2|5 + ψ j+2|5 ).
Both expressions |ψ j-1|5 + ψ j + ψ j+1|5 -π| and ψ j-2|5 + ψ j+2|5 are contained in the interval [0, π) by (2,3), and on this interval the cosine function is monotonely decreasing. It follows that |ψ j-1|5 + ψ j + ψ j+1|5 -π| > ψ j-2|5 + ψ j+2|5 , which for each j = 1, . . . , 5 amounts to the two possibilities

ψ j-1|5 + ψ j + ψ j+1|5 -ψ j-2|5 -ψ j+2|5 > π, 5 j=1 ψ j < π.
Let us prove by contradiction that the second inequality must hold. Assume that 5 j=1 ψ j ≥ π, then for all j = 1, . . . , 5 we have ψ j-1|5 + ψ j + ψ j+1|5ψ j-2|5 -ψ j+2|5 > π. Adding all 5 inequalities together, we arrive at 5 j=1 ψ j > 5π, which contradicts (3). This completes the proof of i).

ii) is evident. iii) By (2,3) we have ψ j-1|5 + ψ j + ψ j+1|5 > 0 and ψ j-2|5 + ψ j+2|5 ∈ (0, π), and by virtue of (4) we have -(ψ j-1|5 + ψ j + ψ j+1|5π) > ψ j-2|5 + ψ j+2|5 > 0. Hence both expressions -(ψ j-1|5 + ψ j + ψ j+1|5π) and ψ j-2|5 + ψ j+2|5 are in the interval (0, π), on which the cosine function is monotonely decreasing. Thus, again by virtue of (4), we have

t j = -cos ψ j-1|5 + ψ j + ψ j+1|5 -π + cos(ψ j-2|5 + ψ j+2|5 ) > 0, yielding (5)
. Lemma 3.4. Let ψ ∈ R 5 satisfy [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF][START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF][START_REF] Baumert | Extreme copositive quadratic forms[END_REF]. Then det T (ψ) > 0.

Proof. By Lemma 3.3,iii) we have [START_REF] Hoffman | On copositive matrices with -1,0,1 entries[END_REF]. Introduce the complex variables z j = e iψ j , j = 1, . . . , 5. We then get

t j = z j-1|5 z j z j+1|5 + z -1 j-1|5 z -1 j z -1 j+1|5 2 + z j-2|5 z j+2|5 + z -1 j-2|5 z -1 j+2|5 2 = (z j-1|5 z j z j+1|5 + z j-2|5 z j+2|5 )(1 + z 1 z 2 z 3 z 4 z 5 ) 2z 1 z 2 z 3 z 4 z 5 .
This yields

det T (ψ) = det         1 -
the function f is hence locally invertible, and its level sets consist of isolated points.

Remark 3.6. The determinants in the proofs of Lemmas 3.4 and 3.5 were computed using a computer algebra system.

In the next sections we prove Theorem 3.1.

Proof of the first part

Assume the conditions of the first part of Theorem 3.1. By Theorem 2.5 there exists a permutation matrix P such that A = P A ′ P T and A ′ has exactly 5 isolated zeros u 1 , . . . , u 5 ∈ ∆ 5 with patterns (11001), (11100), ( 01110), (00111), (10011), respectively. Then by Lemma 2.2 the 3 × 3 submatrices A ′ I 3 j of A ′ are positive semi-definite for j = 1, . . . , 5. Moreover, the set {x ∈

∆ 3 | x T A ′ I 3 j x = 0} consists of a single point, namely u j I 3 j . Hence A ′ I 3 j
satisfies the conditions of the first part of Lemma 3.2 and can be represented in the form [START_REF] Xu | Completely positive matrices of order five[END_REF]. It follows that A has the structure ( 6) with P a permutation matrix, D a diagonal matrix with positive diagonal elements, and ψ satisfying (2,3) by virtue of [START_REF] Burer | The difference between 5 × 5 doubly nonnegative and completely positive matrices[END_REF][START_REF] Baumert | Extreme copositive quadratic forms. II[END_REF]. Note also that T (ψ) is in the orbit of A with respect to G 5 and hence copositive.

It remains to show inequality (4). Consider the upper left 4×4 submatrix B = T I 4 5 (ψ) of T (ψ). The matrix B is copositive and by [1, Theorem 2] must be an element of S + (4) + N 4 , i.e., it can be represented as a sum B ′ + B ′′ with B ′ ∈ S + (4) and B ′′ ≥ 0. By [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF] the vectors x = (sin ψ 5 , sin(ψ 4 + ψ 5 ), sin ψ 4 , 0) T , x ′ = (0, sin ψ 1 , sin(ψ 5 + ψ 1 ), sin ψ 5 ) T are zeros of B. Since these vectors by [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF][START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF] have nonnegative elements, they must also be zeros of both B ′ and B ′′ by the copositivity of these summands. It follows that B ′′ can have nonzero elements only in the upper right and lower left corners, and that both x, x ′ are in the kernel of B ′ . If, however, B ′′ = 0, then B = B ′ , and every convex combination of x, x ′ is also a zero of B with nonnegative elements. This contradicts the condition that A and hence T (ψ) has only isolated zeros in ∆ 5 .

The relation B ′ x = 0 can then be rewritten as follows: there exists t > 0 such that

    1 -cos ψ 4 cos(ψ 4 +ψ 5 ) cos(ψ 2 +ψ 3 )-t -cos ψ 4 1 -cos ψ 5 cos(ψ 5 +ψ 1 ) cos(ψ 4 +ψ 5 ) -cos ψ 5 1 -cos ψ 1 cos(ψ 2 +ψ 3 )-t cos(ψ 5 +ψ 1 ) -cos ψ 1 1         sin ψ 5 sin(ψ 4 +ψ 5 ) sin ψ 4 0     = 0,
which yields t sin ψ 5 = cos(ψ 2 + ψ 3 ) sin cos 5 + cos(ψ 5 + ψ 1 ) sin(ψ 4 + ψ 5 )cos ψ 1 sin ψ 4 = sin ψ 5 (cos(ψ 2 + ψ 3 ) + cos(ψ 1 + ψ 4 + ψ 5 )).

Finally, by virtue of sin ψ 5 > 0, which is a consequence of (2,3), we get cos(ψ 1 + ψ 4 + ψ 5 ) >cos(ψ 2 + ψ 3 ). Repeating the reasoning for the other submatrices T I 4 j (ψ), we arrive at all of the inequalities (5). Now (4) follows from Lemma 3.3,i) and the first part of Theorem 3.1 is proven.

Proof of the second part

Assume A is as in the second part of Theorem 3.1. Since the properties of being copositive, extremal, as well as the exclusion conditions in the formulation of Theorem 3.1 are invariant under the action of G 5 , we can assume without loss of generality that both P and D are given by the identity matrix, and hence A = T (ψ). Note that by Lemma 3.3 the quintuple ψ satisfies all four groups of inequalities (2-5).

A is copositive

The first step will be to prove copositivity of the 4 × 4 submatrices A I -cos(ψ 4 +ψ 5 +ψ 1 )+t 5 cos(ψ 5 +ψ 1 )

-cos ψ 1 1     =     sin ψ 4 -cos ψ 4 0 1 -sin ψ 5 -cos ψ 5 sin(ψ 1 +ψ 5 ) cos(ψ 1 +ψ 5 )         sin ψ 4 -cos ψ 4 0 1 -sin ψ 5 -cos ψ 5 sin(ψ 1 +ψ 5 ) cos(ψ 1 +ψ 5 )     T + t 5 e 14 ,
where t 5 = cos(ψ 4 + ψ 5 + ψ 1 ) + cos(ψ 2 + ψ 3 ) > 0 by Lemma 3.3,iii). Thus B has been represented as a sum of elements in S + (4) and N 4 . This proves copositivity of B. By repeating the argument for the other submatrices A I 4 j , we likewise prove their copositivity.

We shall now consider the values of the quadratic form A on the compact set C = {x ∈ R 5 + | ||x|| 2 = 1}. Since every 4 × 4 principal submatrix of A is copositive, the form A is nonnegative on the boundary of C. Thus the assumption that A is not copositive implies the existence of a local minimum x * of the function f (x) = x T Ax in the interior of C, with f (x * ) < 0. This implies that x * is an eigenvector of A with negative eigenvalue. However, by Lemma 3.4 the matrix A has at least another negative eigenvalue, and this implies the existence of a path on the shell ||x|| 2 = 1 linking x * with -x * on which the form A is strictly negative. But since -x * ∈ C, this contradicts the condition that A is nonnegative on the boundary of C. Hence A must be copositive.

A is extremal

From [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF] it follows that A is zero on the columns x 1 , . . . , x 5 of the matrix

      sin(ψ 3 + ψ 4 ) sin ψ 5 0 0 sin ψ 2 sin ψ 3 sin(ψ 4 + ψ 5 ) sin ψ 1 0 0 0 sin ψ 4 sin(ψ 5 + ψ 1 ) sin ψ 2 0 0 0 sin ψ 5 sin(ψ 1 + ψ 2 ) sin ψ 3 sin ψ 4 0 0 sin ψ 1 sin(ψ 2 + ψ 3 )      
.

We are done if we show that A is, up to multiplication with a constant, the only copositive form that is zero on these vectors. Let B be another such form. Then the 3 × 3 submatrix B I 3 j of B is positive semi-definite by Lemma 2.2. Its kernel contains the vector x j ) with d ′ j > 0, j = 1, . . . , 5, and ξ = (ξ 1 , . . . , ξ 5 ) T satisfies [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF][START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF]. Now by the second part of Lemma 3.2 the kernel of C I 3 j is proportional to the vector (d ′ -1 j-1|5 sin ξ j-2|5 , d ′ -1 j sin(ξ j-2|5 + ξ j+2|5 ), d ′ -1 j+1|5 sin ξ j+2|5 ) T . Hence there exist constants ρ j > 0, j = 1, . . . , 5, such that for all j = 1, . . . , 5

ρ j d ′ -1 j-1|5 sin ξ j-2|5 = sin ψ j-2|5 , (13)
ρ j d ′ -1 j sin(ξ j-2|5 + ξ j+2|5 ) = sin(ψ j-2|5 + ψ j+2|5 ), (14)
ρ j d ′ -1 j+1|5 sin ξ j+2|5 = sin ψ j+2|5 . (15)
Combining (13) for j and (15) for j ′ = j + 1|5, we obtain the relations ρ j d ′ -1 j-1|5 = ρ j+1|5 d ′ -1 j+2|5 , j = 1, . . . , 5. These 5 relations determine the constants ρ j up to a common positive factor ρ in dependence of the numbers d ′ j , namely ρ j = ρd ′ j-1|5 d ′ j d ′ j+1|5 . Thus (13,14) become

d ′ j-2|5 ρd ′ j+2|5 sin ξ j = sin ψ j , (16)
-ρd ′ j-1|5 d ′ j+1|5 sin(ξ j-2|5 + ξ j+2|5 ) = -sin(ψ j-2|5 + ψ j+2|5 ). ( 17
)
Multiplying on the one hand ( 16) with (17) for j, and on the other hand (16) for j ′ = j -1|5 and j ′′ = j + 1|5, and taking the ratio of both products, we obtain for all j = 1, . . . , 5

- sin ξ j sin(ξ j-2|5 + ξ j+2|5 ) sin ξ j-1|5 sin ξ j+1|5 = - sin ψ j sin(ψ j-2|5 + ψ j+2|5 ) sin ψ j-1|5 sin ψ j+1|5 . (18)
Now note that ξ is an explicit continuous function of the elements of C, given elementwise by ξ j = arccos

-C j-2|5,j+2|5 √ C j-2|5,j-2|5 C j+2|5,j+2|5
. For λ = 0 we have C = A and hence ξ = ψ, which is indeed a solution of (18). Moreover, by Lemma 3.5 this is the only solution to equation (18) in some neighbourhood of ψ. Therefore ξ ≡ ψ for all λ ∈ [0, 1], because C is continuous in λ. From (16) we then get d ′ j-2|5 d ′ j+2|5 = ρ -1 for all j = 1, . . . , 5. Taking the logarithm of these equations, we get a linear system in log d ′ j , whose only solution is given by d ′ j = ρ -1/2 for all j = 1, . . . , 5. Thus C = ρ -1 A, and B must be proportional to A. This proves the extremality of A.

A satisfies the exclusion properties

From (3) it follows that there exists at least one index j such that ψ j < π 2 . This impliescos ψ j < 0, so A = T (ψ) is not nonnegative. Now recall that by (12) the 3 × 3 submatrices A I 3 j have rank 2. If A were positive semi-definite, it could hence not be of full rank, which contradicts Lemma 3.4.

It remains to show that A is not in the orbit of the Horn form. To see this, note that the 2 × 2 principal submatrices of A are of full rank by virtue of (2,3), while those of the Horn form are of rank 1, and that this property is invariant under the action of G 5 .

This completes the proof of Theorem 3.1.

Conclusions

Theorems 3.1, 2.1, and the fact that the Horn form is extremal in C 5 [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF] furnish an exhaustive description of the generators of the cone C 5 . While the orbit of the Horn form and the positive semi-definite extremals form 5-dimensional varieties, the extremals (6) form a 10-dimensional variety, parameterized by the diagonal elements of D and the quintuple of angles ψ.

Here for each permutation P we obtain a smooth component of this variety. Since cyclic permutations of the indices and a complete reversal of order yield the same zero pattern in Theorem 2.5 and hence the same smooth component, there exist 5!/10 = 12 such smooth components.

It is worth noting that the intersection of each smooth component with the affine subspace of matrices all whose diagonal elements equal 1 is homeomorphic to the simplex Φ given by [START_REF] Ycart | Extrémales du cône des matrices de type non négatif, à coefficients positifs ou nuls[END_REF]. For P the identity permutation, the vertices of this simplex correspond to the Horn form (for ψ j = 0 for all j = 1, . . . , 5) and to positive semi-definite extremals (for the other 5 vertices). The boundary points on the face opposite to the vertex ψ = 0 also correspond to positive semi-definite matrices (see the proof of Lemma 5.3 in [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF]), while the boundary points on the other faces correspond to forms which can be represented as sums of a rank 1 PSD matrix and a matrix in the orbit of the Horn form (see [START_REF] Dickinson | Irreducible elements of the copositive cone[END_REF]Theorem 3.1]).

1 - 5 -cos ψ 4 1 -cos ψ 5 cos(ψ 5 +ψ 1 )cos(ψ 4 +ψ 5 ) -cos ψ 5 1 -cos ψ 1

 15151511 4 j . Let B = T I 4 5 (ψ) as in the previous subsection. We have the representation cos ψ 4 cos(ψ 4 +ψ 5 ) -cos(ψ 4 +ψ 5 +ψ 1 )+t

I 3 j 3 j) T B I 3 j x j I 3 j= 3 j

 3333 = (sin ψ j-2|5 , sin(ψ j-2|5 + ψ j+2|5 ), sin ψ j+2|5 ) T , because (x j I (x j ) T Bx j = 0. Note that by virtue of (12) the submatrices A I 3 j have rank 2. By possibly replacing B by a convex combination λB + (1λ)A with λ > 0 small enough, we may assume without restriction of generality that the submatrices λB I 3 j + (1λ)A I 3 j also have rank 2 for all λ ∈ [0, 1], and their 1-dimensional kernel is generated byx j I 3 j . Choose λ ∈ [0,1] and set C = λB + (1λ)A. Since all elements of x j I are positive, Lemma 3.2 is applicable to the submatrices C I 3 j , and C has a representation of the form D ′ T (ξ)D ′ , where D ′ = diag(d ′ 1 , . . . , d ′ 5

This relabeling condition has been forgotten in the original formulation of [10, Lemma 4.5].

(1 + z 1 z 2 z 3 z 4 z 5 ) 3 5 j=1 (z j-1|5 z j z j+1|5 + z j-2|5 z j+2|5 ) 16z 4 1 z 4 2 z 4 3 z 4 4 z 4 5

where the last inequality holds by j ψ j ∈ (0, π), as a consequence of (2,4), and by virtue of (5).

Lemma 3.5. Define a function f : Φ → R 5 componentwise by f j (ψ) = -sin ψ j sin(ψ j-2|5 +ψ j+2|5 ) sin ψ j-1|5 sin ψ j+1|5

, j = 1, . . . , 5, where Φ is given by [START_REF] Ycart | Extrémales du cône des matrices de type non négatif, à coefficients positifs ou nuls[END_REF]. Then the equation f (ψ) = c, c ∈ R 5 a constant vector, has only isolated solutions in Φ.

Proof. By Lemma 3.3,ii) the elements ψ ∈ Φ satisfy all three sets of inequalities [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF][START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF][START_REF] Baumert | Extreme copositive quadratic forms[END_REF]. The Jacobian ∂f ∂ψ is given by Introducing complex variables z j = e iψ j and computing the determinant, we get

sin ψ 1 sin ψ 2 sin ψ 3 sin ψ 4 sin ψ 5 > 0.

The last inequality comes from the fact that 5 j=1 ψ j ∈ (0, π) by virtue of (2,4) and ψ j ∈ (0, π) by virtue of [START_REF] Hall | Copositive and completely positive quadratic forms[END_REF][START_REF] Murty | Some NP-complete problems in quadratic and nonlinear programming[END_REF]. By the implicit function theorem


Roland Hildebrand
email: roland.hildebrand@imag.fr

On the ∞-norm of the cubic form of complete hyperbolic affine hyperspheres

Let Mn ⊂ R n+1 be a complete hyperbolic affine hypersphere with mean curvature H, H < 0, and let C be its cubic form. We derive a differential inequality and an upper bound on the scalar function ||C||∞ defined by the fiber-wise maximum of the value of C on the unit sphere bundle of M . The bound is attained for the affine hyperspheres which are asymptotic to a simplicial cone.

Introduction

The subject of this paper are complete hyperbolic affine hyperspheres. The Calabi conjecture [START_REF] Calabi | Complete affine hyperspheres I[END_REF] states that every hyperbolic affine hypersphere M which is complete (in the affine metric or in a metric induced by some Euclidean metric of the ambient affine space) is asymptotic to a regular (with nonempty interior and containing no lines) convex cone in the ambient space, with vertex in the center of M , and conversely, for every regular convex cone K in the ambient space and every negative real number H there exists a unique hyperbolic affine hypersphere with center in the vertex of K and with mean curvature H which is asymptotic to K. The conjecture has been proven by the efforts of many authors, a synthesis of the proof is given in [5, Section 2].

In [2, Lemma 5.2, p.31] Calabi obtained a differential inequality on the maximal eigenvalue of the Ricci tensor on complete hyperbolic affine hyperspheres and proved that the Ricci curvature has to be non-positive [START_REF] Calabi | Complete affine hyperspheres I[END_REF]Theorem 5.1,p.31]. He also showed that this bound is sharp, by presenting an example of a complete hyperbolic affine hypersphere with flat affine metric, namely the one which is asymptotic to a simplicial cone [2, p.37]. Similar differential inequalities and bounds can be obtained for the Pick invariant [9, eq. (2.5)], [START_REF] Li | Global affine differential geometry of hypersurfaces[END_REF]Cor. 2.6.5,p.128].

In this contribution we use the techniques of [START_REF] Calabi | Complete affine hyperspheres I[END_REF] to obtain a differential inequality (Theorem 3.1) and a bound (Corollary 4.1) on the function

Υ(x) = max ξ∈TxM,||ξ||=1 (C(x))(ξ, ξ, ξ) (1)
on a complete hyperbolic affine hypersphere M , with C being the cubic form. This function can be considered as the (point-wise) ∞-norm of the cubic form. The main motivation for studying this function lies in conic optimization, to which a link can be made as follows. An n-dimensional complete hyperbolic affine hypersphere M with center in the origin of R n+1 is asymptotic to some regular convex cone K ⊂ R n+1 . On the interior of K define a logarithmically homogeneous convex function F by the relation F [αM ] = {log α} for all α > 0 (cf. [START_REF] Loftin | Affine spheres and Kähler-Einstein metrics[END_REF]). Then a bound on (1) translates into a bound on the self-concordance parameter [7, Sect. 2.3.3] of an appropriate multiple of F . We will elaborate on this relation in a subsequent publication (cf. also [START_REF] Hildebrand | Barriers on projective convex sets[END_REF]Theorem 4.8]). Our bound on the cubic form is sharp, as we will demonstrate on the example of the affine hypersphere asymptotic to a simplicial cone (Proposition 5.1).

Notations and preliminaries

Let us recall the definition of the cubic form and the expression for its Laplacian on affine hyperspheres. Let M be an n-dimensional complete hyperbolic affine hypersphere with mean curvature H < 0, g the affine metric, ∇ the Levi-Civita connection of the affine metric, and ∇ the affine connection induced by the ambient real affine space. The cubic form is defined as the covariant derivative C = ∇g [8, eq.

R ij = (n -1)Hg ij + 1 4 C rs i C jrs , (2)
∆C ijk = (n + 1)HC ijk + 1 4 C abc (C abi C cjk + C abj C cki + C abk C cij ) - 1 2 C a ib C b jc C c ka . (3)

Differential inequality

Our purpose is to derive a differential inequality on the function Υ defined by (1) on M . Let p ∈ M be an arbitrary point and let ξ ∈ T p M be a maximizer of the cubic form on the unit sphere in

T p M , Υ(p) = (C(p))(ξ, ξ, ξ), ||ξ|| = 1.
Transport ξ from p to a neighbourhood U of p along the geodesics through p by means of the Levi-Civita connection to obtain a smooth unit length vector field on U . Then ξ satisfies ∇ξ = 0, ∆ξ = 0 (4) at p [2, p.32], and Ῡ = C ijk ξ i ξ j ξ k ≤ Υ on U , with equality attained at p. Define the symmetric second-order tensor B = ∇ξ g on U , in index form B ij = C ijk ξ k . Note that B is traceless by the apolarity condition C i ij = 0 [8, Theorem 4.3, p.51], and that B ij ξ i ξ j = Ῡ. Moreover, by [5, Lemma 2.2.3.19, p.106] we have at p that B ij ξ i η j = 0 and B ij η i η j ≤1 2 B ij ξ i ξ j ≤ Ῡ for every unit length vector η which is orthogonal to ξ. It follows that ξ is also a maximizer of B(p) on the unit sphere in T p M . In particular, at p we have

B ij ξ j = Ῡg ij ξ j (5)
as the first order optimality condition, and Ῡ is the maximal eigenvalue of the matrix of B(p) in any orthonormal basis of T p M . Let us now estimate the Laplacian of Ῡ. At p we have by virtue of (3),(4), and ( 5)

∆ Ῡ = (∆C) ijk ξ i ξ j ξ k = (n + 1)H Ῡ + 3 4 C abc C abi C cjk ξ i ξ j ξ k - 1 2 C a ib C b jc C c ka ξ i ξ j ξ k = (n + 1)H Ῡ + 3 4 C abc B ab B cj ξ j - 1 2 B a b B b c B c a = (n + 1)H Ῡ + 3 4 ῩB ab B ab - 1 2 B a b B b c B c a ≥ (n + 1)H Ῡ + n(n + 1) 4(n -1) 2 Ῡ3 .
Here the inequality follows from Corollary A.2 in the Appendix. We obtain the following result.

Bound

From Theorem 3.1 we might obtain a bound on the function (1) on a complete hyperbolic affine hypersphere. Namely, from [3, Cor. 1, p.857] 2 it follows that Υ ≤ -4H(n-1)

2 n = 2(n-1) √ -H √ n
. As in the case of the Pick invariant [5, Cor. 2.6.5, p.128], however, there exists a purely algebraic proof.

As in the preceding section, let p ∈ M be an arbitrary point, let ξ ∈ T p M be a maximizer of the cubic form on the unit sphere in T p M , and define the traceless symmetric second-order tensor B = ∇ξ C on T p M . Let {ξ, η 1 , . . . , η n-1 } be an orthonormal basis of T p M , then we have

Υ 2 (p) = (B ij ξ i ξ j ) 2 = - n-1 k=1 B ij η i k η j k 2 ≤ (n -1) n-1 k=1 (B ij η i k η j k ) 2 ≤ (n -1) n-1 k=1 B il B l j η i k η j k = (n -1) B il B li -B il B l j ξ i ξ j = (n -1) C ilj C li k ξ j ξ k -Υ 2 (p) = 4(n -1)(R jk -(n -1)Hg jk )ξ j ξ k -(n -1)Υ 2 (p) ≤ -4(n -1) 2 H -(n -1)Υ 2 (p).
Here we used ( 5) and (2) in the last two equalities, respectively, and the non-positivity of the Ricci curvature [2, Theorem 5.1, p.31] in the last inequality. We obtain the following result.

Corollary 4.1. Let M be an n-dimensional complete hyperbolic affine hypersphere with mean curvature H < 0, and let C be its cubic form. Then the function Υ

(x) = max ξ∈TxM,||ξ||=1 (C(x))(ξ, ξ, ξ) satisfies the inequality Υ ≤ 2(n-1) √ -H √ n
.

Affine hyperspheres asymptotic to a simplicial cone

In this section we show that the inequalities in Theorem 3.1 and Corollary 4.1 are saturated for the affine hyperspheres which are asymptotic to a simplicial cone. Denote by I k the k × k identity matrix, by 1 k ∈ R k the all-ones vector, and by e k ∈ R n the k-th canonical basis vector. Let K = R n+1 + be the nonnegative orthant, H < 0 a negative real number, and let M ⊂ K be the hyperbolic affine hypersphere with mean curvature H which is asymptotic to K. It is well-known that M is given by the equation x 0 • • • • • x n = c for some c > 0. On the interior of K we introduce the coordinates y 0 , . . . , y n by    y 0 . . .

y n    = γU log x = γ 1 √ n+1 1 √ n+1 1 T n -1 √ n+1 1 n I n + 1 n 1 √ n+1 -1 1 n 1 T n    log x 0 . . . log x n    ,
where γ > 0 is a constant to be determined later. Then in the y-coordinates the surface M is given by the equation

y 0 = γ log c √ n+1 . The remaining coordinates y 1 , . . . , y n ∈ R define a global coordinate chart on M .
It is easily seen that the subgroup of unimodular diagonal automorphisms of K, which leaves M invariant, acts by translations on M . The affine metric g and the cubic form C of M have thus constant coefficients. The symmetric group S n+1 , which acts by permutations of the coordinates x i on K, has a unique fixed point y 0 ∈ M given by y 1 = • • • = y n = 0. Therefore S n+1 acts on the tangent space T y 0 M , and both g and C have to be invariant under this action. It is not hard to check that the subgroup S n ⊂ S n+1 permuting the coordinates x 1 , . . . , x n on K acts just by a corresponding permutation of the 2 Obviously, in the formulation of this Corollary it should read d 1 > 0, d 2 < 0, and u ≤ -d 2 /d 1 , otherwise the assertion of the Corollary can be disproved simply by choosing u to be an appropriate constant. The proof of the Corollary contains several flaws, e.g., it assumes that a lower bound on the Ricci curvature implies an upper bound on the quantity r∆r, where r is the distance function from some point p [3, p.856]. Consider the unit ball in R n equipped with the hyperbolic geometry given by the metric g(x)

= (1-R 2 )I+xx T (1-R 2 ) 2
in matrix form, where R = √ x T x is the Euclidean distance from the centre and I the identity matrix. The geodesic distance function from the centre is then given by r = 1 2 log 1+R 1-R , and ∆r = n-1 R . Hence r∆r tends to +∞ as R → 1. It is, however, straightforward to write down a correct proof of the Corollary, e.g., by setting f = (a 2 -r 2 )u [3, p.856]. With the choice f = (1 + cos πr 2 a 2 )u one can handle also differential inequalities of the form ∆ψ ≥ d 1 u 2 + d 2 u. y-coordinates. Therefore the coefficients g ij , C ijk depend only on the number of distinct indices in the sets {i, j} and {i, j, k}, respectively. Denote the latter number by θ ijk . The permutation σ i ∈ S n+1 exchanging the coordinates x 0 , x i acts on T y 0 M by the orthogonal transformation

U i = I - 1 - √ n + 1 n 1 n -e i 1 - √ n + 1 n 1 n -e i T .
It is not difficult to check that the invariance of g and C with respect to the transformations given by U i determines these tensors up to a constant multiple. Namely, the matrix of the metric g has to be proportional to the identity matrix, and the cubic form C is given by

C ijk =    -α(n -1) 2 + (n -2) √ n + 1 , θ ijk = 1, α 2 + (n -2) √ n + 1 , θ ijk = 2, α n + 2 -2 √ n + 1 , θ ijk = 3, (6)
where α is a yet to be determined proportionality constant. Let us choose γ such that the matrix of g is given by I n . Contracting (2) with the metric and taking into account that M is flat, we obtain C irs C irs = -4n(n -1)H. Inserting the values for C irs from (6), we get α 2 n 5 (n -1) = -4n(n -1)H, yielding α = ± 2 √ -H n 2

(it can be checked that the sign is positive).

Hence on the unit length vector 1 √ n 1 n the cubic form has the value αn 3 (n-1)

n 3/2 = ± 2(n-1) √ -H √ n
, finally giving Υ ≥ 2(n-1)

√ -H √ n
. From Corollary 4.1 we can then conclude that Υ ≡ 2(n-1)

√ -H √ n on M . By the affine equivalence of an arbitrary simplicial cone to the nonnegative orthant we obtain the following result.

Proposition 5.1. Let M ⊂ R n+1 be a complete hyperbolic affine hypersphere which is asymptotic to a simplicial cone. Then both the bound in Theorem 3.1 and in Corollary 4.1 are saturated.

In particular, this will allow us to show that the optimal self-concordance parameter of an arbitrary regular convex cone is not worse than the parameter of the standard barrier for the nonnegative orthant of the same dimension.

( 2 . 6 )

 26 , p.34; Theorem 3.3, p.42]. The difference tensor 1 is defined as the difference ∇ -∇ and equals A = -1 2 C [8, Prop.4.1, p.50].The difference tensor and hence the cubic form are symmetric in all three indices[2, pp.23-24]. The Ricci curvature of the affine metric and the Laplacian of C with respect to the affine metric are given by[9, p.3]

Theorem 3 . 1 .

 31 Let M be an n-dimensional complete hyperbolic affine hypersphere with mean curvature H < 0, and let C be its cubic form. Then the function Υ(x) = max ξ∈TxM,||ξ||=1 (C(x))(ξ, ξ, ξ) satisfies the differential inequality ∆Υ ≥ (n + 1)HΥ + n(n+1) 4(n-1) 2 Υ 3 weakly in the sense of[START_REF] Calabi | An extension of E. Hopf's maximum principle with an application to Riemannian geometry[END_REF] Def. 1, p.46].

Sometimes, such as in[START_REF] Calabi | Complete affine hyperspheres I[END_REF], the difference tensor is called cubic form, which can lead to serious confusions and apparently resulted in a missing factor of

in[START_REF] Cheng | Complete affine hypersurfaces, part I. The completeness of affine metrics[END_REF] Cor. 2, p.857] for the bound on the Pick invariant.

A Matrix lemma

In this section we provide an auxiliary inequality.

Lemma A.1. Let n ≥ 2 and λ 1 , . . . , λ n-1 ≤ 1 be such that

Proof. Define c i = (n -1)λ i + 1. Then n-1 i=1 c i = 0 and c i ≤ n for all i. It follows that c 3 i ≤ nc 2 i for all i. We then have

This completes the proof.

Corollary A.2. Let B be a real symmetric n × n matrix with vanishing trace. Then 3 4 λ max (B) tr B 2 -

Proof. If λ max (B) = 0, then B = 0 and the assertion of the corollary is evident. Suppose now that λ max (B) > 0. Let where the inequality comes from the preceding lemma.