Nearest Neighbor Preserving Embeddings

Piotr Indyk MIT and Assaf Naor Microsoft Research

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. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems General Terms: Algorithms, Theory Additional Key Words and Phrases: nearest neighbor, dimensionality reduction, embeddings, doubling spaces

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 has become 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 [Indyk and Motwani 1999; Kushilevitz et al. 2000], to give efficient approximate nearest neighbor algorithms in high-dimensional spaces.

More recently (e.g., in [Indyk 2000]), 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 to X, 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

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 [Indyk and Motwani 1999; Har-Peled 2001] 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

The first author was supported in part by NSF ITR grant CCR-0220280, David and Lucille Packard Fellowship and Alfred P. Sloan Fellowship. Permission to make digital/hard copy of all or part of this material without fee for personal or classroom use provided that the copies are not made or distributed for profit or commercial advantage, the ACM copyright/server notice, the title of the publication, and its date appear, and notice is given that copying is by permission of the ACM, Inc. To copy otherwise, to republish, to post on servers, or to redistribute to lists requires prior specific permission and/or a fee. \begin{matrix}c \\ ◯ \end{matrix} 20YY ACM 0000-0000/20YY/0000-0001 $5.00

ACM Journal Name, Vol. V, No. N, Month 20YY, Pages 1–0??.

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.

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 [Indyk 2000]. 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 [Brinkman and Charikar 2005; Lee and Naor 2004]. Thus, the definition of NNpreserving 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 [Gupta et al. 2003]). See [Clarkson 2005] for a survey of notions of dimension which are relevant to nearest neighbor search. 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 [Andoni et al. 2005]), 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 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, a bi-Lipschitz embedding of a doubling Euclidean metric into a low dimensional Euclidean space cannot be in general linear (this is discussed in Section 4).

nearest neighbor, not just the near neighbor. 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}) [Har-Peled 2001; Arya and Malamatos 2002], 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 O(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 [Krauthgamer and Lee 2004; Har-Peled and Mendel 2006], 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 [Indyk and Motwani 1999; Kushilevitz et al. 2000] 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 [Indyk and Motwani 1999], while being 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 G(q) in {G(S_{1}) … G(S_{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 [Magen 2002], 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 prob-

lem 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 NN-preserving embeddings into any space which supports fast approximate nearest neighbor search, e.g., low dimensional ℓ_{∞} [Indyk 1998].

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, r) 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 [Heinonen 2001]), 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_{X} 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 of E_{X}, 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 [Ledoux and Talagrand 1991]). 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 [Barvinok 1997; Barvinok and Samorodnitsky 2001; 2004]. 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 [Ledoux and Talagrand 1991]) 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 [Talagrand 1987] 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 [Konyagin and Vol′berg 1987; Heinonen 2001] 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 [Talagrand 1996; 2001; 2005] states that for every X ⊆ ℓ_{2}, E_{X} = Θ(γ_{2}(X)) (we refer to [Guédon and Zvavitch 2003] 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 [Gordon 1988]:

Theorem 3.2 [Gordon 1988]. 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 [Gordon 1988] 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 probability- see also [Schechtman 1989; 2006]), 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 [Klartag and Mendelson 2005] 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 have sub-Gaussian tail bounds, i.e. Pr[|γ_{ij}| > u] ≤ Ke^{−δu^{2}} for every u > 0 and some constants K, δ > 0. In this case the implied constants may depend on K, δ. A particular case of interest is when Γ is a random ±1 matrix- just like in Achlioptas’ variant [Achlioptas 2003] of the Johnson-Lindenstrauss lemma [Johnson and Lindenstrauss 1984], we obtain “database friendly” versions of Theorem 4.1.

It should be pointed out here that although several papers [Frankl and Maehara 1988; Dasgupta and Gupta 2003; Indyk and Motwani 1999; Achlioptas 2003] 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. sub-Gaussian 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})). Here is a simple proof of this fact using an elementary large-deviation argument (a similar argument was also recently obtained in [Matoušek 2006]). Let g be a standard Gaussian random variable, i.e. its density is \frac{1}{\sqrt{2π}} e^{−x^{2}/2}. In what follows g will always be assumed to be independent of all the other random variables that appear in the proof. The only properties of g that we will need is that for all t ∈ ℝ we have 𝔼e^{tg} = e^{t^{2}/2} and for all t ∈ (0, 1/2) we have 𝔼e^{tg^{2}} = \frac{1}{\sqrt{1−2t}}.

Now, let X be a symmetric random variable (i.e. X and −X have the same distribution) such that 𝔼X^{2}=1. Assume that X is sub-Gaussian, i.e. that 𝔼e^{uX} ≤ e^{cu^{2}} for all u ∈ ℝ and some constant c > 0 (note that this condition on the moment generating function easily follows from sub-Gaussian tail bounds). Fix a unit vector a = (a_{1}, …, a_{n}) ∈ S^{n−1}. Let X_{1}, …, X_{n} be i.i.d. copies of X and denote U = ∑_{j=1}^{n} a_{j}X_{j}. Then 𝔼U^{2} = 1, and for every 0 ≤ t ≤ \frac{1}{8c} we have

𝔼e^{tU^{2}} = 𝔼_{U}𝔼_{g}e^{\sqrt{2t}gU} = 𝔼_{g} (∏_{j=1}^{n} 𝔼_{X}e^{\sqrt{2t}a_{j}gX} ) ≤ E_{g} [∏_{j=1}^{n} e^{2cta_{j}^{2}g^{2}} ] = 𝔼_{g}e^{2ctg^{2}} = \frac{1}{\sqrt{1 − 4ct}} ≤ \sqrt{2}. (5)

Therefore using (5) we see that for every −\frac{1}{8c} ≤ t ≤ \frac{1}{8c} we have

𝔼e^{tU^{2}} = ∑_{m=0}^{∞} \frac{t^{m}𝔼U^{2m}}{m!} ≤ 1 + t + ∑_{m=2}^{∞} \frac{(8c|t|)^{m} (\frac{1}{8c})^{m} 𝔼U^{2m}}{m!} ≤ 1 + t + (8ct)^{2} ∑_{m=2}^{∞} \frac{(\frac{1}{8c})^{m} 𝔼U^{2m}}{m!}

≤ 1 + t + (8ct)^{2} 𝔼e^{U^{2}/(8c)} ≤ 1 + t + 100c^{2}t^{2} ≤ e^{t+100c^{2}t^{2}}. (6)

Hence if U_{1}, …, U_{k} are i.i.d. copies of U then for every 0 < ε ≤ 25c we can apply (6) with t = \frac{ε}{200c^{2}} to get that

Pr [\frac{1}{k} ∑_{i=1}^{k} U_{i}^{2} ≥ 1 + ε] ≤ e^{−k(1+ε)t} (𝔼e^{tU^{2}})^{k} ≤ e^{−k(1+ε)t+kt+100kc^{2}t^{2}} = e^{−kε^{2}/(400c^{2})},

and

Pr [−\frac{1}{k} ∑_{i=1}^{k} U_{i}^{2} ≥ −1 + ε] ≤ e^{k(1−ε)t} (𝔼e^{−tU^{2}})^{k} ≤ e^{k(1−ε)t−kt+100kc^{2}t^{2}} = e^{−kε^{2}/(400c^{2})}.

In summary, we proved that for every 0 < ε < 25c we have

Pr [|\frac{1}{k} ∑_{i=1}^{k} U_{i}^{2} − 1| ≥ ε] ≤ 2e^{−kε^{2}/(400c^{2})}.

Another way to phrase this inequality is that if {X_{ij} : i = 1, …, k j = 1, …, n} are i.i.d. copies of X, and we consider the k × n random matrix A := \frac{1}{\sqrt{k}} (X_{ij}) then for every x ∈ ℝ^{n} we have

Pr [|∥Ax∥_{2}^{2} − ∥x∥_{2}^{2}| ≥ ε∥x∥_{2}^{2}] ≤ 2e^{−kε^{2}/(400c^{2})}.

An application of the union bound shows that this concentration inequality implies the Johnson-Lindenstrauss dimensionality reduction result for arbitrary random matrices with sub-Gaussian i.i.d. entries.

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 [Alon 2003] (see also [Matoušek 2002]) we deduce that k = Ω (\frac{log m}{ε^{2} log(1/ε)}) = Ω (\frac{E_{X}^{2}}{δ^{2}ε^{2} log(1/ε)}). Thus the value of k in 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 [Durrett 1996]) 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} .  (7)

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 [Gordon 1988; Schechtman 1989; 2006], 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 (7).

Proof 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 (7) we get that Pr[∥Gy∥_{2} ≥ 1 + ε] ≤ e^{−kε^{2}/8}. Thus for k ≥ C log(1/δ)/ε^{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}.  (8)

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−2)}{4}} ≤ \{ \begin{matrix}1 − ε/4 & i ≤ 1/ε^{2} \\ C/\sqrt{i} & i > 1/ε^{2}. \end{matrix}

Hence, by (7)

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}  (9)

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

Now, from (8) and (9) 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 problem (which is folklore, but apparently has been first stated explicitly in print in [Lang and Plaut 2001]): 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, as observed in [Gupta et al. 2003], the results of [Laakso 2000; Gupta et al. 2004] imply that the analogous result in ℓ_{1} is false (see also [Lee et al. 2005] for a stronger negative result in ℓ_{1}). The following example shows that more work needs to be done towards solving this problem positively (if at all possible. In fact, we believe that this problem has a negative answer): 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 Achlioptas, D. 2003. Database-friendly random projections: Johnson-Lindenstrauss with binary coins. J. Comput. System

Sci. 66, 4, 671–687. Special issue on PODS 2001 (Santa Barbara, CA). Alon, N. 2003. Problems and results in extremal combinatorics. I. Discrete Math. 273, 1-3, 31–53. EuroComb’01 (Barcelona). Andoni, A., Datar, M., Immorlica, N., Indyk, P., and Mirrokni, V. 2005. Locality-sensitive hashing scheme based on stable

distributions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press. Arya, S. and Malamatos, T. 2002. Linear-size approximate voronoi diagrams. Proceedings of the ACM-SIAM Symposium

on Discrete Algorithms, 147–155. Barvinok, A. 1997. Approximate counting via random optimization. Random Structures Algorithms 11, 2, 187–198. Barvinok, A. and Samorodnitsky, A. 2001. The distance approach to approximate combinatorial counting. Geom. Funct.

Anal. 11, 5, 871–899. Barvinok, A. and Samorodnitsky, A. 2004. Random weighting, asymptotic counting, and inverse isoperimetry. Preprint. Brinkman, B. and Charikar, M. 2005. On the impossibility of dimension reduction in l_{1}. J. ACM 52, 5, 766–788 (electronic).

Clarkson, K. 2005. Nearest-neighbor searching and metric space dimensions. In Nearest-Neighbor Methods for Learning and

Vision: Theory and Practice. MIT Press. Dasgupta, S. and Gupta, A. 2003. An elementary proof of a theorem of Johnson and Lindenstrauss. Random Structures

Algorithms 22, 1, 60–65. Durrett, R. 1996. Probability: theory and examples, Second ed. Duxbury Press, Belmont, CA. Frankl, P. and Maehara, H. 1988. The Johnson-Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory

Ser. B 44, 3, 355–362. Gordon, Y. 1988. On Milman’s inequality and random subspaces which escape through a mesh in R^{n}. In Geometric aspects

of functional analysis (1986/87). Lecture Notes in Math., vol. 1317. Springer, Berlin, 84–106. Guédon, O. and Zvavitch, A. 2003. Supremum of a process in terms of trees. In Geometric aspects of functional analysis.

Lecture Notes in Math., vol. 1807. Springer, Berlin, 136–147. Gupta, A., Krauthgamer, R., and Lee, J. R. 2003. Bounded geometries, fractals, and low-distortion embeddings. Annual

Symposium on Foundations of Computer Science, 534–543. Gupta, A., Newman, I., Rabinovich, Y., and Sinclair, A. 2004. Cuts, trees and l_{1}-embeddings of graphs. Combinator-

ica 24, 2, 233–269. Har-Peled, S. 2001. A replacement for voronoi diagrams of near linear size. Annual Symposium on Foundations of Computer

Science, 94–103. Har-Peled, S. and Mendel, M. 2006. Fast construction of nets in low-dimensional metrics and their applications. SIAM J.

Comput. 35, 5, 1148–1184 (electronic). Heinonen, J. 2001. Lectures on analysis on metric spaces. Universitext. Springer-Verlag, New York. Indyk, P. 1998. On approximate nearest neighbors in non-euclidean spaces. Proceedings of the Symposium on Foundations of

Computer Science, 148–155. Indyk, P. 2000. Stable distributions, pseudorandom generators, embeddings and data stream computation. In 41st Annual

Symposium on Foundations of Computer Science (Redondo Beach, CA, 2000). IEEE Comput. Soc. Press, Los Alamitos, CA, 189–197.

Indyk, P. and Motwani, R. 1999. Approximate nearest neighbors: towards removing the curse of dimensionality. In STOC

’98 (Dallas, TX). ACM, New York, 604–613. Johnson, W. B. and Lindenstrauss, J. 1984. Extensions of Lipschitz mappings into a Hilbert space. In Conference in modern

analysis and probability (New Haven, Conn., 1982). Amer. Math. Soc., Providence, RI, 189–206. Klartag, B. and Mendelson, S. 2005. Empirical processes and random projections. J. Funct. Anal. 225, 1, 229–245. Konyagin, S. V. and Vol′berg, A. L. 1987. On measures with the doubling condition. Izv. Akad. Nauk SSSR Ser. Mat. 51, 3,

666–675. Krauthgamer, R. and Lee, J. R. 2004. Navigating nets: simple algorithms for proximity search. In SODA ’04: Proceedings

of the fifteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 798–807.

Kushilevitz, E., Ostrovsky, R., and Rabani, Y. 2000. Efficient search for approximate nearest neighbor in high dimensional

spaces. SIAM J. Comput. 30, 2, 457–474 (electronic). Laakso, T. J. 2000. Ahlfors Q-regular spaces with arbitrary Q > 1 admitting weak Poincaré inequality. Geom. Funct.

Anal. 10, 1, 111–123. Lang, U. and Plaut, C. 2001. Bilipschitz embeddings of metric spaces into space forms. Geom. Dedicata 87, 1-3, 285–307. Ledoux, M. and Talagrand, M. 1991. Probability in Banach spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete (3)

[Results in Mathematics and Related Areas (3)], vol. 23. Springer-Verlag, Berlin. Isoperimetry and processes. Lee, J. R., Mendel, M., and Naor, A. 2005. Metric structures in L_{1}: dimension, snowflakes, and average distortion. European

J. Combin. 26, 8, 1180–1190. Lee, J. R. and Naor, A. 2004. Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal. 14, 4,

745–747. Magen, A. 2002. Dimensionality reductions that preserve volumes and distance to affine spaces, and their algorithmic appli-

cations. In Randomization and approximation techniques in computer science. Lecture Notes in Comput. Sci., vol. 2483. Springer, Berlin, 239–253.

Matoušek, J. 2002. Lectures on discrete geometry. Graduate Texts in Mathematics, vol. 212. Springer-Verlag, New York. Matoušek, J. 2006. On variants of the Johnson-Lindenstrauss lemma. Preprint. Schechtman, G. 1989. A remark concerning the dependence on ϵ in Dvoretzky’s theorem. In Geometric aspects of functional

analysis (1987–88). Lecture Notes in Math., vol. 1376. Springer, Berlin, 274–277. Schechtman, G. 2006. Two observations regarding embedding subsets of Euclidean spaces in normed spaces. Adv. Math. 200, 1,

125–135. Talagrand, M. 1987. Regularity of Gaussian processes. Acta Math. 159, 1-2, 99–149. Talagrand, M. 1996. Majorizing measures: the generic chaining. Ann. Probab. 24, 3, 1049–1103. Talagrand, M. 2001. Majorizing measures without measures. Ann. Probab. 29, 1, 411–417. Talagrand, M. 2005. The generic chaining. Springer Monographs in Mathematics. Springer-Verlag, Berlin. Upper and lower

bounds of stochastic processes.