Hervé Jégou

Andrew Zisserman

Triangulation embedding and democratic aggregation for image search

We consider the design of a single vector representation for an image that embeds and aggregates a set of local patch descriptors such as SIFT. More specifically we aim to construct a dense representation, like the Fisher Vector or VLAD, though of small or intermediate size.

We make two contributions, both aimed at regularizing the individual contributions of the local descriptors in the final representation. The first is a novel embedding method that avoids the dependency on absolute distances by encoding directions. The second contribution is a "democratization" strategy that further limits the interaction of unrelated descriptors in the aggregation stage.

These methods are complementary and give a substantial performance boost over the state of the art in image search with short or mid-size vectors, as demonstrated by our experiments on standard public image retrieval benchmarks.

Introduction

C ONSIDER the problem of representing a set of vectors describing an image, for example a set of SIFT descriptors [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], by a single set-vector such that a simple comparison of two such set-vectors with cosine similarity reflects the similarity of the original sets. This is what is done in the literature in the many papers on large scale image retrieval, where the first step is to describe an image by a set of vectors (bag-of-features) each representing sub-parts (patches) of the image, and this set is then converted into a single vector based on an aggregation strategy, such as the bag-of-visual-words (BOW) representation [START_REF] Sivic | Video Google: A text retrieval approach to object matching in videos[END_REF], BOW with multiple- [START_REF] Jégou | Improving bag-offeatures for large scale image search[END_REF][START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF] or soft-assignment [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Van Gemert | Visual word ambiguity[END_REF], localityconstrained linear coding [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], VLAD [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF] or the Fisher vector [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF][START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF]. A similar approach is also employed in large scale image classification, but we will concentrate on image retrieval here.

All these methods can be decomposed into two steps: the embedding step individually maps each vector of the set to a high-dimensional space; whilst the aggregating step produces a single vector from the set of mapped vectors, for in-stance using sum-or max-pooling [5]. In this paper, we revisit these two steps and make a novel contribution to each. Our overall objective is to design a "democratic" kernel, such that each vector of the set contributes almost equally to the set similarity. This objective is addressed separately in both the embedding and aggregating stages.

First, we aim to design the embedding step φ such that, for any pair of vectors (x, y) describing two patches, the similarity φ(x) ⊤ φ(y) is close to unity if the patches match, and close to zero if they do not, i.e., the magnitude of φ(x) ⊤ φ(y) should be small for unrelated patches. To this end, our first contribution is to introduce a triangulation embedding (T-embedding) that encodes the input vector with respect to a set of anchor points using only directions, not magnitudes. In contrast to most similar existing techniques [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF][START_REF] Liu | Hashing with graphs[END_REF][START_REF] Roux | Local component analysis[END_REF], we discard the magnitude information between the input vector and the anchor points, as we consider this unreliable. From this point of view, our method can be seen as a way to localize the vector with a triangulation strategy.

Our second contribution is an aggregating strategy that explicitly takes into account the interference between the vectors of a set to remove it, and tends to give equal weight to each vector in the final score between two sets. This involves an optimization problem to find weights linearly balancing the contribution of each mapped vector in the final vector representation, and is solved with a modified Sinkhorn algorithm [START_REF] Knight | The Sinkhorn-Knopp algorithm: convergence and applications[END_REF][START_REF] Sinkhorn | A relationship between arbitrary positive matrices and double stochastic matrices[END_REF]. This method is especially effective for relatively short representations, where it is essential to cancel the interference between the mapped vectors.

As will be demonstrated on public benchmarks for large scale image search, both these contributions give a significant improvement over previous techniques: our Tembedding outperforms the Fisher vector by a large margin for a given dimensionality, and our aggregation strategy offers a similar gain, which is also complementary to the so-called power-law normalization [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF].

This paper is organized as follows. Section 2 introduces notation and motivates our contributions. Section 3 introduces our T-embedding and Section 4 our aggregation strategy. The experiments are presented in Section 5. Appendices are provided as supplementary material and available with code on the project page1 .

Preliminaries

Let us consider two sets X and Y such that card(X ) = n and card(Y) = m. Each set consists of a set of vectors, such as local descriptors associated with an image. We first consider match kernels, in a framework derived from Bo and Sminchisescu [4] 2 , that have the form:

K(X , Y) = x∈X y∈Y k(x, y) = ψ(X ) ⊤ ψ(Y), (1)
where k(x, y) is a kernel between individual vectors of the sets. The right term indicates that we consider more specifically a vector representation for sets, such that two images are compared based on the inner product between their representations ψ(X ) and ψ(Y). The match kernel is also written as

K(X , Y) = 1 ⊤ n K(X , Y) 1 m (2)
where

1 n = [1, . . . , 1]
×n , and we define the n × m matrix

K(X , Y) =    k(x 1 , y 1 ) . . . k(x 1 , y m ) . . . . . . . . . k(x n , y m ) . . . k(x n , y m )    . (3)
This matrix typically contains all the pairwise similarities between the local descriptors of two images. For any kernel K, we denote its normalized counterpart

K ⋆ (X , Y) = α(X ) α(Y) K(X , Y), (4)
where the normalizer α(.) is defined such that K ⋆ (X , X ) = 1, i.e., α(X ) = K(X , X ) -1/2 .

Construction: embedding and aggregation

We divide the construction of K into two steps, namely embedding and aggregation. The embedding step φ : R d → R D maps each x ∈ X as x → φ(x).

(

) 5
The aggregating step computes a single vector from the set {φ(x 1 ), . . . , φ(x n )} of embedded vectors through a function ψ. This function is for instance a simple summation, in which case we denote it ψ s :

ψ s (X ) = x∈X φ(x). (6)
This simple definition of ψ is implicitly used in (1). In this case, k(x, y) = φ(x)|φ(y) . The match kernel K is 2 The only minor difference is that we do not use the same normalizers: [4] normalize the vector representation by the number of features. computed as the inner product between the aggregated vectors:

ψ s (X ) ⊤ ψ s (Y) = x∈X y∈Y φ(x) ⊤ φ(y), (7)
where each possible match (x, y) contributes to the overall set similarity, each with weight φ(x) ⊤ φ(y). This formulation, considered in particular by Bo and Sminchisescu [4] and Tolias et al. [START_REF] Tolias | To aggregate or not to aggregate: Selective match kernels for image search[END_REF], encompasses many approaches. Let us first consider the embedding step. For a bag-of-visual-words vocabulary C of size |C| = D, a single descriptor x of X is mapped to a D-dimensional vector having one component equal to 1 (if not considering inverse document frequency) and the others to zero: φ BOW (x) = [. . . , 0, 1, 0, . . . ] ⊤ . The non-zero position is determined based on a nearest-neighbor assignment rule. With multiple assignment to visual words [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF], several components are set to one, while soft assignment [START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF][START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF][START_REF] Van Gemert | Visual word ambiguity[END_REF] gives different weights to a few components to account for the distances to centroids. Approaches such as local linear coding [START_REF] Wang | Locality-constrained linear coding for image classification[END_REF], the Fisher vector [START_REF] Perronnin | Fisher kernels on visual vocabularies for image categorization[END_REF] or VLAD [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF], also give alternative definitions of φ. Power-law normalization [START_REF] Jégou | On the burstiness of visual elements[END_REF][START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF][START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF] modifies the function ψ by post-processing the aggregated vector.

Remark: The embedding step resembles the coding step as usually considered in the literature [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF], and ( 6) is close to the pooling step [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF]. We use another terminology to avoid confusion, because in our case all the operations applied on a per descriptor basis are included in the embedding stage. In this respect, the function φ already includes part of the pooling, including geometry-based pooling such as a spatial pyramid [START_REF] Lazebnik | Beyond bags of features: spatial pyramid matching for recognizing natural scene categories[END_REF]. Consequently, in this formulation the dimensionality of φ(x) is typically the same as that of the final representation of the set X .

Interferences in match kernels

The set vectorization underpinning (6), by casting a set of descriptor vectors into a single vector, has the advantage of producing a vector representation compatible with linear algebra, SVM and quantization, to mention but a few. However, this procedure gives unequal importance to the original descriptors in the final representation. More precisely, by comparing ψ s (X ) to itself, the contribution of a given vector x to the set similarity ψ s (X ) ⊤ ψ s (X ) is given by φ(x) ⊤ ψ s (X ):

φ(x) ⊤ x ′ ∈X φ(x ′ ) = φ(x) 2 + φ(x) ⊤ x ′ ∈X :x ′ =x φ(x ′ ).
(8) This equation suggests two important properties for φ:

1. The left term φ(x) 2 isolates the matching descriptor, whose contribution strongly (i.e., quadratically) depends on its norm. 2. The right term is the "noise" polluting the contribution of x due to its interaction with the other vectors.

This paper aims at addressing these two problems, both in the design of the embedding function φ (in Section 3) and in that of the aggregation function ψ (in Section 4).

Triangulation embedding

In this section, we introduce the T-embedding function φ △ . It offers several desirable properties motivated by the observations raised by [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF], in particular that the inner product between two unrelated features is almost zero, except when the features are close enough with respect to other features drawn from the same distribution.

Construction

Given a distribution of vectors x on the d-dimensional unit sphere, we consider a set C = {c 1 , . . . , c |C| } i , c i ∈ R d , of |C| representative anchor points. This set is typically learned by k-means and is similar to a visual vocabulary. Yet in our context it is more related to the anchor graph proposed for the purpose of binary encoding [START_REF] Liu | Hashing with graphs[END_REF].

In contrast to most existing works, we focus on the directional information and discard the absolute distances to the anchor points. This strategy can be related to secant manifolds [START_REF] Hegde | A convex approach for learning near-isometric linear embeddings[END_REF]. This is the key to circumvent the "bandwidth issue", i.e., the dependence on absolute distances, which are generally not reliable [7]. As a result, our novel vector representation is implicitly defined by triangulation 3 . This is achieved by considering the set of normalized residual vectors

r j (x) = x -c j x -c j for j = 1 . . . |C|, (9)
which preserves the angular information between x and c j while discarding the absolute magnitude. Figure 1 illustrates this triangulation strategy. We assume that x = c j for all j, which is guaranteed for ℓ 2 -normalized SIFT vectors if c j are obtained by k-means (k-means centroids, as the average of distinct vectors, strictly lie inside the unit ball). The concatenation

R(x) = [r 1 (x) ⊤ , . . . , r |C| (x) ⊤ ] ⊤ is an intermediate D-dimensional representation such that D = |C| × d.
It is redundant and gives too much weight to the main directions. We subsequently whiten the representation [START_REF] Liu | Hashing with graphs[END_REF] (center, rotate and scale based on eigenvalues). More precisely, denoting by Σ the covariance matrix associated with the random variable R(X), our T-embedding is obtained from R(x) as

φ △ (x) = Σ -1/2 (R(x) -R 0 ), (10)
where both R 0 = E X [R(X)] and Σ are empirically measured on a training set. Figure 2 depicts, in the original space, the values associated with each eigenvector, i.e., each component of the output descriptor φ △ (x). By analogy to PCA or Laplacian Eigenmaps [3], the largest eigenvalues are associated with the "low frequencies": the corresponding components vary slowly as a function of the input descriptors. In contrast, eigenvectors associated with small eigenvalues correspond to high frequencies: A small variation of a given input feature has a larger impact on the corresponding output component, as can be seen in Figure 2 where the components are ordered from largest (left) to smallest eigenvalues (right).

As a result, our embedding compares descriptors at different resolutions. This is also the case in prior works like the pyramid match kernel [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF] and the vocabulary tree [START_REF] Nistér | Scalable recognition with a vocabulary tree[END_REF], which implement varying resolutions by using different quantizers. In our case, there is no quantization artifact: the first components reflect the rough positions while the last are more localized. In order to improve the localization of the descriptors, we discard the d first components associated with the largest eigenvalues. This reduces the variance of the cosine similarity between unrelated descriptors, as discussed in Appendix A. The final dimensionality of the embedded descriptor φ △ (x) is therefore D = d × (|C| -1).

Efficient computation with match kernels

We now consider a match kernel inherited from our Tembedding, as introduced in Section 2. Exploiting the linearity in equations ( 6) and ( 10), we compute the explicit set representation of a vector set X comprising n vectors as

ψ(Φ △ (X )) = x∈X φ △ (x) (11) = Σ -1/2 x∈X R(X) -nΣ -1/2 R 0 . ( 12
)
Computing this representation for typical parameters (d = 128, n = 3000, |C| = 16) takes about 20 ms on a quad-core laptop with an efficient Matlab implementation. However, it is worth normalizing φ △ before the aggregation to ensure that φ △ (x) ⊤ φ △ (x) = 1. In particular, this is important for the aggregation technique presented in Section 4. In this case the computation is slower, as each R(x)/ R(x) is projected separately with Σ -1/2 .

Properties

By construction, and apart from singular cases of C, our T-embedding satisfies several desirable properties. First, the function φ △ : R d → R D : x → φ △ (x) is injective. Second, it is continuous everywhere except at the location of the centroids (and as noted above, for a vector distribution on the unit sphere (as SIFT descriptors are) and anchor points learned with k-means, it is continuous everywhere because the centroids are strictly inside the sphere). This property ensures that an infinitesimal change of the input vector does not produce an abrupt change in the output space. Similarly, the embedding function is differentiable everywhere.

Note that VLAD, LLC and the Fisher vector are also injective, but bag-of-words is not. Among these three embedding techniques, only Fisher is continuous.

In addition to these formal mathematical properties, another key characteristic of our embedding, as will be demonstrated next, is that the inner product φ △ (x)|φ △ (y) between two unrelated vectors is close to 0 with high probability. In contrast, when applied to SIFT descriptors, similar patches compared with their embedded descriptors have a similarity much greater than 0.

Quantitative analysis on a patch dataset. We collect empirical statistics of the cosine similarity for related and unrelated image patches. For this purpose, we use the datasets Liberty and Notredame provided by Brown et al. [START_REF] Winder | Learning local image descriptors[END_REF]. Each dataset consist of about 500k patches from multiple images grouped into 150k clusters, where a cluster corresponds to the same physical scene point. These datasets are usually employed for learning patch descriptors [START_REF] Simonyan | Learning local feature descriptors using convex optimisation[END_REF][START_REF] Winder | Learning local image descriptors[END_REF], but here we use them for learning and evaluating embeddings, and simply use RootSIFT [1] as the patch descriptor. Learning (e.g., of Σ for our method) is performed on Liberty for all methods. We test on Notredame by considering 150k pairs of matching descriptors (a pair per cluster) and the same number of pairs for unrelated descriptors (we take two descriptors from two different clusters). Figure 3 shows the cosine similarity for related/unrelated patches for the original descriptors (RootSIFT), and after they are individually mapped with Fisher vector encoding (without aggregation) and our T-embedding (φ △ ).

Both Fisher and T-embedding increase the contrast between unrelated and related descriptors. In this respect, T- embedding is better than Fisher. First, on average the similarity between unrelated patches is closer to 0 with φ △ , and few unrelated pairs deviate from this behavior. Moreover, in Fisher, a large proportion (note the log scale) of correct matches are given a similarity close to 0. This proportion is comparatively much lower in T-embedding.

A high φ △ cosine similarity associated with two local descriptors x and y reliably reflects the confidence that we have in the visual resemblance of the corresponding patches. As a byproduct of this observation, it is possible to determine how close patches are based on their absolute φ △ cosine similarity, as visually illustrated in Figure 4 by detecting similar patterns (bursts [START_REF] Jégou | On the burstiness of visual elements[END_REF]) in a given image. The quality of the similarity measure for descriptors mapped with T-embedding is evaluated with a ROC curve in Appendix A. Supervised learning of patch descriptors [START_REF] Simonyan | Learning local feature descriptors using convex optimisation[END_REF][START_REF] Winder | Learning local image descriptors[END_REF] would further improve the separation in all cases.

Democratic aggregation

Our T-embedding reduces the interferences in (8) by giving a cosine similarity that is almost 0 for unrelated pairs of descriptors, while providing a comparatively higher posi- tive score to the true matches. However, at this stage, the descriptors are still considered independently. In the following, we further limit interferences by explicitly analyzing and reducing them in the aggregation stage.

A match kernel K is defined as democratic if and only if, for any set X s.t. card(X ) = n, the corresponding matrix K satisfies K(X , X )

1 n = C 1 n , (13)
where the scaling factor C may (or not) depend on X . In other words, a democratic kernel ensures that all the vectors in X contribute equally to the set self-similarity. In the rest of this section, we present the optimization problem aiming at producing a democratic kernel from an arbitrary one in the aggregation stage. Then we discuss convergence issues and present a strategy to achieve convergence.

Democratization

A kernel as in (1) is normally not democratic. To achieve this property, we modify it by including additional weights linearly associated with each vector, as

K(X , Y) = x∈X y∈Y λ X (x) λ Y (y) k(x, y). ( 14
)
Each scalar λ X (x) (respectively λ Y (y)) only depends on x and the set X (respectively y and Y). Considering the set X = {x 1 , . . . , x n }, the corresponding weights λ i , i = 1 . . . n, are determined by solving, when possible, the set of equations

∀x i ∈ X , λ i × xj ∈X λ j k(x i , x j ) = C (15)
under the constraint ∀i, λ i > 0. The problem is summarized in matrix form as

ΛKΛ1 n = C1 n , (16)
where Λ = diag(λ) = diag(λ 1 , . . . , λ n ) is a matrix whose diagonal is strictly positive. Note, ( 14) is equivalent to defining a new match kernel k ′ (x, y) = λ X (x) λ Y (y) k(x, y). Consider the particular case of the match kernel "embed+aggregate" introduced in Section 2. Equation ( 14) is re-written as

K(X , Y) = x∈X y∈Y λ X (x) λ Y (y) φ(x) ⊤ φ(y) (17) = x∈X λ X (x)φ(x) ⊤   y∈Y λ Y (y)φ(y)   ,
where it can be seen that the democratization amounts to defining an alternative function ψ, denoted ψ d . More precisely, we replace the aggregation function ψ s in ( 6) by the weighted summation:

ψ d (Φ(X )) = φi∈Φ(X ) λ i φ i . ( 18
)
The weighted vector is ℓ 2 -normalized to produce the normalized match kernel.

Modified Sinkhorn scaling algorithm

It is worth noticing that this problem resembles that of projection to a doubly stochastic matrix [START_REF] Sinkhorn | A relationship between arbitrary positive matrices and double stochastic matrices[END_REF]: It is equivalent if C = 1 and K is positive. Under additional assumptions (matrix K has total support and is fully indecomposable [START_REF] Knight | The Sinkhorn-Knopp algorithm: convergence and applications[END_REF]), the Sinkhorn's algorithm converges to a unique solution satisfying ∀i, λ i > 0. It is a fixed-point algorithm that proceeds by alternately normalizing the rows and columns. We adopt a symmetric variant analyzed by Knight [START_REF] Knight | The Sinkhorn-Knopp algorithm: convergence and applications[END_REF] and weaken the impact of each iteration, as recently suggested [START_REF] Jégou | Accurate image search using the contextual dissimilarity measure[END_REF], by using a power exponent smaller than 0.5 for a smoother convergence.

Appendix B gives pseudo-code for this optimization strategy. Sinkhorn is an algorithm that converges quickly. We stop it after 10 iterations for efficiency reasons. Experimentally, no benefit comes from using more iterations.

General case: convergence issue and a solution

In the case of an arbitrary kernel k(., .), the assumptions required for convergence with Sinkhorn are generally not satisfied (Matrix K nonnegative and fully indecomposable [START_REF] Knight | The Sinkhorn-Knopp algorithm: convergence and applications[END_REF]). Thus, a positive solution does not necessarily exist. Any optimization algorithm may produce negative weights for kernels with negative values, which typically happen if j k(x i , x j ) < 0. This is not desirable because it means that the weight computation is sensitive to new/deleted vectors in the set. We solve this problem by adopting the following pre-processing step.

Enforcing positivity. After ℓ 2 -normalizing φ △ (x) so that the energy is identical for all vectors, we solve the convergence issue by setting all negative values to 0 in K. The weights computed with this new matrix K + are positive with Sinkhorn's algorithm because all rows/columns sums are positive. The resulting embedding ψ d is not strictly a democratic kernel but tends towards more "democracy".

Discussion

Consider the right term in [START_REF] Grauman | The pyramid match kernel: Discriminative classification with sets of image features[END_REF]. If the embedding perfectly removes it (no interaction between the descriptors of the same set), then our democratization is a calibration such that all the norms φ(x) are equal. Appendix C also shows that our strategy is equivalent to the square-root componentwise normalization in the case of bag-of-visual-words vectors without inverse document frequency weighting.

Experiments

This section presents results for our democratic kernel. The novel ingredients that form our method, namely Tembedding and democratic aggregation, can be used separately. Therefore we evaluate their impact separately, by performing experiments (a) with T-embedding only; (b) with democratic aggregation applied to Fisher embedding; (c) with our two methods. Throughout this section, we only use the normalized kernel K ⋆ , meaning that the image vector is normalized to have unit Euclidean norm.

Datasets and evaluation protocol

We adopt public datasets and corresponding evaluation protocols that are often used in the context of large scale image search. All the learning stages, i.e., k-means clustering and learning the projection for our T-embedding, are performed off-line using a distinct image collection, that does not contain the indexed database nor the query images.

Oxford5k [START_REF] Philbin | Object retrieval with large vocabularies and fast spatial matching[END_REF] consists of 5062 images of buildings and 55 query images corresponding to 11 distinct buildings in Oxford. The search quality is measured by the mean average precision (mAP) computed over the 55 queries. Images are annotated as either relevant, not relevant, or junk, which indicates that it is unclear whether a user would consider the image as relevant or not. Following the recommended protocol, the junk images are removed from the ranking. For the experiments on Oxford5k, all the learning stages are performed on the Paris6k dataset [START_REF] Philbin | Lost in quantization: Improving particular object retrieval in large scale image databases[END_REF]. Oxford105k is the combination of Oxford5k with 100k negative images, in order to evaluate the search quality on a large scale.

INRIA Holidays [START_REF] Jégou | Improving bag-offeatures for large scale image search[END_REF]. This dataset includes 1491 photos of different locations and objects, 500 of them being used as queries. The search quality is measured by mAP, with the query removed from the ranked list. To obtain the vocabulary, we use the independent dataset Flickr60k provided with Holidays. For Holidays and Oxford5k, we perform the experiments three times for our methods (for three distinct vocabularies) and report the mean performance.

Implementation notes

Local descriptors are extracted with the Hessian-affine detector [START_REF] Mikolajczyk | Scale and affine invariant interest point detectors[END_REF] and described by SIFT [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF]. We have used the same descriptors as provided in a previous paper [2]. We use the RootSIFT variant [1], in all our experiments.

Power-law normalization. Images contain "visual bursts" [START_REF] Jégou | On the burstiness of visual elements[END_REF], meaning that numerous descriptors are almost identical within the same image, as observed in Figure 4. These descriptors tend to dominate the similarity even in democratic kernels. As a common post-processing step [START_REF] Jégou | On the burstiness of visual elements[END_REF][START_REF] Perronnin | Improving the Fisher kernel for large-scale image classification[END_REF], we apply power-law normalization on the vector image representation, and subsequently ℓ 2 -normalize it. This processing is parametrized by a constant α that controls the value of the exponent when modifying a component a such that a := |a| α sign(a). We standardly set α = 0.5 to ensure a fair comparison between the methods. Note that this section also includes a specific analysis for this parameter.

Rotation and Normalization (RN).

The power-law normalization suppresses visual bursts, but not the frequent co-occurrences that also corrupt the similarity measure [6]. In VLAD, this problem is addressed [START_REF] Jégou | Negative evidences and cooccurences in image retrieval: The benefit of PCA and whitening[END_REF] by whitening the vectors. However, the whitening learning stage requires a lot of input data and the smallest eigenvalues generate artifacts. This makes such processing suitable only when producing very short representations. As an alternative [START_REF] Safadi | Descriptor optimization for multimedia indexing and retrieval[END_REF], we apply power-normalization after rotating the data with a PCA rotation matrix learned on image vectors (from the learning set), i.e. no whitening. This produces a similar effect to that of whitening, but is more stable and not dependent on PCA eigenvalues. To avoid the full eigendecomposition and the need to use too many images for the learning stage, we compute the first 1000 eigenvectors and apply Gram-Schmid orthogonalization on the reminder of the space (orthogonal complement to these first eigenvectors) to produce a complete basis. After this rotation, we apply the regular power-law normalization, which then jointly addresses the bursts and co-occurrences by selecting a basis capturing both phenomenons on the first components.

Impact of the methods and parameters

Our methods introduce no extra parameter compared with existing techniques, apart from constants with no impact on performance, like the number of iterations in Sinkhorn. The main parameters are the vocabulary size |C| and the parameter α associated with power-law normalization. The analysis of these parameters is shown in Figure 5 for Holidays. The analysis for Oxford5k is in Appendix D (supplementary material). The conclusions drawn are identical on both datasets. To complement these curves, Table 1 shows the impact of our methods step by step for a fixed vocabulary size on Oxford5k, Oxford105k and Holidays. Vocabulary size. For all representations, including Tembedding and democratic aggregation, the performance is an increasing function of the vocabulary size. For reference, we give the performance of the improved Fisher baseline. Note the large gain provided by our embedding for a fixed vocabulary size. Our aggregation method gives a complementary gain. The improvement tends to be smaller for larger vocabularies: This is expected, as for larger vocabularies the interaction between the descriptors is less important than for small ones. For |C| > 128, the benefit of democratic aggregation is not worth the computational overhead.

Our aggregation strategy gives a significant boost in performance with φ △ . As to be expected, it improves the performance when no power-law is applied. Moreover, the analysis of the parameter α also reveals that our aggregation method ψ d is complementary to the power-law normalization, as both methods improves the score.

Power-law normalization and RN. Power-law normalization is less important with our methods (the right curves φ △ + ψ s and φ △ + ψ d are more flat), except if we employ RN: This normalization gives a large improvement in performance when used with the (standard) parameter α = 0.5.

Dimensionality reduction.

In order to get shorter representations, we keep the first D ′ components, after RN normalization, of the vector produced by our embeddings. Table 1 reports the performance for short vectors of varying dimensionality, D ′ = 128 to 1024. Despite a drop in performance due to dimensionality reduction, our best configuration (φ △ +ψ d +RN) still outperforms the 5120-dimensional Fisher vector with D ′ = 512.

Comparison with the state of the art

Baselines. We consider as baselines recent works targeting the same application scenario and similar representations, i.e., that represent an image by a vector that may be subsequently reduced [START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF]. We compare with works recently published on similar mid-size vector representations [2,[START_REF] Jégou | Aggregating local descriptors into compact codes[END_REF].

We also compare with our re-implemented (improved) version of VLAD and Fisher vectors that integrates RootSIFT. This baseline, by itself, approaches or outperforms the state of the art by combining most of the effective ingredients.

Results. Table 2 shows that our method outperforms the compared methods by a large margin on all datasets. The gain over a recent paper [2] using a larger vocabulary is +11.8% in mAP on both Holidays and Oxford5k. Compared with our improved Fisher baseline using the same vocabulary size, the gain is +13.2% in mAP for Holidays, +16.9% for Oxford5k and +16.2% for Oxford105k. Even when reducing the dimensionality to D ′ = 1, 024 components, we outperform all other methods by a large margin, with a much smaller vector representation. Only when reducing the vector to D ′ = 128 components, our method gives on average slightly lower results than those reported by Arandjelović and Zisserman [2].

Conclusion

The key motivation for this paper is to reduce the interference between local descriptors when combining them to produce a vector representation of an image. It is addressed by two novel and complementary methods. The first is a T-embedding that reduces the impact of unrelated matches on the image similarity. The second method explicitly limits the interference between descriptors when aggregating them. The resulting representation compares favorably with state-of-the-art encoding methods for image search, such as the Fisher kernel, even when our representation is reduced to 1,000 components.

Abstract

The appendices provided in this supplemental material complement our paper in several aspects. We provide additional experiments, results and interpretations. We give pseudo-code of our democratization strategy and show how the democratic kernel relates to square-rooting normalization (powerlaw with α = 0.5) in the case of bag-ofwords vectors without inverse document frequency terms. Then, we report additional results, in particular on the UKB benchmark and Holidays merged with 1 million images. Finally, we provide complexity measurements.

Appendix A -ROC curves and discussion

Figure 1 gives the receiver operating curves associated with Fisher and T-embedding. We consider the same setup as in recent papers for evaluation of learned local descriptors [7], which is also used in Section 3.3. We learn on Liberty and test on NotreDame. The baseline is RootSIFT. Here, we use this framework to evaluate the impact of the encoding technique on the hypothesis test. More precisely we compare local descriptors individually encoded by the Fisher vector (mean components, no power-law componentwise normalization) and our encoding technique φ △ . We also evaluate our strategy without removing the low frequency terms.

The first observation is that the Fisher vector is not as good as RootSIFT with respect to the hypothesis test, i.e., when vectors are compared individually with cosine similarity. Observe, also, that the benefit of T-embedding is especially significant for low false positive rates, which explains why T-embedding is more suitable than RootSIFT to detect visual bursts based on a high similarity threshold. Despite its relative poor performance on these curves, recall that the Fisher vector offers better performance than Root-SIFT once aggregated with a sum. This leads us to the following interpretation: the main benefit of these embedding functions is not the underlying quality of the comparison metric (although this also mat- ters), but mainly the fact that they limit the interferences between descriptors once aggregated, thanks to the mapping to a higher dimensional space. This is also supported by the comparison of T-embedding before and after removing the first components. While the ROC curve of T-embedding is better when keeping the low frequencies (and better than RootSIFT), the recognition performance for image search is better when we remove them.

Impact of removing the components associated with low frequencies. The previous interpretation is consistent with the fact that, before removing the low frequencies in our T-embedding, the variance of the cosine similarity for unrelated descriptors is comparable to that of RootSIFT after PCA. In this case, there is a lot of interferences between the aggregated descriptors.

After removing these components, the distribution of cosine similarities, for unrelated descriptors, is more comparable to that obtained with high-dimensional vectors distributed on the unit hypersphere: It is Gaussian-like with a small variance. These remarks are illustrated by Figure 2, which shows how the distributions of related and unrelated patches evolve when removing a varying number of components: 0 (=none removed), 64, 128, 192 and 256. Observe that our removal strategy has a dramatic impact of the distributions of cosine similarities, in particular for the first d components, where d is the input (SIFT) dimensionality.

The strategy has also an effect on the true matches: the corresponding similarities decrease when removing components. Even though a significant proportion of the matches remain associated with strong similarities, the hypothesis test on individual descriptors is weakened. Our strategy therefore aims at optimizing a trade-off between

• reducing the interferences in the match kernel

• and keeping the hypothesis test as good as possible.

By removing more than d=128 components, the benefit of variance reduction is less significant for unrelated patches: compare the Figures associated with 128 and 256 removed components, which have comparable shapes for unrelated matches. In contrast, the similarity of true matches continue to suffer. In particular, more patches have a similarity close to 0. These observations are consistent with our preliminary experiments, where the optimal performance, with respect to search accuracy, is approximately obtained when removing d components.

As a final remark, recall that the embeddings we consider are learned in an unsupervised manner: The ROC curves would be certainly improved by using metric learning techniques such as those proposed for descriptor learning [6]. However, as discussed in this section, the ROC performance is not directly related to the image search performance because of the interferences. This shows the limit of the ROC evaluation setup in the context of match kernels.

Figure 1 .

 1 Figure 1. Illustration of our T-embedding for d = 2 and |C| = 4. (a) Distribution and learned anchor points. (b) Residual vectors associated with a given vector x; (c) Normalized residuals R(x).

Figure 2 .

 2 Figure 2. Pictorial representation of the function φ △ for the same example as in Figure 1. The 8 components of φ △ (x), where the spatial position in each map indicates the 2-D input vector x, while the magnitude represents the output value (red=negative, blue=positive, white=0) of a given component of φ △ . The components associated with the two largest eigenvalues (on the left) are smoothly varying, and are discarded in the final representation. Observe the locality conveyed by the other components.

Figure 3 .

 3 Figure 3. Histogram of the cosine similarity between related (plain) and unrelated (dashed) patches, for RootSIFT descriptors (top), embedded with Fisher kernel (middle, |C| = 16) and our Tembedding (bottom, |C| = 16). The count is shown in log-scale.

Figure 4 .

 4 Figure 4. Detection of self-similar structures by thresholding the cosine similarity between embedded descriptors. To produce it, we have simply thresholded the gram matrix K (with threshold 0.5) between descriptors mapped with φ △ , and performed connected component analysis of the associated graph. We display the five largest components (one color for each).

Figure 5 .

 5 Figure 5. Impact of the parameters on the Holidays' performance for different image vector representations: VLAD, Fisher, our Tembedding φ △ with sum aggregation ψs, and democratic aggregation ψ d (without and with RN). Left: as a function of vocabulary size |C|; Right: as a function of the power-law normalization exponent α. Note, α = 0 amounts to binarizing the vector.

Figure 1 .

 1 Figure 1. ROC curves: comparison of RootSIFT, Fisher (applied on RootSIFT, k=16), and T-embedding (k=16) before (D=2048) and after (D=1920) removing the first D components associated with the low frequencies.

Table 1 .

 1 Impact of our methods on the performance. First we evaluate the Fisher and combine it with democratic aggregation. Then we consider T-embedding φ △ with sum (ψs) and democratic (ψ d ) aggregation, and show the boost given by RN. Finally, we present results after dimensionality reduction to short vectors. |C| = 64.

		dim. red.		mAP
	method ↓	to → D ′	Holidays Oxford5k Ox105k
	Fisher baseline	-	63.9	50.7	44.9
	Fisher + ψ d	-	63.8	52.0	45.9
	φ △ + ψs	-	70.4 ±0.3 58.9 ±0.3	52.3
	φ △ + ψ d	-	72.2 ±0.2 61.2 ±0.4	55.9
	φ △ + ψs + RN	-	74.5 ±0.4 63.3 ±0.9	55.5
	φ △ + ψ d + RN	-	77.1 ±0.7 67.6 ±0.2	61.1
	φ △ + ψ d + RN → 1,024 72.0 ±0.2 56.2 ±0.1	50.2
	φ △ + ψ d + RN → 512	70.0 ±0.6 52.8 ±0.4	46.1
	φ △ + ψ d + RN → 256	65.7 ±0.3 47.2 ±0.2	40.8
	φ △ + ψ d + RN → 128	61.5 ±0.7 40.0 ±0.1	33.9

Table 2 .

 2 Comparison with the state of the art for short and intermediate vector dimensionality on Holidays, Oxford5k and Ox-ford105k datasets. The two last rows show the performance after reducing our vector from 8,064 to 1,024 or 128 components.

		|C|	D	mAP
	method ↓		Hol. Ox5k Ox105k
	BOW [13]	20k	20,000 43.7	35.4	-
	BOW [13]	200k	200,000 54.0	36.4	-
	VLAD [13]	64	4,096 55.6	37.8	-
	Fisher [13]	64	4,096 59.5	41.8	-
	VLAD-intra [2] 256	32,536 65.3	55.8	-
	VLAD-intra [2] 256	→ 128 62.5	44.8	37.4
			Our methods
	φ △ + ψs + RN	16	1,920 69.5	53.1	45.6
	φ △ + ψs + RN	64	8,064 74.5	63.3	55.5
	φ △ + ψ d + RN	16	1,920 72.3	57.1	49.5
	φ △ + ψ d + RN	64	8,064 77.1	67.6	61.1
	φ △ + ψ d + RN	16	→ 128 61.7	43.3	35.3
	φ △ + ψ d + RN	64 → 1,024 72.0	56.0	50.2

http://tinyurl.com/democratic-kernel

Triangulation only relies on angles to determine the position of a point, in contrast to trilateration that finds point locations by measuring distances.

Acknowledgments. This work was done within the Project Fire-ID, supported by the ANR French research agency, and also supported by ERC grant VisRec no. 228180. We warmly thank Karen Simonyan for providing features and Miaojing Shi for the complementary results on UKB and Holidays+Flickr1M in Appendix E. We also thank Florent Perronnin and Naila Murray for preliminary discussions, and encourage reading their related paper [20] on generalized max pooling.

Appendix B -Modified Sinkhorn: Pseudo-code

The algorithm below gives pseudo-code for our democratization strategy, solved by a symmetric variant of the Sinkhorn scaling algorithm. We set γ = 0.3, typically. Note however that using a value lower than γ = 0.5 (like in the regular Knight variant) is critical only if we re-compute the kernel matrix from the weighted descriptors at each iteration of the Sinkhorn algorithm.

Input:

Gram matrix K % of size n × n parameters γ and n iter Output:

Weight vector λ Initialization: λ = 1 n For i=1 to n iter σ = diag(λ) × K × diag(λ) × 1 n % Sums of rows ∀i, λ i := λ i /σ γ i % Update

Note, we provide a package associated with paper, which includes a Matlab implementation of this algorithm: http://tinyurl.com/democratic-kernel. Appendix C -Bag-of-visual-words: Link between democratization with square-root normalization

In this section, we discuss the particular case of our method when applied to the bag-of-word representation with cosine similarity. We do not consider inversedocument-frequency terms. In this case, φ BOW is defined by φ BOW (x) = [0, . . . , 0, 1, 0, . . . , 0] ⊤ .

(1)

These mapped vectors are summed up to produce the bag-of-visual-words vector

where m j (X ) is the number of descriptors assigned to visual word j in X .

The match kernel matrix K BOW (X , X ) is, up to a permutation (to assume that the vectors are ordered by increasing visual word indices), block diagonal with only 1 in the blocks:

This matrix is positive, which means that the strategy to enforce only positive values has no effect. Similarly, the mapped vectors are already normalized to unit norm. A trivial solution to

is such that

for a vector assigned to visual word j such that m j = 0.

The resulting vector

is a democratic kernel that plainly satisfies the "democratic" condition of Equation 4. Interestingly, it is the same vector as the one obtained by applying square-root componentwise normalization [3,5], which significantly improves bag-of-words performance.

Consider now the symmetric version of the Sinkhorn algorithm (Algorithm 1), where we set γ = 0.5. The first iteration computes the sum of each row. If the i th vector is assigned to the visual word j, then the sum is m j and λ i = 1/ √ m j . In other terms, the algorithm reaches the fixed-point in a single iteration. For other values of γ < 0.5, the algorithm also converges to this fixed point.

Appendix D -Parameter and method evaluation

We complement the parameter study of Section 5.3 by providing the same experiments performed on the Oxford5k dataset. We also include the variant method φ △ + ψ s + RN in the plot. The results are shown in Figure 3 for the vocabulary size |C| and in Figure 4 for the exponent α involved in power-law normalization.

The conclusions drawn in our main paper are identical for both datasets: • The performance grows as a function of the vocabulary size for all methods, apart from |C| = 128 with the best variant. For this last point, a possible explanation is that the number of learning images (10k for Holidays, the 6k images from Paris for Oxford105k) is no large enough to accurately learn the rotation matrix. • Our democratic aggregation strategy is complementary with power-law normalization, and improves upon our embedding; • RN is worth applying and combining with power-law normalization in most cases. • When using RN, the best performance is noticeably attained for α = 0.5. 1. Performance of different combinations. For all the methods, we report the average over 3 distinct vocabularies, which are the same for all the methods. We set α = 0.5.

|C|

Appendix E -Performance on UKB and Holi-days+Flickr1M

The performance of our best method, namely our Tembedding associated with Sinkhorn democratization, is presented in Table 2 for two additional datasets, namely

Appendix F -Complexity analysis

Table 3 reports the timings measured to compute our representations for different vocabulary sizes k c . The measures are obtained on the query images of Oxford5k. The measurements are carried out on a Xeon E5-2650/2.00GHz (32 cores). We report the CPU times (larger than elapsed ones because CPU time cumulates all active threads). On a quad-core laptop with multi-threading, the timing is typically 20ms per image for φ △ + ψ s .

The computation of φ △ is fast. The bottleneck is democratic aggregation, when adopted. This is partially due to the low degree of optimization: Democratic aggregation is done in plain Matlab, while we have optimized the computation of φ △ with a mex file. This also suggests that further optimization strategies should be considered for larger vocabularies. A simple effective one is to threshold the gram matrix by setting to 0 all values below a threshold (typically, 0.1), to get it sparse at a small accuracy cost.


1 • • p α k k ✇❤❡r❡ p 1 = 2, p 2 = 3 ❡t❝ ✳ ✳ ✳ ❋♦r s ∈ C✱ ✇❡ ❝♦♥s✐❞❡r z = (z 1 , z 2 , . . . ) = (p -s 1 , p -s 2 , . . . )✳ ❚❤❡♥✱ ✇r✐t✐♥❣ f (s) = +∞ n=1 a n n -s ✭✶✮ ✇❡ ❣❡t f (s) = +∞ n=1 a n (p -s 1 ) α1 • • (p -s k ) α k = +∞ n=1 a n z α1 1 • • z α k k . ❙♦ ✇❡ ❝❛♥ s❡❡ ❛ ❉✐r✐❝❤•❡t s❡r✐❡s ❛s ❛ ❋♦✉r✐❡r s❡r✐❡s ♦♥ t❤❡ ✐♥✜♥✐t❡✲❞✐♠❡♥s✐♦♥❛• ♣♦•②t♦r✉s T ∞ = {(z 1 , z 2 , • • • ), |z i | = 1, ∀i ≥ 1}✳ ❲❡ s❤❛•• ❞❡♥♦t❡ t❤✐s ❋♦✉r✐❡r s❡r✐❡s D(f )✳ ▲❡t ✉s ✜① ♥♦✇ p ≥ 1✳ ❚❤❡ s♣❛❝❡ H p (T ∞ ) ✐s t❤❡ ❝•♦s✉r❡ ♦❢ t❤❡ s❡t ♦❢ ❛♥❛•②t✐❝ ♣♦•②♥♦♠✐❛•s ✇✐t❤ r❡s♣❡❝t t♦ t❤❡ ♥♦r♠ ♦❢ L p (T ∞ , m) ✇❤❡r❡ m ✐s t❤❡ ♥♦r♠❛•✲ ✐③❡❞ ▲❡❜❡s❣✉❡ ♠❡❛s✉r❡ ♦♥ T ∞ ✳ ▲❡t f ❜❡ ❛ ❉✐r✐❝❤•❡t ♣♦•②♥♦♠✐❛•✱ D(f ) ✐s t❤❡♥ ❛♥ ❛♥❛•②t✐❝ ♣♦•②♥♦♠✐❛• ♦♥ T ∞ ❜② t❤❡ ❇♦❤r✬s ♣♦✐♥t ♦❢ ✈✐❡✇✳ ❇② ❞❡✜♥✐t✐♦♥✱ f H p := D(f ) H p (T ∞ ) ❛♥❞ H p ✐s t❤❡ ❝•♦s✉r❡ ♦❢ t❤❡ s❡t ♦❢ ❉✐r✐❝❤•❡t ♣♦•②♥♦♠✐✲ ❛•s ✇✐t❤ r❡s♣❡❝t t♦ t❤✐s ♥♦r♠✳ ❚❤❡ s♣❛❝❡s H p ❛♥❞ H p (T ∞ ) ❛r❡ t❤❡♥ ✐s♦♠❡tr✐❝❛••② ✐s♦♠♦r♣❤✐❝✳ ❲❡ r❡❝❛•• ♥♦✇ ❤♦✇ ✇❡ ❝❛♥ ❞❡✜♥❡ t❤❡ ✇❡✐❣❤t❡❞ ❇❡r❣♠❛♥ s♣❛❝❡s ♦❢ ❉✐r✐❝❤•❡t s❡r✐❡s✳ ❋♦r σ > 0✱ f σ ✇✐•• ❜❡ t❤❡ tr❛♥s•❛t❡ ♦❢ f ❜② σ✱ ✐✳❡✳ f σ (s) := f (σ + s)✳ ❲❡ s❤❛•• ❞❡♥♦t❡ ❜② P t❤❡ s❡t ♦❢ ❉✐r✐❝❤•❡t ♣♦•②♥♦♠✐❛•s✳ ▲❡t p ≥ 1✱ P ∈ P ❛♥❞ µ ❜❡ ❛ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ♦♥ (0, +∞) s✉❝❤ t❤❛t 0 ∈ Supp(µ)✳ ❚❤❡♥ P A p µ := +∞ 0 P σ p H p dµ(σ) 1/p • ✶ A p µ ✐s t❤❡ ❝♦♠♣•❡t✐♦♥ ♦❢ P ✇✐t❤ r❡s♣❡❝t t♦ t❤✐s ♥♦r♠✳ ❲❤❡♥ dµ(σ) = 2e -2σ dσ✱ t❤❡s❡ s♣❛❝❡s ❛r❡ s✐♠♣•② ❞❡♥♦t❡❞ ❜② A p ✳ ■t ✐s s❤♦✇♥ ✐♥ ❬✷( t❤❛t t❤❡② ❛r❡ s♣❛❝❡s ♦❢ ❝♦♥✈❡r❣❡♥t ❉✐r✐❝❤•❡t s❡r✐❡s ♦♥ C 1/2 ✳ ■♥ ❬✼(✱ t❤❡ ❜♦✉♥❞❡❞ ❝♦♠♣♦s✐t✐♦♥ ♦♣❡r❛t♦rs ♦♥ H 2 ✱ ✐♥ ♦t❤❡r ✇♦r❞s t❤❡ ❛♥❛•②t✐❝ ❢✉♥❝t✐♦♥s Φ : C 1 2 → C 1 2 s✉❝❤ t❤❛t ❢♦r ❛♥② f ∈ H 2 ✱ f • Φ ∈ H 2 ✱ ❛r❡ ❝❤❛r❛❝t❡r✐③❡❞✳ ■♥ ❬✸(✱ ❋✳ ❇❛②❛rt ❣❡♥❡r❛•✐③❡❞ t❤✐s r❡s✉•t t♦ t❤❡ s♣❛❝❡ H p ✇❤❡♥ p ≥ 1✳ ❲❡ ❞❡♥♦t❡ ❜② D t❤❡ s❡t ♦❢ ❢✉♥❝t✐♦♥s f ✇❤✐❝❤ ❛❞♠✐t ❛ r❡♣r❡s❡♥t❛t✐♦♥ ❜② ❛ ❝♦♥✈❡r❣❡♥t ❉✐r✐❝❤•❡t s❡r✐❡s ✐♥ s♦♠❡ ❤❛•❢✲♣•❛♥❡ ❛♥❞ ❢♦r θ ∈ R✱ C θ ✇✐•• ❜❡ t❤❡ ❢♦••♦✇✐♥❣ ❤❛•❢✲♣•❛♥❡ {s ∈ C, ℜ(s) > θ}✳ ❲❡ s❤❛•• ❞❡♥♦t❡ C + ✐♥st❡❛❞ ♦❢ C 0 ✳ ❖♥ t❤❡ s♣❛❝❡s A p µ ✱ t❤❡ ❢♦••♦✇✐♥❣ t❤❡♦r❡♠s ❤❛✈❡ ❜❡❡♥ ♣r♦✈❡❞ ✐♥ ❬✶(✿ ❚❤❡♦r❡♠ ✶ ✭❬✶(✱❚❤✶✮✳ ▲❡t Φ : C 1 2 → C 1 2 ❜❡ ❛♥ ❛♥❛•②t✐❝ ❢✉♥❝t✐♦♥ ♦❢ t❤❡ ❢♦r♠ Φ(s) = c 0 s + ϕ(s) ✇❤❡r❡ c 0 ≥ 1 ❛♥❞ ϕ ∈ D✳ ❚❤❡♥ C Φ ✐s ❜♦✉♥❞❡❞ ♦♥ A p µ ✐❢ ❛♥❞ ♦♥•② ✐❢ ϕ ❝♦♥✈❡r❣❡s ✉♥✐❢♦r♠•② ✐♥ C ε ❢♦r ❡✈❡r② ε > 0 ❛♥❞ ϕ(C + ) ⊂ C + ✳ ▼♦r❡♦✈❡r ✐♥ t❤✐s ❝❛s❡✱ C Φ ✐s ❛ ❝♦♥tr❛❝t✐♦♥✳ ❚❤❡♦r❡♠ ✷ ✭❬✶(✱❚❤✷✮✳ ▲❡t Φ : C 1 2 → C 1 2 ❜❡ ✐♥ D✳ ❚❤❡♥ ✭✐✮ ■❢ C Φ ✐s ❜♦✉♥❞❡❞ ♦♥ A p µ t❤❡♥ Φ ❝♦♥✈❡r❣❡s ✉♥✐❢♦r♠•② ✐♥ C ε ❢♦r ❡✈❡r② ε > 0 ❛♥❞ Φ(C + ) ⊂ C 1/2 ✳ ✭✐✐✮ ■❢ Φ ❝♦♥✈❡r❣❡s ✉♥✐❢♦r♠•② ✐♥ C ε ❢♦r ❡✈❡r② ε > 0 ❛♥❞ Φ(C + ) ⊂ C 1/2+η ✇✐t❤ s♦♠❡ η > 0 t❤❡♥ C Φ ✐s ❜♦✉♥❞❡❞ ♦♥ A 2 µ ✳ ■♥ t❤❡ s❡q✉❡•✱ ✇❡ ❛ss✉♠❡ t❤❛t µ ✐s ❛ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ♦♥ (0, +∞) s✉❝❤ t❤❛t dµ(σ) = h(σ)dσ ✇❤❡r❡ h ✐s ❛ ♣♦s✐t✐✈❡ ❝♦♥t✐♥✉♦✉s ❢✉♥❝t✐♦♥✳ ❊①❛♠♣•❡✳ ▲❡t α > -1✱ ✇❡ ❞❡♥♦t❡ µ α t❤❡ ♣r♦❜❛❜✐•✐t② ♠❡❛s✉r❡ ❞❡✜♥❡❞ ♦♥ (0, +∞) ❜② dµ α (σ) = 2 α+1 Γ(α + 1)
σ α e -2σ dσ.

❲❡ ❞❡♥♦t❡ t❤❡ ❝♦rr❡s♣♦♥❞✐♥❣ s♣❛❝❡ A p α ✐♥st❡❛❞ ♦❢ A p µα ✳ ▼❛✐♥ ❚❤❡♦r❡♠✳ ▲❡t 1 ≤ p < +∞ ❛♥❞ C Φ ❜❡ ❛ ❜♦✉♥❞❡❞ ❝♦♠♣♦s✐t✐♦♥ ♦♣❡r❛t♦r ♦♥ A p µ ✳ ❚❤❡ ❢♦••♦✇✐♥❣ ❛ss❡rt✐♦♥s ❛r❡ ❡q✉✐✈❛•❡♥t✿ ✭✐✮ C Φ ✐s ✐♥✈❡rs✐❜•❡✳ ✭✐✐✮ C Φ ✐s ❋r❡❞❤♦•♠✳ ✭✐✐✐✮ C Φ ✐s ❛♥ ✐s♦♠❡tr②✳ ✭✐✈✮ Φ ✐s ❛ ✈❡rt✐❝❛• tr❛♥s•❛t✐♦♥✿ t❤❡r❡ ❡①✐sts τ ∈ R s✉❝❤ t❤❛t ❢♦r ❡✈❡r② s ∈ C + ✱ Φ(s) = s + iτ ✳ ❲❡ ♣♦✐♥t ♦✉t t❤❛t t❤❡ r❡s✉•t ✐s ❢❛•s❡ ♦♥ t❤❡ s♣❛❝❡s H p ✿ ❋✳ ❇❛②❛rt ♣r♦✈❡❞ t❤❛t (i), (ii), (iii) ❛r❡ st✐•• ❡q✉✐✈❛•❡♥t ♦♥ H p ❜✉t ♦❜t❛✐♥❡❞ ❛ ❞✐✛❡r❡♥t ❝❤❛r❛❝t❡r✐③❛t✐♦♥ ❢♦r t❤❡ ✐s♦♠❡tr✐❝ ❝♦♠♣♦s✐t✐♦♥ ♦♣❡r❛t♦rs ♦♥ H p ✭s❡❡ ❬✸(✮✳ ❋♦r ❡①❛♠♣•❡✱ ✐❢ Φ ✐s ❞❡✜♥❡❞ ❢♦r ❡✈❡r② s ∈ C + ❜② Φ(s) = c 0 s ✇✐t❤ c 0 ≥ 2✱ t❤❡♥ C Φ ✐s ❛♥ ✐s♦♠❡tr② ♦♥ H p ❜✉t ♥♦t ♦♥ A p µ ✳ ❚❤❡ s❛♠❡ ♣❤❡♥♦♠❡♥♦♥ ❛♣♣❡❛rs ✐♥ t❤❡ ❢r❛♠❡✇♦r❦ ♦❢ ❝♦♠♣♦s✐t✐♦♥ ♦♣❡r❛t♦rs ♦♥ t❤❡ ✉♥✐t ❞✐s❦ ✭s❡❡ ❬✶✵(✮✳ ■r ♦r❞❡r t♦ ♣r♦✈❡ t❤❡ ♠❛✐♥ t❤❡♦r❡♠✱ ✐t s✉✣❝❡s t♦ s❤♦✇ t❤❛t (ii) ⇒ (iv) ❛♥❞ (iii) ⇒ (iv)✳ ■♥❞❡❡❞✱ (i) ⇒ (ii)✱ (iv) ⇒ (i) ❛♥❞ (iv) ⇒ (iii) ❛r❡ ❝•❡❛r✳ ✷ ✷ ❇❛❝❦❣r♦✉♥❞ ♠❛t❡r✐❛• ▲❡t f ❜❡ ❛ ❉✐r✐❝❤•❡t s❡r✐❡s ♦❢ ❢♦r♠ (1)✳ ❲❡ ❞♦ ♥♦t r❡❝❛•• t❤❡ ❞❡✜♥✐t✐♦♥ ♦❢ ❛❜s❝✐ss❛ ♦❢ s✐♠♣•❡ ✭r❡s♣✳ ❛❜s♦•✉t❡✮ ❝♦♥✈❡r❣❡♥❝❡ ❞❡♥♦t❡❞ ❜② σ c ✭r❡s♣✳ σ a ✮✱ s❡❡ ❬✶✸( ♦r ❬✶✹( ❢♦r ♠♦r❡ ❞❡t❛✐•s✳ ❲❡ s❤❛•• ♥❡❡❞ t❤❡ t✇♦ ♦t❤❡r ❢♦••♦✇✐♥❣ ❛❜s❝✐ss❛s✿ σ u (f ) = inf{a | ❚❤❡ s❡r✐❡s (1) ✐s ✉♥✐❢♦r♠•② ❝♦♥✈❡r❣❡♥t ❢♦r ℜ(s) > a} = ❛❜s❝✐ss❛ ♦❢ ✉♥✐❢♦r♠ ❝♦♥✈❡r❣❡♥❝❡ ♦❢ f. σ b (f ) = inf{a | t❤❡ ❢✉♥❝t✐♦♥ f ❤❛s ❛♥ ❛♥❛•②t✐❝✱ ❜♦✉♥❞❡❞ ❡①t❡♥s✐♦♥ ❢♦r ℜ(s) > a} = ❛❜s❝✐ss❛ ♦❢ ❜♦✉♥❞❡❞♥❡ss ♦❢ f. ■t ✐s ❡❛s② t♦ s❡❡ t❤❛t σ c (f ) ≤ σ u (f ) ≤ σ a (f )✳ ❆♥ ✐♠♣♦rt❛♥t r❡s✉•t ✐s t❤❛t σ u (f ) ❛♥❞ σ b (f ) ❝♦✐♥❝✐❞❡✿ t❤✐s ✐s t❤❡ ❇♦❤r✬s t❤❡♦r❡♠ ✭s❡❡ ❬✺(✮✳ ❚❤✐s r❡s✉•t ✐s r❡❛••② ✉s❡❢✉• ❢♦r t❤❡ st✉❞② ♦❢ H ∞ ✱ t❤❡ ❛•❣❡❜r❛ ♦❢ ❜♦✉♥❞❡❞ ❉✐r✐❝❤•❡t s❡r✐❡s ♦♥ t❤❡ r✐❣❤t ❤❛•❢✲♣•❛♥❡ C + ✭s❡❡ ❬✶✶(✮✳ ❲❡ s❤❛•• ❞❡♥♦t❡ ❜② • ∞ t❤❡ ♥♦r♠ ♦♥ t❤✐s s♣❛❝❡✿ f ∞ := sup ℜ(s)>0 |f (s)|. ❲❡ s❤❛•• ♠❛❦❡ ❛ ❝r✉❝✐❛• ✉s❡ ♦❢ t❤❡ ♣♦✐♥t ❡✈❛•✉❛t✐♦♥ ✐♥ t❤❡ ♣r♦♦❢ ♦❢ t❤❡ ▼❛✐♥ ❚❤❡♦r❡♠✿ ❢♦r ❡✈❡r② p ≥ 1✱ t❤❡ s♣❛❝❡s H p ❛♥❞ A p µ ❛r❡ s♣❛❝❡s ♦❢ ❤♦•♦♠♦r♣❤✐❝ ❢✉♥❝t✐♦♥s ♦♥ C 1/2 ❛♥❞ ♠♦r❡ ♣r❡❝✐s❡•② ✐❢ δ s ✐s t❤❡ ♦♣❡r❛t♦r ♦❢ ♣♦✐♥t ❡✈❛•✉❛t✐♦♥ ❛t s ∈ C 1/2 ✱ t❤❡♥ ❜② ❬✸(✱❚❤✸✿ δ s (H p ) * = ζ(2ℜ(s)) ❛♥❞ ❜② ❬✷(✱❚❤✶ t❤❡ ♣♦✐♥t ❡✈❛•✉❛t✐♦♥ ✐s ❛•s♦ ❜♦✉♥❞❡❞ ♦♥ t❤❡ s♣❛❝❡s A p µ ✳ ▼♦r❡♦✈❡r σ b (f ) ≤ 1/2 ❢♦r ❛♥② f ∈ A p µ ✳ ❋♦r ❡①❛♠♣•❡ ✇❤❡♥ µ = µ α ✱ ✐t ✐s s❤♦✇♥ ✐♥ ❬✷(✱❈♦r✶ t❤❛t t❤❡r❡ ❡①✐sts ❛ ♣♦s✐t✐✈❡ ❝♦♥st❛♥t c α,p s✉❝❤ t❤❛t ❢♦r ❡✈❡r② s ∈ C 1/2 ✱ δ s (A p α ) * ≤ c α,p ℜ(s) 2ℜ(s) -1 2+α p • ❲❤❡♥ p = 2✱ A 2 µ ✐s ❛ ❍✐•❜❡rt s♣❛❝❡ ❛♥❞ ✐t ✐s ❡❛s② t♦ s❡❡ t❤❛t f A 2 µ = +∞ n=1 |a n | 2 w h (n) 1/2 ✇❤❡r❡ ❢♦r ❡✈❡r② n ≥ 1✱ w h (n) = +∞ 0 n -2σ h(σ)dσ. ❚❤❛♥❦s ♦❢ t❤❡ ❜♦✉♥❞❡❞♥❡ss ♦❢ t❤❡ ♣♦✐♥t ❡✈❛•✉❛t✐♦♥ ❛t s ∈ C 1/2 ✱ ✇❡ ❝♦♥s✐❞❡r t❤❡ ❢♦••♦✇✐♥❣ r❡♣r♦❞✉❝✐♥❣ ❦❡r♥❡•s ❞❡✜♥❡❞ ❢♦r ❡✈❡r② w ∈ C 1/2 ❜② K µ (s, w) = +∞ n=1 n -s-w w h (n) • ❋♦r ❡✈❡r② f ∈ A 2 µ ❛♥❞ s ∈ C 1/2 ✱ ♦♥❡ ❤❛s f (s) =< f, K µ (s, • ) > A 2 µ • ✸ ❊①❛♠♣•❡✳ ❖♥ t❤❡ s♣❛❝❡ A 2 α ✱ ✇❡ s✐♠♣•② ❞❡♥♦t❡ (w α n ) t❤❡ ❝♦rr❡s♣♦♥❞✐♥❣ ✇❡✐❣❤t ❛♥❞ t❤❡♥ ❢♦r ❡✈❡r② n ≥ 1✱ w α n = 1 (log(n) + 1) α+1 • ▲❡t Φ : C 1 2 → C 1 2 ❜❡ ❛♥ ❛♥❛•②t✐❝ ❢✉♥❝t✐♦♥ s✉❝❤ t❤❛t Φ(s) = c 0 s + ϕ(s) ✇❤❡r❡ c 0 ✐s ❛ ♥♦♥♥❡❣❛t✐✈❡ ✐♥t❡❣❡r ❛♥❞ ϕ ∈ D✳ ❲❡ s❤❛•• s❛② t❤❛t Φ ✐s ❛ s②♠❜♦• ✐❢ C Φ ✐s ❜♦✉♥❞❡❞ ♦♥ t❤❡ s♣❛❝❡s A p µ ✳ ❋♦r σ > 0✱ ✇❡ ❞❡♥♦t❡ Φ σ t❤❡ tr❛♥s•❛t❡ ♦❢ Φ ❜② σ✿ Φ σ (s) := Φ(σ + s)✳ ❲❤❡♥ c 0 ≥ 1✱ t❤❛♥❦s t♦ t❤❡ ❚❤❡♦r❡♠ 1 ✇❡ ❦♥♦✇ t❤❛t Φ ✐s ❛ s②♠❜♦• ✐❢ ❛♥❞ ♦♥•② ϕ ❝♦♥✈❡r❣❡s ✉♥✐❢♦r♠•② ♦♥ C ε ❢♦r ❡✈❡r② ε > 0 ❛♥❞ ϕ(C + ) ⊂ C + ✳ ■♥ t❤✐s ❝❛s❡✱ ✐t ✐s ❡❛s② t♦ s❡❡ t❤❛t ❢♦r ❡✈❡r② σ > 0✱ Φ σ -σ ✐s ❛•s♦ ❛ s②♠❜♦•✿ ✐♥❞❡❡❞ •❡t σ > 0 ❛♥❞ s ∈ C + ✱ t❤❡♥ ℜ(Φ σ (s) -σ) = ℜ(c 0 (σ + s)) + ℜ(ϕ(σ + s)) -σ > σ(c 0 -1) + ℜ(s) > 0 ❜❡❝❛✉s❡ ϕ(C + ) ⊂ C + ❛♥❞ s ∈ C + ✳ P♦✐♥t ♦✉t t❤❛t t❤✐s r❡s✉•t ❝❛♥ ❜❡ s❡❡♥ ❛s t❤❡ ❙❝❤✇❛r③✬s •❡♠♠❛ ✐♥ t❤✐s ❢r❛♠❡✇♦r❦✳ ✸ Pr♦♦❢ ♦❢ (ii) ⇒ (iv) ❲✐t❤ ❤❡•♣ ♦❢ Pr♦♣♦s✐t✐♦♥ ✹✳✷ ❢r♦♠ ❬✼(✱ ❋✳ ❇❛②❛rt ♣r♦✈❡❞ t❤❡ ❢♦••♦✇✐♥❣ ✉s❡❢✉• •❡♠♠❛✳ ▲❡♠♠❛ ✶ ✭❬✸(✱▲❡♠✶✶✮✳ ▲❡t Φ ❜❡ ❛ s②♠❜♦•✳ ■❢ Φ ✐s ♥♦t ❛ ✈❡rt✐❝❛• tr❛♥s•❛t✐♦♥ t❤❡♥ t❤❡r❡ ❡①✐sts ε ❛♥❞ η > 0 s✉❝❤ t❤❛t Φ(C 1/2-ε ) ⊂ C 1/2+η . Pr♦♦❢ ♦❢ (ii) ⇒ (iv)✳ ❲❡ ❢♦••♦✇ ✐❞❡❛s ❢r♦♠ ❬✸(✱❚❤✶✹✳ ❆ss✉♠❡ t❤❛t Φ ✐s ♥♦t ❛ ✈❡rt✐❝❛• tr❛♥s•❛t✐♦♥✳ ❇② t❤❡ ♣r❡✈✐♦✉s •❡♠♠❛✱ t❤❡r❡ ❡①✐sts ε ❛♥❞ η > 0 s✉❝❤ t❤❛t Φ(C 1/2-ε ) ⊂ C 1/2+η . ❲❡ r❡♠❛r❦ t❤❛t ❡❛❝❤ ❡•❡♠❡♥t ♦❢ ■♠✭C Φ ✮ ✐s ❞❡✜♥❡❞ ❛♥❞ ❜♦✉♥❞❡❞ ♦♥ C 1/2-ε ✿ ✐♥❞❡❡❞ Φ(C 1/2-ε ) ⊂ C 1/2+η ❛♥❞ ✐❢ f ∈ A p µ ✱ f ✐s ❜♦✉♥❞❡❞ ♦♥ C 1/2+η ✭❜❡❝❛✉s❡ σ b (f ) ≤ 1/2✮✳ ◆♦✇ ❜② •❡♠♠❛ ❬✸(✱▲❡♠✾ ✇❡ ❦♥♦✇ t❤❛t t❤❡r❡ ❡①✐sts f ∈ H p s✉❝❤ t❤❛t t❤❡ •✐♥❡ ℜ(s) = 1/2 ✐s ❜♦t❤ ❛❜s❝✐ss❛ ♦❢ ❝♦♥✈❡r❣❡♥❝❡ ❛♥❞ ♥❛t✉r❛• ❜♦✉♥❞❛r② ❢♦r f ✳ ❇❡❝❛✉s❡ ♦❢ t❤❡ ✐♥❝•✉s✐♦♥ H p ⊂ A p µ ✱ f ❜❡•♦♥❣s t♦ A p µ ✳ ❲❡ ❝♦♥s✐❞❡r t❤❡ ❢♦••♦✇✐♥❣ ✐♥✜♥✐t❡ ❞✐♠❡♥s✐♦♥❛• s✉❜s♣❛❝❡ ♦❢ A p µ ✿ F = s♣❛♥{n -s f, n ≥ 1} = f P. ❲❡ s❤❛•• s❤♦✇ t❤❛t F ∩ Im(C Φ ) = {0} ❛♥❞ ❝♦♥s❡q✉❡♥t•② ❈♦❞✐♠✭■♠✭C Φ ✮✮❂+∞ ✇❤✐❝❤ ✐s ❛ ❝♦♥tr❛❞✐❝t✐♦♥ ✇✐t❤ (ii)✳ ▲❡t h ∈ F ∩ Im(C Φ )✱ t❤❡r❡ ❡①✐sts P ∈ P s✉❝❤ t❤❛t h = P f ✳ ■❢ h = 0✱ t❤❡r❡ ❡①✐sts s 0 s✉❝❤ t❤❛t ℜ(s 0 ) = 1/2 ❛♥❞ P (s 0 ) = 0✳ ❇✉t ✐♥ t❤✐s ❝❛s❡✱ f ❡①t❡♥❞s ❜❡②♦♥❞ C 1/2 ❛♥❞ t❤❡♥ ✇❡ ♦❜t❛✐♥ ❛ ❝♦♥tr❛❞✐❝t✐♦♥ ❜❡❝❛✉s❡ t❤❡ •✐♥❡ ℜ(s) = 1/2 ✐s ❛ ♥❛t✉r❛• ❜♦✉♥❞❛r② ❢♦r f ✳ ❋✐♥❛••② F ∩ Im(C Φ ) = {0}✳ ✹ ✹ Pr♦♦❢ ♦❢ (iii) ⇒ (iv) ❋✐rst ✇❡ s❤❛•• s❤♦✇ t❤❛t ✐❢ C Φ ✐s ❛♥ ✐s♦♠❡tr② t❤❡♥ c 0 ≥ 1✳ ❲❡ ♥❡❡❞ t❤❡ ❢♦••♦✇✐♥❣ r❡s✉•t✳ ▲❡♠♠❛ ✷✳ lim ℜ(s)→+∞ δ s (A 1 µ ) * = 1. Pr♦♦❢✳ ▲❡t s ∈ C 1 ✳ ❇② t❤❡ r❡♣r♦❞✉❝✐♥❣ ❦❡r♥❡• ♣r♦♣❡rt② ♦♥ A 2 µ ✭♦r •✉st ❜② ❛ s✐♠♣•❡ ❝♦♠♣✉t❛t✐♦♥✮✱ ❢♦r ❛♥② ❉✐r✐❝❤•❡t ♣♦•②♥♦♠✐❛• ✇❡ ❤❛✈❡ P (s) = +∞ 0 lim T →+∞ 1 2T T -T P (σ + it)K µ (s, σ + it) dtdµ(σ). ◆♦✇ ❜② ❞❡✜♥✐t✐♦♥ ♦❢ t❤❡ ♥♦r♠ ♦❢ ❉✐r✐❝❤•❡t ♣♦•②♥♦♠✐❛•s ✐♥ H 1 ✭s❡❡ ❞❡✜♥✐t✐♦♥ ✶ ❢r♦♠ ❬✸(✮✱ ✇❡ ❤❛✈❡ P A 1 µ = +∞ 0 lim T →+∞ 1 2T T -T |P (σ + it)|dtdµ(σ) • ❈♦♥s❡q✉❡♥t•② |P (s)| ≤ P A 1 µ × K µ (s, • ) ∞ . ◆♦✇ K µ (s, •) ∞ = sup w∈C+ +∞ n=1 n -s+w w h (n) ≤ +∞ n=1 n -ℜ(s) w h (n) ❛♥❞ ✇❡ ♣♦✐♥t ♦✉t t❤❛t w h (1) = 1 s♦ lim sup ℜ(s)→+∞ δ s (A 1 µ ) * ≤ lim ℜ(s)→+∞ +∞ n=1 n -ℜ(s) w h (n) = 1. ❖♥ t❤❡ ♦t❤❡r ❤❛♥❞✱ ✐t ✐s ❝•❡❛r t❤❛t δ s (A 1 µ ) * ≥ 1 ❛♥❞ t❤❡♥ ✇❡ ♦❜t❛✐♥ t❤❡ r❡s✉•t✳ Pr♦♣♦s✐t✐♦♥ ✶✳ ▲❡t Φ ❜❡ ❛ s②♠❜♦•✳ ■❢ C Φ ✐s ❛ ❝♦♥tr❛❝t✐♦♥ t❤❡♥ c 0 ≥ 1✳ Pr♦♦❢✳ ▲❡t s ∈ C 1/2 ✳ ❋♦r ❡✈❡r② f ∈ A p µ ✇❡ ❤❛✈❡ |f • Φ(s)| ≤ δ s (A p µ ) * f • Φ ≤ δ s (A p µ ) * C Φ f ❛♥❞ t❤❡♥ δ Φ(s) (A p µ ) * δ s (A p µ ) * ≤ C Φ . ❇② ✐♥❝•✉s✐♦♥ ♦❢ t❤❡ s♣❛❝❡s A p µ ❛♥❞ t❤❡ ❢❛❝t t❤❛t H p ⊂ A p µ ✇✐t❤ • A p µ ≤ • H p ✇❡ ♦❜t❛✐♥✿ δ Φ(s) (H p ) * δ s (A 1 µ ) * ≤ C Φ . ❇② ❚❤❡♦r❡♠ ✸ ❢r♦♠ ❬✸(✱ ✇❡ ♦❜t❛✐♥ ζ(2ℜ(Φ(s))) 1/p × δ s -1 (A 1 µ ) * ≤ C Φ . ✺ ◆♦✇ ❛ss✉♠❡ c 0 =

  0✱ t❤❡♥ Φ(s) = ϕ(s) = +∞ n=1 c n n -s ❛♥❞ ℜ(c 1 ) > 1/2 ✭s❡❡ ♣r♦♦❢ ♦❢ ▲❡♠♠❛ 3.3 ❢r♦♠ ❬✼(✮✳ ❋✐♥❛••② t❤❛♥❦s t♦ t❤❡ ▲❡♠♠❛ 2✱ ✇❤❡♥ ℜ(s) ❣♦❡s t♦ ✐♥✜♥✐t② ✇❡ ❣❡t C Φ ≥ ζ(2ℜ(c 1 )) 1/p > 1 ❛♥❞ ❝♦♥s❡q✉❡♥t•② C Φ ✐s ♥♦t ❛ ❝♦♥tr❛❝t✐♦♥✳ |❡♠❛r❦✳ ■♥ t❤❡ ♣r❡✈✐♦✉s ▲❡♠♠❛ ✇❡ ❛❝t✉❛••② ✉s❡❞ t❤❛t ❢♦r ❡✈❡r② s ∈ C 1/2 ✱ δ s • C Φ = δ Φ(s) ✳ Pr♦♦❢ ♦❢ (iii) ⇒ (iv)✳ ❆ss✉♠❡ t❤❛t C Φ ✐s ❛♥ ✐s♦♠❡tr②✳ ❇② t❤❡ •❛st •❡♠♠❛✱ c 0 ≥ 1 ❛♥❞ t❤❡♥ ✇❡ ❦♥♦✇ t❤❛t Φ : C + → C + t❤❛♥❦s t♦ t❤❡ ❚❤❡♦r❡♠ 1✳ ❖♥❡ ❤❛s -• p H p -2 -Φ(σ+•) p H p dµ(σ) = 0.

❇✉t 2 -

 2 Φ(σ+•) H p = 2 -σ-(Φ(σ+•)-σ) H p = C Φσ-σ (2 -σ-• ) H p . ❚❤❛♥❦s t♦ t❤❡ ❙❝❤✇❛r③✬s •❡♠♠❛ ✐♥ t❤✐s ❢r❛♠❡✇♦r❦ ✭r❡❝❛•• t❤❛t c 0 ≥ 1✮ ✇❡ ❦♥♦✇ t❤❛t Φ σ -σ : C + → C + ✳ ❙♦ ❜② t❤❡ ❚❤❡♦r❡♠ ✶✱ C Φσ-σ ✐s ❛ ❜♦✉♥❞❡❞ ❝♦♠♣♦s✐t✐♦♥ ♦♣❡r❛t♦r ♦♥ H p ❛♥❞ C Φσ-σ ≤ 1✳ ❚❤❡♥

-Φ(σ+•) H p ≤ 2 -σ-• H p .