Nearest Neighbor Preserving Embeddings

Piotr Indyk MIT

Assaf Naor Microsoft Research

Abstract

In this paper we introduce the notion of nearest neighbor preserving embeddings. These are randomized embeddings between two metric spaces which preserve the (approximate) nearest neighbors. We give two examples of such embeddings, for Euclidean metrics with low “intrinsic” dimension. Combining the embeddings with known data structures yields the best known approximate nearest neighbor data structures for such metrics.

1 Introduction

The nearest neighbor problem is defined as follows: given a set X of points in ℝ^{d}, build a data structure which given any q ∈ ℝ^{d}, quickly reports the point in X that is (approximately) closest to q. This problem, and its approximate versions, are some of the central problems in computational geometry.

Since the late 1990’s, it became apparent that designing efficient approximate nearest neighbor algorithms, at least for high-dimensional data, is closely related to the task of designing low-distortion embeddings. A bi-Lipschitz embedding between two metric spaces (X, d_{X}) and (X′, d′_{X}) is a mapping f : X → X′ such that for some scaling factor C > 0, for every p, q ∈ X we have Cd_{X}(p, q) ≤ d′_{X}(f(p), f(q)) ≤ DCd_{X}(p, q), where the parameter D ≥ 1 called the distortion of f. Of particular importance, in the context of approximate nearest neighbor, are low-distortion embeddings that map X ⊆ ℝ^{d} into ℝ^{k}, where k is much smaller than d. For example, a well-known theorem of Johnson and Lindenstrauss guarantees that for any set X ⊆ ℝ^{d} there is a (1 + ε)-distortion embedding of (X, ∥ · ∥_{2}) into (ℝ^{k}, ∥ · ∥_{2}) for k = O(log |X|/ε^{2}). This embedding and its variants have been utilized e.g., in [20, 26], to give efficient approximate nearest neighbor algorithms in high-dimensional spaces.

More recently (e.g., in [19]), it has been realized that the approximate nearest neighbor problem requires embedding properties that are somewhat different from the above definition. One (obvious) difference is that the embedding must be oblivious, that is, well-defined over the whole space ℝ^{d}, not just the input data points X. This is because, in general, a query point q ∈ ℝ^{d} does not belong to X. The aformentioned Johnson-Lindenstrauss lemma indeed satisfies this (stronger) property. The second difference is that the embedding does not need to preserve all interpoint distances. Instead, it suffices^{1} that the embedding f is randomized, and satisfies the following definition which we introduce:

Definition 1.1. Let (Y, d_{Y}), (Z, d_{Z}) be metric spaces and X ⊆ Y. We say that a distribution over mappings f : Y → Z is a nearest neighbor preserving embedding (or NN-preserving) with distortion D ≥ 1 and probability of correctness^{2} P ∈ [0, 1] if for every c ≥ 1 and any q ∈ Y, with probability at least P, if x ∈ X is such that f(x) is a c-approximate nearest neighbor of f(q) in f(X) (i.e. d(f(q), f(x)) ≤ c · d(f(q), f(X))), then x is a D · c approximate nearest neighbor of q in X.

1If we consider the approximate near neighbor problem, i.e., the decision version of the approximate nearest neighbor, then the constraints that an embedding needs to satisfy are even weaker. Also, it is known [20, 16] that the approximate nearest neighbor can be reduced to its decision version. However, such reductions are non-trivial and introduce certain overhead in the query time and space. Thus, it is beneficial that the embedding preserves the approximate nearest neighbor, not just the near neighbor.

This notion is the appropriate generalization of oblivious embeddings à la Johnson and Lindenstrauss: we want f to be defined on the entire space of possible query points Y, and we require much less than a bi-Lipschitz condition. Clearly, the Johnson-Lindenstrauss theorem is an example of a NN-preserving embedding. Another example of such a mapping is a (weak) dimensionality reduction in ℓ_{1} norm given in [19]. It maps (ℝ^{d}, ∥ · ∥_{1}) into (ℝ^{k}, ∥ · ∥_{1}), where k is much smaller than d, and guarantees that, for any pair of points, the probability that the distance between the pair gets contracted is ”very small”, while the probability of the distance being expanded by a is at most 1/2. It is easy to see that such mapping is a-NN-preserving. At the same time, the standard dimensionality reduction in ℓ_{1} (that preserves all distances) is provably impossible [8, 30]. Thus, the definition of NN-preserving embeddings allows us to overcome the impossibility results for the stronger notion of bi-Lipschitz embeddings, while being sufficient for the purpose of the nearest neighbor and related problems.

In this paper we initiate a systematic study of NN-preserving embeddings into low-dimensional spaces. In particular, we prove that such embeddings exist for the following subsets X of the Euclidean space (ℝ^{d}, ∥ · ∥_{2}):

1. Doubling sets. The doubling constant of X, denoted λ_{X}, is the smallest integer λ such that for any p ∈ X and r > 0, the ball B(p, r) (in X) can be covered by at most λ balls of radius r/2 centered at points in X. It is also convenient to define the doubling dimension of X to be log λ_{X} (this terminology is used in [15]). See [9] for a survey of nearest neighbor algorithms for doubling sets. We give, for any ε > 0, δ ∈ (0, 1/2], a randomized mapping f : ℝ^{d} → ℝ^{k} that is (1 + ε)- NN-preserving for X, with probability of correctness 1 − δ, where

k = O (\frac{log(1/ε)}{ε^{2}} · log(1/δ) · log λ_{X}) .

2. Sets with small aspect ratio and small γ-dimension. Consider sets X of diameter 1. The aspect ratio of X, Δ, is the inverse of the smallest interpoint distance in X. The γdimension of X, which is a natural notion motivated by the theory of Gaussian processes, is defined in Section 2. Here we just state that γ(X) = O(\sqrt{log λ_{X}}) for all X. We give, for any ε > 0, a randomized mapping f : ℝ^{d} → ℝ^{k} that is (1 + ε)-NN-preserving for X, where k = O(Δ^{2}γ^{2}/ε^{2}). Although quadratic dependence of the dimension on Δ might seem excessive, there exist natural high dimensional data sets with (effectively) small aspect ratios. For example, in the MNIST data set (investigated e.g., in [3]), for all but 2% of points, the distances to nearest neighbors lie in the range [0.19, 0.72].

The above two results are not completely disjoint. This is because, for metrics with constant aspect ratio, the γ dimension and doubling dimension coincide, up to constant factors. However, this is not the case for Δ = ω(1).

Our investigation here is related to the following fascinating open problem in metric geometry: is it true that doubling subsets of ℓ_{2} embed bi-Lipschitzly into low dimensional Euclidean space? (see section 4 for a precise formulation). This question is of great theoretical interest, but it is also clear that a positive answer to it will have algorithmic applications. Our result shows that for certain purposes, such as nearest neighbor search, a weaker notion of embedding suffices, and provably exists. It is worth noting that while our nearest neighbor preserving mapping is linear, an embedding satisfying the conditions of this problem cannot be in general linear (this is discussed in section 4).

2Whenever P is not specified, it is assumed to be equal to 1/2.

Algorithmic implications. Our NN-preserving embeddings have, naturally, immediate applications to efficient approximate nearest neighbor problems.

Our first application combines NN-preserving embeddings with efficient (1 + ε)-approximate nearest neighbor data structures in the Euclidean space (ℝ^{k}, ∥ · ∥_{2}) [16, 4], which use O(|X|/ε^{k}) space and have O(k log(|X|/ε)) query time (recall that we guarantee k = O(log λ_{X} log(1/ε)/ε^{2}), and that we need to add dk to the query time to account for the time needed to embed the query point). This results in a very efficient (1 + ε)-approximate nearest neighbor data structure. For comparison, the data structure of [25], which works for general metrics, suffers from query time exponential in log λ_{X}. For the case of subsets of (ℝ^{d}, ∥ · ∥_{2}) (which we consider here), their data structure can be made faster [Krauthgamer-Lee, personal communication] by using fast approximate nearest neighbor algorithm of [20, 26] as a subroutine. In particular, the query time becomes roughly O(dk + k · log Δ) and space O(|X|/ε^{k}). However, unlike in our case, the query time of that algorithm depends on the aspect ratio Δ. Since for any X we have that λ_{X} ≤ |X|, it follows that our algorithm always uses space |X|^{O([log(1/ε)/ε]^{2})} and has query time O(d log |X| log(1/ε)/ε^{2}). Thus, our algorithm almost matches the bounds of the algorithm of [20], while being much more general.

Our second application involves approximate nearest neighbor where the data set consists of objects that are more complex than points. Specifically, we consider an arbitrary set X containing n sets {S_{1} … S_{n}}, where S_{i} ⊂ ℝ^{d}, i = 1 … n. Let λ = max_{i=1...n} λ_{S_{i}}. If we set δ = \frac{1}{2n}, it follows that for any point q ∈ ℝ^{d}, a random mapping G : ℝ^{d} → ℝ^{k}, k = O(log λ · log n · log(1/ε)/ε^{2}), preserves a (1 + ϵ)-nearest neighbor of q in ∪_{i=1}^{n}S_{i} with probability at least 1/2. Therefore, if we find a (1+ϵ)-approximate nearest neighbor of Gq in {GS_{1} … GS_{n}}, then, with probability 1/2, it is also a (1+O(ϵ))-approximate nearest neighbor of q in {S_{1} … S_{n}}. This corollary provides a strong generalization of a result of [31], who showed this fact for the case when S′_{i}s are affine spaces (although our bound is weaker by a factor of log(1/ϵ)).

Our embedding-based approach to design of approximate nearest neighbor algorithms has the following benefits:

• Simplicity preservation: our data structure is as simple as the data structure we use as a subroutine.

• Modularity: any potential future improvements to algorithms for the approximate nearest neighbor problem in ℓ_{2}^{k} will, when combined with our embedding, automatically yield a better bound for the same problem in ℓ_{2} metrics with low doubling constant.

Although in this paper we focused on embeddings into ℓ_{2}, it is interesting to design NNpreserving embeddings into any space which supports fast approximate nearest neighbor search, e.g., low dimensional ℓ_{∞} [18].

2 Basic concepts

In this section we introduce the basic concepts used in this paper. In particular, we define the doubling constant, the parameter E_{X}, and the γ-dimension. We also point out the relations between these parameters.

Doubling constant. Let (X, d_{X}) be a metric space. In what follows, B_{X}(x, ε) denotes the ball in X of radius r centered at x ∈ X, i.e. B_{X}(x, r) = {y ∈ X : d_{X}(x, y) < r}. The doubling constant of X (see [17]), denoted λ_{X}, is the least integer λ ≥ 1 such that for every x ∈ X and r > 0 there is S ⊆ X with |S| ≤ λ such that

B_{X}(x, 2r) ⊆ ⋃_{s∈S} B_{X}(s, r).

The parameter E_{X}. Fix an integer N and denote by ⟨·, ·⟩ the standard inner product in ℝ^{N}. In what follows g = (g_{1}, ..., g_{N}) is a standard Gaussian vector in ℝ^{N} (i.e. a vector with independent coordinates which are standard Gaussian random variables). Given X ⊆ ℓ_{2}^{N} we denote:

E_{X} = 𝔼 sup_{x∈X} |⟨x, g⟩| = 𝔼 sup_{(x_{1},...,x_{N})∈X} ∑_{i=1}^{N} x_{i}g_{i}.  (1)

We observe that the parameter E of a given bounded set X ⊆ ℓ_{2}^{d} can be estimated very efficiently, that is, in time O(d|X|). This follows directly from the definition, and the fact that for every t > 0, Pr[| sup_{x∈X} |⟨g, x⟩| − E_{X}| > t] ≤ 2e^{−t^{2}/(4 max_{x∈X} ∥x∥_{2}^{2})} (this deviation inequality is a consequence of the fact that the mapping g ↦ sup_{x∈X} |⟨g, x⟩| is Lipschitz with constant max_{x∈X} ∥x∥_{2}, and the Gaussian isoperimetric inequality– see [28]). In addition, even if X is large, e.g., has size exponential in d, E_{X} can often be computed in time polynomial in d [5, 6, 7]. For example, this is the case when X is a set of all matchings in a given graph G, where each matching is represented by a characteristic vector of its edge set.

Doubling constant vs. the parameter E_{X}. We observe that for every bounded X ⊆ ℓ_{2}^{N}:

E_{X} = O (diam(X)\sqrt{log λ_{X}}) .  (2)

Indeed an, inequality of Dudley (see [28]) states that

E_{X} ≤ 24 ∫_{0}^{diam(X)} \sqrt{log N(X, ε)} dε,

where N(X, ε) are the entropy numbers of X, namely the minimal number of balls of radius ε required to cover X. The doubling condition implies that for every ε > 0 we have that N(X, ε diam(X)) ≤ (2/ε)^{log_{2} λ_{X}}, so

E_{X} ≤ 24 diam(X)\sqrt{log_{2} λ_{X}} ∫_{0}^{1} \sqrt{log_{2}(2/ε)} dε ≤ 80 diam(X)\sqrt{log_{2} λ_{X}}.

Another way to prove (2) is as follows. Let B(X) be the set of all Borel probability measures on X. The celebrated Majorizing Measure Theorem of Talagrand [35] states that

E_{X} = Θ ( inf_{μ∈B(X)} sup_{x∈X} ∫_{0}^{∞} \sqrt{log (\frac{1}{μ(B_{X}(x, ε))})} dε) .  (3)

A theorem of Konyagin and Vol′berg [24, 17] states that if X is a complete metric space there exists a Borel measure μ on X such that for every x ∈ X and r > 0, μ(B_{X}(x, 2r)) ≤ λ_{X}^{2}μ(B_{X}(x, r)). Now we just plug μ into (3) and obtain (2).

γ-dimension. The right-hand side of (3) makes sense in arbitrary metric spaces, not just subsets of ℓ_{2}. In fact, another equivalent formulation of (1) is based on Talagrand’s γ_{2} functional, defined as follows. Given a metric space (X, d_{X}) set

γ_{2}(X) = inf sup_{x∈X} ∑_{s=0}^{∞} 2^{s/2}d_{X}(x, A_{s}),  (4)

where the infimum is taken over all choices of subsets A_{s} ⊆ X with |A_{s}| ≤ 2^{2^{s}}. Talagrand’s “generic chaining” version of the majorizing measures theorem [36, 37] states that for every X ⊆ ℓ_{2}, E_{X} = Θ(γ_{2}(X)) (we refer to [14] for a related characterization). The parameter γ_{2}(X) can be defined for arbitrary metric spaces (X, d_{X}) and it is straightforward to check that in general γ_{2}(X) = O (diam(X)\sqrt{log λ_{X}}). Thus, it is natural to define the γ dimension of X to be:

γ dim(X) ≡ [\frac{γ_{2}(X)}{diam(X)}]^{2} .

3 The Case of Euclidean spaces with low γ-dimension

We introduce the following useful modification of the notion of bi-Lipschitz embedding. We then use this notion to give NN-preserving embeddings of ℓ_{2} submetrics with bounded aspect ratio and γ-dimension, into low-dimensional ℓ_{2}.

Definition 3.1 (Bi-Lipschitz embeddings with resolution). Let (X, d_{X}), (Y, d_{Y}) be metric spaces, and δ, D > 0. A mapping f : X → Y is said to be D bi-Lipschitz with resolution δ if there is a (scaling factor) C > 0 such that

∀a, b ∈ X, d_{X}(a, b) > δ ⟹ Cd_{X}(a, b) ≤ d_{Y} (f(a), f(b)) ≤ CDd_{X}(a, b).

In what follows S^{d−1} denotes the unit Euclidean sphere centered at the origin. We will use the following theorem, which is due to Gordon [13]:

Theorem 3.2 (Gordon [13]). Fix X ⊆ S^{d−1} and ε ∈ (0, 1). Then there exists an integer k = O (\frac{E_{X}^{2}}{ε^{2}} ) and a linear mapping T : ℝ^{d} → ℝ^{k} such that for every x ∈ X,

1 − ε ≤ ∥T x∥_{2} ≤ 1 + ε.

Remark 3.1. Since the proof of the above theorem uses probabilistic method (specifically, Gordon [13] proved that if Γ is a k × d matrix whose coordinates are i.i.d. standard Gaussian random variables then T = \frac{1}{\sqrt{k}} Γ will satisfy the assertion of Theorem 3.2 with high probabilitysee also [34, 33]), it also follows that there exists a randomized embedding that satisfy the thesis of the above theorem with probability 1/2. Recently Klartag and Mendelson [23] showed that the same result holds true if the entries of Γ = (γ_{ij}) are only assumed to be i.i.d., have mean 0 and variance 1, and satisfy the ψ_{2} condition 𝔼 e^{γ_{ij}^{2}/C^{2}} ≤ 2 for some constant C. In this case the implied constants may depend on C. A particular case of interest is when Γ is a random ±1 matrix- just like in Achlioptas’ variant [1] of the Johnson-Lindenstrauss lemma [22], we obtain “database friendly” versions of Theorem 4.1. It should be pointed out here that although several papers [12, 10, 21, 1] obtained alternative proofs of the Johnson-Lindenstrauss lemma using different types of random matrices, it turns out that the only thing that matters is that the entries are i.i.d. ψ_{2} random variables (to see this just note that when δ = 0 the set X̃ contains at most |X|^{2} points, and for any n-point subset Z of ℝ^{d}, E_{Z} = O(\sqrt{log n})).

A simple corollary of Theorem 3.2 is the following theorem.

Theorem 3.3. Fix ε, δ > 0 and a set X ⊆ ℝ^{d}. Then there exists an integer k = O (\frac{E_{X}^{2}}{δ^{2}ε^{2}} ) such

that X embeds 1 + ε bi-Lipschitzly in ℝ^{k} with resolution δ. Moreover, the embedding extends to a linear mapping defined on all of ℝ^{d}.

Proof. Consider the set X̃ = \{\frac{x−y}{∥x−y∥_{2}} : x, y ∈ X, ∥x − y∥_{2} ≥ δ\}. Then

EX̃ = 𝔼 (sup \{\frac{|⟨x − y, g⟩|}{∥x − y∥_{2}} : x, y ∈ X ∥x − y∥_{2} ≥ δ\}) ≤ \frac{1}{δ} 𝔼 sup_{x,y∈X} |⟨x − y, g⟩| ≤ \frac{2}{δ}E_{X}.

So the required result is a consequence of Theorem 3.2 applied to X̃.

Remark 3.2. We can make Theorem 3.3 scale invariant by normalizing by diam(X), in which case we get a 1 + ε bi-Lipschitz embedding with resolution δ diam(X), where k = O (\frac{γ dim(X)}{δ^{2}ε^{2}}).

Remark 3.3. Let {e_{j}}_{j=1}^{∞} be the standard basis of ℓ_{2}. Fix ε, δ ∈ (0, 1/2), an integer n and set m = ⌈n^{1/δ^{2}}⌉. Consider the set X = \{e_{1}, …, e_{n}, δe_{n+1}, …, δe_{n+m}\}. Then E_{X} = Θ(\sqrt{log n} + δ\sqrt{log m}) = Θ(\sqrt{log n}). Let f : X → ℝ^{k} be a (not necessarily linear) 1+ε bi-Lipschitz embedding with resolution δ (which is thus a 1+ε bi-Lipschitz embedding since the minimal distance in X is δ\sqrt{2}). By a result of Alon [2] (see also [32]) we deduce that k = Ω (\frac{log m}{ε^{2} log(1/ε)}) = Ω (\frac{E_{X}^{2}}{δ^{2}ε^{2} log(1/ε)}). Thus Theorem 3.3 is nearly optimal.

4 The case of Euclidean doubling spaces

We recall some facts about random Gaussian matrices. Let a ∈ S^{n−1} be a unit vector and let {g_{ij} : 1 ≤ i ≤ k, 1 ≤ j ≤ n} be i.i.d. standard gaussian random variables. Denoting G = \frac{1}{\sqrt{k}} (g_{ij}), by standard arguments (see [11]) the random variable ∥Ga∥_{2}^{2} has distribution whose density is:

\frac{1}{2^{k/2}Γ(k/2)} · x^{\frac{k}{2} −1}e^{−x/2}, x > 0.

By a simple computation it follows that for D > 0

Pr [|∥Ga∥_{2} − 1| ≥ D] ≤ e^{−kD^{2}/8} and Pr[∥Ga∥_{2} ≤ 1/D] ≤ (\frac{3}{D} )^{k} .  (5)

The main result of this section is the following theorem:

Theorem 4.1. For X ⊆ ℝ^{d}, ε ∈ (0, 1) and δ ∈ (0, 1/2) there exists k = O (\frac{log(2/ε)}{ε^{2}} · log(1/δ) · log λ_{X}) such that for every x_{0} ∈ X with probability at least 1 − δ,

1. d(Gx_{0}, G(X \ {x_{0}})) ≤ (1 + ε)d(x_{0}, X \ {x_{0}})

2. Every x ∈ X with ∥x_{0} − x∥_{2} > (1 + 2ε)d(x_{0}, X \ {x_{0}}) satisfies

∥Gx_{0} − Gx∥ > (1 + ε)d(x_{0}, X \ {x_{0}}).

The following lemma can be proved using the methods of [13, 34, 33], but the doubling assumption allows us to give a simple direct proof.

Lemma 4.2. Let X ⊆ B(0, 1) be a subset of the n-dimensional Euclidean unit ball. Then there exist universal constants c, C > 0 such that for k ≥ C log λ_{X} + 1 and D > 1,

Pr[∃x ∈ X, ∥Gx∥_{2} ≥ D] ≤ e^{−ckD^{2}}.

Proof. Without loss of generality 0 ∈ X. We construct subsets I_{0}, I_{1}, I_{2}, … ⊆ X as follows. Set I_{0} = {0}. Inductively, for every t ∈ I_{j} there is a minimal S_{t} ⊆ X with |S_{t}| ≤ λ_{X} such that B(t, 2^{−j}) ∩ X ⊆ ∪_{s∈S_{t}}B(s, 2^{−j−1}) ∩ X. We define I_{j+1} = ∪_{t∈I_{j}}S_{t}.

For x ∈ X there is a sequence {0 = t_{0}(x), t_{1}(x), t_{2}(x), …} ⊆ X such that for all j we have t_{j+1}(x) ∈ S_{t_{j}(x)}, and x = ∑_{j=0}^{∞}[t_{j+1}(x) − t_{j}(x)]. Now, using the fact that ∥t_{j+1}(x) − t_{j}(x)∥_{2} ≤ 2^{−j+1}, we get

Pr[∃x ∈ X, ∥Gx∥_{2} ≥ D] ≤ Pr [∃x ∈ X ∃j ≥ 0, ∥G[t_{j+1}(x) − t_{j}(x)]∥_{2} ≥ \frac{D}{3} (\frac{3}{2})^{−j}]

≤ ∑_{j=0}^{∞} Pr [∃t ∈ I_{j} ∃s ∈ S_{t}, ∥G(t − s)∥_{2} ≥ \frac{D}{6} (\frac{4}{3})^{j} ∥t − s∥_{2}]

≤ ∑_{j=0}^{∞} λ_{X}^{2j}e^{− \frac{kD^{2}}{400} (4/3)^{2j}} ≤ e^{−ckD^{2}},

provided that k ≥ C log λ_{X} + 1 and using the first estimate in (5).

Proof of Theorem 4.1. Without loss of generality x_{0} = 0 and d(x_{0}, X \ {x_{0}}) = 1. If y ∈ X satisfies ∥y∥_{2} = 1 then by (5) we get that Pr[∥Gy∥_{2} ≥ 1 + ε] ≤ e^{−kε^{2}/8}. Thus for k ≥ C/ε^{2} we get that

Pr[d(Gx_{0}, G(X \ {x_{0}})) > (1 + ε)d(x_{0}, X \ {x_{0}})] < δ/2.

Define r_{−1} = 0, r_{0} = 1, r_{i} = 1 + 2ε + ε(i − 1)/4, and consider the annuli

X_{i} = X ∩ [B(0, r_{i}) \ B(0, r_{i−1})] .

Fix an integer i ≥ 1, and use the doubling condition to find S ⊆ X_{i} such that X_{i} ⊆ ∪_{s∈S}B(s, ε/4) and |S| ≤ λ_{X}^{log_{2}(16r_{i}/ε)}. Then by Lemma 4.2

Pr [∃s ∈ S ∃x ∈ B(s, ε/4) ∩ X_{i}, ∥Gs − Gx∥_{2} ≥ \frac{ε\sqrt{i}}{4}] ≤ λ_{X}^{log_{2}(16r_{i}/ε)} · e^{−cki} ≤ e^{−c′ki}.  (6)

On the other hand fix s ∈ S. If ∥Gs∥_{2} < 1 + ε + \frac{ε\sqrt{i}}{4} then there exists a universal constant C > 0 such that

\frac{∥Gs∥_{2}}{∥s∥_{2}} ≤ \frac{1 + ε + \frac{ε\sqrt{i}}{4}}{1 + 2ε + \frac{ε(i−1)}{4}} ≤ \{ \begin{matrix}1 − ε/4 & i ≤ 1/ε^{2} \\ C/\sqrt{i} & i > 1/ε^{2}. \end{matrix}

Hence, by (5)

Pr [∃s ∈ S ∥Gs∥_{2} ≤ 1 + ε + \frac{ε\sqrt{i}}{4}] ≤ \{ \begin{matrix}λ_{X}^{log_{2}(16r_{i}/ε)}e^{−c′′kε^{2}} & i ≤ 1/ε^{2} \\ λ_{X}^{log_{2}(16r_{i}/ε)} · (3C/\sqrt{i})^{k} & i > 1/ε^{2} \end{matrix}

≤ \{ \begin{matrix}e^{−c′′′kε^{2}} & i ≤ 1/ε^{2} \\ i^{−c′′′k} & i > 1/ε^{2}. \end{matrix}  (7)

provided k ≥ C \frac{log(2/ε)}{ε^{2}} · log λ_{X} for a large enough constant C.

Now, from (6) and (7) we see that there exists a constant c̃ such that

Pr[∀x ∈ X_{i}, ∥Gx∥_{2} > 1 + ε] ≥ \{ \begin{matrix}1 − 2e^{−c̃kε^{2}} & i ≤ 1/ε^{2} \\ 1 − 2i^{−c̃k} & i > 1/ε^{2}. \end{matrix}

Hence,

Pr [∃x ∈ X, ∥x∥_{2} > 1 + 2ε ∧ ∥Gx∥_{2} < 1 + ε] ≤ ∑_{i=1}^{∞} Pr[∃x ∈ X_{i}, ∥Gx∥_{2} < 1 + ε]

≤ \frac{2}{ε^{2}} e^{c̃kε^{2}} − 2 ∑_{i>1/ε^{2}} i^{−c̃k} < δ/2,

for large enough k. This completes the proof of Theorem 4.1.

Remark 4.1. Since γ dim(X) = O(log λ_{X}) Theorem 4.1 sheds some light on the following well known problem (which is folklore, but apparently has been first stated explicitly in print in [27]): is it true that any subset X ⊆ ℓ_{2} embeds into ℓ_{2}^{d(λ_{X})} with distortion D(λ_{X}), where d(λ_{X}), D(λ_{X}) depend only on the doubling constant of X. Ideally d(λ_{X}) should be O(log λ_{X}), but no bound depending only on λ_{X} is known. Moreover the analogous result in ℓ_{1} is known to be false [29]. The following example shows that more work needs to be done towards this interesting problem: linear mappings cannot yield the required embedding without a positive lower bound on the resolution. Specifically, we claim that for every D > 1 there are arbitrarily large n-point subsets X_{n} of ℓ_{2} which are doubling with constant 6, such that if there exists a linear mapping T : ℓ_{2} → ℝ^{d} which is D-bi-Lipschitz on X_{n} then d ≥ \frac{log n}{log D} (observe that by the Johnson-Lindenstrauss lemma any n point subset of ℓ_{2} embeds with distortion D via a linear mapping into ℓ_{2}^{k}, with k = O (\frac{log n}{log D} )).

To see this fix D > 1 and an integer d. Let N be a 1/(4D) net in S^{d−1}. Write n + 1 = |N | and N = {x_{1}, …, x_{n}} ∪ {0}. Define X = {2^{−j}x_{j}}_{j=1}^{n}. Whenever 1 ≤ i < j ≤ n we have that

2^{−i} − 2^{−j} ≤ ∥2^{−i}x_{i} − 2^{−j}x_{j}∥_{2} ≤ 2^{−i} + 2^{−j} ≤ 3(2^{−i} − 2^{−j}),

so X is embeddable into the real line with distortion 3. In particular, X is doubling with constant at most 6. However, X cannot be embedded into low dimensions using a linear mapping. Indeed, assume that T : ℝ^{d} → ℝ^{k} is a linear mapping such that for every x, y ∈ X, ∥x − y∥_{2} ≤ ∥T x − T y∥_{2} ≤ D∥x − y∥_{2}. Then for every i, ∥T x_{i}∥_{2} = 2^{i}∥T (2^{−i}x_{i}) − T (0)∥_{2} ∈ [1, D]. Take x ∈ S^{d−1} for which ∥T x∥_{2} = ∥T ∥ = max_{y∈S^{d−1}} ∥T y∥_{2}. There is 1 ≤ i ≤ n such that ∥x−x_{i}∥_{2} ≤ 1/(4D) ≤ 1/2. Then ∥T ∥ = ∥T x∥_{2} ≤ ∥T x_{i}∥_{2} + ∥T (x − x_{i})∥_{2} ≤ D + ∥T ∥ · ∥x − x_{i}∥_{2} ≤ D + \frac{1}{2}∥T ∥. Thus ∥T ∥ ≤ 2D. Now, for every y ∈ S^{d−1} there is 1 ≤ j ≤ n for which ∥y − x_{j}∥_{2} ≤ 1/(4D). It follows that ∥T y∥_{2} ≥ ∥T x_{j}∥_{2} − ∥T (y − x_{j})∥_{2} ≥ 1 − ∥T ∥/(4D) ≥ 1/2. This implies that T is invertible, so necessarily k ≥ d. This proves our claim since by standard volume estimates |X| ≤ (12D)^{d}.

Acknowledgments

The authors would like to thank Mihai Badoiu, Robert Krauthgamer, James R. Lee and Vitali Milman, for discussions during the initial phase of this work.

References

[1] D. Achlioptas. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. System Sci., 66(4):671–687, 2003. Special issue on PODS 2001 (Santa Barbara, CA).

[2] N. Alon. Problems and results in extremal combinatorics. I. Discrete Math., 273(1-3):31–53, 2003. EuroComb’01 (Barcelona).

[3] A. Andoni, M. Datar, N. Immorlica, P. Indyk, and V. Mirrokni. Locality-sensitive hashing scheme based on stable distributions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, 2005.

[4] S. Arya and T. Malamatos. Linear-size approximate voronoi diagrams. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, pages 147–155, 2002.

[5] A. Barvinok. Approximate counting via random optimization. Random Structures Algorithms, 11(2):187–198, 1997.

[6] A. Barvinok and A. Samorodnitsky. The distance approach to approximate combinatorial counting. Geom. Funct. Anal., 11(5):871–899, 2001.

[7] A. Barvinok and A. Samorodnitsky. Random weighting, asymptotic counting, and inverse isoperimetry. 2004. Preprint.

[8] B. Brinkman and M. Charikar. On the impossibility of dimension reduction in ℓ_{1}. Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, 2003.

[9] K. Clarkson. Nearest-neighbor searching and metric space dimensions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, 2005.

[10] S. Dasgupta and A. Gupta. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures Algorithms, 22(1):60–65, 2003.

[11] R. Durrett. Probability: theory and examples. Duxbury Press, Belmont, CA, second edition, 1996.

[12] P. Frankl and H. Maehara. The Johnson-Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. B, 44(3):355–362, 1988.

[13] Y. Gordon. On Milman’s inequality and random subspaces which escape through a mesh in R^{n}. In Geometric aspects of functional analysis (1986/87), volume 1317 of Lecture Notes in Math., pages 84–106. Springer, Berlin, 1988.

[14] O. Guédon and A. Zvavitch. Supremum of a process in terms of trees. In Geometric aspects of functional analysis, volume 1807 of Lecture Notes in Math., pages 136–147. Springer, Berlin, 2003.

[15] A. Gupta, R. Krauthgamer, and J. R. Lee. Bounded geometries, fractals, and low-distortion embeddings. Annual Symposium on Foundations of Computer Science, 2003.

[16] S. Har-Peled. A replacement for voronoi diagrams of near linear size. Annual Symposium on Foundations of Computer Science, 2001.

[17] J. Heinonen. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York, 2001.

[18] P. Indyk. On approximate nearest neighbors in non-euclidean spaces. Proceedings of the Symposium on Foundations of Computer Science, pages 148–155, 1998.

[19] P. Indyk. Stable distributions, pseudorandom generators, embeddings and data stream computation. Annual Symposium on Foundations of Computer Science, 2000.

[20] P. Indyk and R. Motwani. Approximate nearest neighbor: towards removing the curse of dimensionality. Proceedings of the Symposium on Theory of Computing, 1998.

[21] P. Indyk and R. Motwani. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC ’98 (Dallas, TX), pages 604–613. ACM, New York, 1999.

[22] W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern analysis and probability (New Haven, Conn., 1982), pages 189–206. Amer. Math. Soc., Providence, RI, 1984.

[23] B. Klartag and S. Mendelson. Empirical processes and random projections. J. Funct. Anal. To appear.

[24] S. V. Konyagin and A. L. Vol′berg. On measures with the doubling condition. Izv. Akad. Nauk SSSR Ser. Mat., 51(3):666–675, 1987.

[25] R. Krauthgamer and J. R. Lee. Navigating nets: Simple algorithms for proximity search. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 2004.

[26] E. Kushilevitz, R. Ostrovsky, and Y. Rabani. Efficient search for approximate nearest neighbor in high dimensional spaces. Proceedings of the Thirtieth ACM Symposium on Theory of Computing, pages 614–623, 1998.

[27] U. Lang and C. Plaut. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata, 87(1-3):285–307, 2001.

[28] M. Ledoux and M. Talagrand. Probability in Banach spaces, volume 23 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Springer-Verlag, Berlin, 1991. Isoperimetry and processes.

[29] J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: Dimension, snowflakes, and average distortion. European J. Combin. To appear.

[30] J. R. Lee and A. Naor. Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal., 14(4):745–747, 2004.

[31] A. Magen. Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic applications. Proceedings of RANDOM, 2002.

[32] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002.

[33] G. Schechtman. Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. To appear.

[34] G. Schechtman. A remark concerning the dependence on ϵ in Dvoretzky’s theorem. In Geometric aspects of functional analysis (1987–88), volume 1376 of Lecture Notes in Math., pages 274–277. Springer, Berlin, 1989.

[35] M. Talagrand. Regularity of Gaussian processes. Acta Math., 159(1-2):99–149, 1987.

[36] M. Talagrand. Majorizing measures: the generic chaining. Ann. Probab., 24(3):1049–1103, 1996.

[37] M. Talagrand. Majorizing measures without measures. Ann. Probab., 29(1):411–417, 2001.