A SPECTRAL GAP PRECLUDES LOW-DIMENSIONAL EMBEDDINGS

ASSAF NAOR

Abstract. We prove that there is a universal constant C > 0 with the following property. Suppose that n ∈ ℕ and that A = (a_{ij}) ∈ M_{n}(ℝ) is a symmetric stochastic matrix. Denote the second-largest eigenvalue of A by λ_{2}(A). Then for any finite-dimensional normed space (X, ∥ · ∥) we have

∀ x_{1}, …, x_{n} ∈ X, dim(X) ⩾ \frac{1}{2} exp (C \frac{1 − λ_{2}(A)}{\sqrt{n}} ( \frac{∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥^{2}} )^{\frac{1}{2}} ) .

This implies that if an n-vertex O(1)-expander embeds with average distortion D ⩾ 1 into X, then necessarily dim(X) ≳ n^{c/D} for some universal constant c > 0, thus improving over the previously best-known estimate dim(X) ≳ (log n)^{2}/D^{2} of Linial, London and Rabinovich, strengthening a theorem of Matoušek, and answering a question of Andoni, Nikolov, Razenshteyn and Waingarten.

1. Introduction

Given n ∈ ℕ and a symmetric stochastic matrix A ∈ M_{n}(ℝ), the eigenvalues of A will be denoted below by 1 = λ_{1}(A) ⩾ … ⩾ λ_{n}(A) ⩾ −1. Here we prove the following statement. Theorem 1. There is a universal constant C > 0 with the following property. Fix n ∈ ℕ and a symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ). For any finite-dimensional normed space (X, ∥·∥),

∀ x_{1}, …, x_{n} ∈ X,  dim(X) ⩾ \frac{1}{2} exp (C \frac{1 − λ_{2}(A)}{\sqrt{n}} (\frac{∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥^{2}} )^{\frac{1}{2}} ) . (1)

We shall next explain a noteworthy geometric consequence of Theorem 1 that arises from an examination of its special case when the matrix A is the normalized adjacency matrix of a connected graph. Before doing so, we briefly recall some standard terminology related to metric embeddings.

Suppose that (�, d) is a finite metric space and (X, ∥·∥) is a normed space. For L ⩾ 0, a mapping ϕ : � → X is said to be L-Lipschitz if ∥ϕ(x) − ϕ(y)∥ ⩽ Ld(x, y) for every x, y ∈ �. For D ⩾ 1, one says that � embeds into X with (bi-Lipschitz) distortion D if there is a D-Lipschitz mapping ϕ : � → X such that ∥ϕ(x) − ϕ(y)∥ ⩾ d(x, y) for every x, y ∈ �. Following Rabinovich [Rab08], given D ⩾ 1 one says that � embeds into X with average distortion D if there exists a D-Lipschitz mapping ϕ : � → X such that ∑_{x,y∈�} ∥ϕ(x) − ϕ(y)∥ ⩾ ∑_{x,y∈�} d(x, y).

For n ∈ ℕ write [n] = {1, …, n}. Fix k ∈ {3, …, n} and let G = ([n], E_{G}) be a k-regular connected graph whose vertex set is [n]. The shortest-path metric that is induced by G on [n] is denoted d_{G} : [n] × [n] → ℕ ∪ {0}. A simple (and standard) counting argument (e.g. [Mat97]) gives

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j) ≳ \frac{log n}{log k},  (2)

where in (2), as well as in the rest of this article, we use the following (standard) asymptotic notation. Given two quantities Q, Q′ > 0, the notations Q ≲ Q′ and Q′ ≳ Q mean that Q ⩽ KQ′ for some universal constant K > 0. The notation Q ≍ Q′ stands for (Q ≲ Q′) ∧ (Q′ ≲ Q). If we need to allow for dependence on certain parameters, we indicate this by subscripts. For example, in the presence of an auxiliary parameter ψ, the notation Q ≲_{ψ} Q′ means that Q ⩽ c(ψ)Q′, where c(ψ) > 0 is allowed to depend only on ψ, and similarly for the notations Q ≳_{ψ} Q′ and Q ≍_{ψ} Q′.

Date: June 8, 2017.

2010 Mathematics Subject Classification. 30L05, 46B85, 46B20, 46B80.

Key words and phrases. Metric embeddings, dimensionality reduction, expander graphs, nonlinear spectral gaps, nearest neighbor search, complex interpolation, Markov type.

Supported by BSF grant 2010021, the Packard Foundation and the Simons Foundation. The research presented here was conducted under the auspices of the Simons Algorithms and Geometry (A&G) Think Tank.

The normalized adjacency matrix of the graph G, denoted A_{G}, is the matrix whose entry at (i, j) ∈ [n] × [n] is equal to \frac{1}{k}1_{\{i,j\}∈E_{G}}. Denote from now on λ_{2}(G) = λ_{2}(A_{G}). Let (X, ∥ · ∥) be a finite-dimensional normed space. Fix D ⩾ 1 and a mapping ϕ : [n] → X that satisfies

(\frac{1}{|E_{G}|} ∑_{\{i,j\}∈E_{G}} ∥ϕ(i) − ϕ(j)∥^{2})^{\frac{1}{2}} = (\frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n}(A_{G})_{ij}∥ϕ(i) − ϕ(j)∥^{2})^{\frac{1}{2}} ⩽ D.  (3)

Condition (3) holds true, for example, if ϕ is D-Lipschitz as a mapping from ([n], d_{G}) to (X, ∥ · ∥). Let η > 0 be the implicit constant in the right hand side of (2), and suppose that ϕ also satisfies

(\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥ϕ(i) − ϕ(j)∥^{2})^{\frac{1}{2}} ⩾ η\frac{log n}{log k}.  (4)

Due to (2) and the Cauchy–Schwarz inequality, conditions (3) and (4) hold true simultaneously (for an appropriately chosen ϕ) if e.g. ([n], d_{G}) embeds with average distortion D into (X, ∥ · ∥). At the same time, by an application of Theorem 1 with x_{i} = ϕ(i) and A = A_{G} we see that

dim(X) ≳ e^{\frac{Cη(1−λ_{2}(A)) log n}{D log k}} = n^{\frac{Cη(1−λ_{2}(A))}{D log k}} .

For ease of later reference, we record this conclusion as the following corollary.

Corollary 2. There exists a universal constant ρ ∈ (0, ∞) such that for every n ∈ ℕ and k ∈ [n], if G = ([n], E_{G}) is a connected n-vertex k-regular graph and D ⩾ 1, then the dimension of any normed space (X, ∥ · ∥) into which the metric space ([n], d_{G}) embeds with average distortion D must satisfy dim(X) ≳ n^{c(G)/D}, where c(G) = ρ(1 − λ_{2}(A))/ log k.

For every n ∈ ℕ there exists a 4-regular graph G_{n} = ([n], E_{G_{n}}) with λ_{2}(G_{n}) ⩽ 1 − δ, where δ ∈ (0, 1) is a universal constant; see the survey [HLW06] for this statement as well as much more on such expander graphs. It therefore follows from Corollary 2 that for every n ∈ ℕ there exists an n-point metric space �_{n} with the property that its embeddability into any normed space with average distortion D forces the dimension of that normed space to be at least n^{c/D}, where c > 0 is a universal constant.^{1} The significance of this statement will be discussed in Section 1.1 below.

The desire to obtain Corollary 2 was the goal that initiated our present investigation, because Corollary 2 resolves (negatively) a question that was posed by Andoni, Nikolov, Razenshteyn and Waingarten [ANRW16, Section 1.6] in the context of their work on efficient approximate nearest neighbor search (NNS). Specifically, they devised in [ANRW16] an approach for proving a hardness result for NNS that requires the existence of an n-vertex expander that embeds with bi-Lipschitz distortion O(1) into some normed space of dimension n^{o(1)}. Corollary 2 shows that no such expander exists. One may view this statement as a weak indication that perhaps an algorithm for NNS in general norms could be designed with better performance than what is currently known, but we leave this interesting algorithmic question for future research and refer to [ANRW16] for a full description of this connection. The previously best-known bound in the context of Corollary 2 was due to Linial, London and Rabinovich in [LLR95, Proposition 4.2], where it was shown that if G is O(1)-regular and λ_{2}(G) = 1 − Ω(1), then any normed space X into which G embeds with average distortion D must satisfy dim(X) ≳ (log n)^{2}/D^{2}. The above exponential improvement over [LLR95] is sharp, up to the value of c, as shown by Johnson, Lindenstrauss and Schechtman [JLS87].

1A good bound on the constant c can be obtained if one applies Corollary 2 to Ramanujan graphs [LPS88, Mar88] rather than to arbitrary expanders, but we shall not pursue this here.

1.1. Dimensionality reduction. The present work relates to fundamental questions in pure and applied mathematics that have been extensively investigated over the past three decades, and are of major current importance. The overarching theme is that of dimensionality reduction, which corresponds to the desire to “compress” n-point metric spaces using representations with few coordinates, namely embeddings into ℝ^{k} with (hopefully) k small, in such a way that pairwise distances could be (approximately) recovered by computing lengths in the image with respect to an appropriate norm on ℝ^{k}. Corollary 2 asserts that this cannot be done in general if one aims for compression to k = n^{o(1)} coordinates. In essence, it states that a spectral gap induces an inherent (power-type) high-dimensionality even if one allows for recovery of pairwise distances with large multiplicative errors, or even while only approximately preserving two averages of the squared distances: along edges and all pairs, corresponding to (3) and (4), respectively. In other words, we isolate two specific averages of pairwise squared distances of a finite collection of vectors in an arbitrary normed space, and show that if the ratio of these averages is roughly (i.e., up to a fixed but potentially large factor) the same as in an expander then the dimension of the ambient space must be large.

In addition to obtaining specific results along these lines, there is need to develop techniques to address dimensionality questions that relate nonlinear (metric) considerations to the linear dimension of the vector space. Our main conceptual contribution is to exhibit a new approach to a line of investigations that previously yielded comparable results using algebraic techniques. In contrast, here we use an analytic method arising from a recently developed theory of nonlinear spectral gaps.

Adopting the terminology of [LLR95, Definition 2.1], given D ∈ [1, ∞), n ∈ ℕ and an n-point metric space �, define a quantity dim_{D}(�) ∈ ℕ, called the (distortion-D) metric dimension of �, to be the minimum k ∈ ℕ for which there exists a k-dimensional normed space X_{�} such that � embeds into X_{�} with distortion D. We always have dim_{D}(�) ⩽ dim_{1}(�) ⩽ n − 1 by the classical Fréchet isometric embedding [Fré06] into ℓ_{∞}^{n−1}. In their seminal work [JL84], Johnson and Lindenstrauss asked [JL84, Problem 3] whether dim_{D}(�) = O(log n) for some D = O(1) and every n-point metric space �. Observe that the O(log n) bound arises naturally here, as it cannot be improved due to a standard volumetric argument when one considers embeddings of the n-point equilateral space; see also Remark 4 below for background on the Johnson–Lindenstrauss question in the context of the Ribe program. Nevertheless, Bourgain proved [Bou85, Corollary 4] that this question has a negative answer. He showed that for arbitrarily large n ∈ ℕ there is an n-point metric space �_{n} such that dim_{D}(�) ≳ (log n)^{2}/(D log log n)^{2} for every D ∈ [1, ∞). He also posed in [Bou85] the natural question of determining the asymptotic behavior of the maximum of dim_{D}(�) over all n-point metric spaces �. It took over a decade for this question to be resolved.

In terms of upper bounds, Johnson, Lindenstrauss and Schechtman [JLS87] proved that there exists a universal constant α > 0 such that for every D ⩾ 1 and n ∈ ℕ we have dim_{D}(�) ≲_{D} n^{α/D} for any n-point metric space �. In [Mat92, Mat96], Matoušek improved this result by showing that one can actually embed � with distortion D into ℓ_{∞}^{k} for some k ∈ ℕ satisfying k ≲_{D} n^{α/D}, i.e., the target normed space need not depend on � (Matoušek’s proof is also simpler than that of [JLS87], and it yields a smaller value of α; see the exposition in Chapter 15 of the monograph [Mat02]).

In terms of lower bounds, an asymptotic improvement over [Bou85] was made by Linial, London and Rabinovich [LLR95, Proposition 4.2], who showed that for arbitrarily large n ∈ ℕ there exists an n-point metric space �_{n} such that dim_{D}(�_{n}) ≳ (log n)^{2}/D^{2} for every D ∈ [1, ∞). For small distortions, Arias-de-Reyna and Rodríguez-Piazza proved [AdRRP92] the satisfactory assertion that for arbitrarily large n ∈ ℕ there exists an n-point metric space �_{n} such that dim_{D}(�_{n}) ≳_{D} n for every 1 ⩽ D < 2. For larger distortions, it was asked in [AdRRP92, page 109] whether for every D ∈ (2, ∞) and n ∈ ℕ we have dim_{D}(�) ≲_{D} (log n)^{O(1)} for any n-point metric space �. In [Mat96], Matoušek famously answered this question negatively by proving Theorem 3 below via a clever argument that relies on (a modification of) graphs of large girth with many edges and an existential counting argument (inspired by ideas of Alon, Frankl and Rödl [AFR85]) that uses the classical theorem of Milnor [Mil64] and Thom [Tho65] from real algebraic geometry.

Theorem 3 (Matoušek [Mat96]). For every D ⩾ 1 and arbitrarily large n ∈ ℕ, there is an n-point metric space �_{n}(D) such that dim_{D} (�_{n}(D)) ≳_{D} n^{c/D}, where c > 0 is a universal constant.

Due to the upper bound that was quoted above, Matoušek’s theorem satisfactorily answers the questions of Johnson–Lindenstrauss and Bourgain, up to the value of the universal constant c. Corollary 2 also resolves these questions, via an approach for deducing dimensionality lower bounds from rough (bi-Lipschitz) metric information that differs markedly from Matoušek’s argument.

Our solution has some new features. The spaces �_{n}(D) of Theorem 3 can actually be taken to be independent of the distortion D, while the construction of [Mat96] depends on D (it is based on graphs of girth of order D). One could alternatively achieve this by considering the disjoint union of the spaces {�_{n}(2^{k})}_{k=0}^{m} for m ≍ log n, which is a metric space of size O(n log n). More importantly, rather than using an ad-hoc construction (relying also on a non-constructive existential statement) as in [Mat96], here we specify a natural class of metric spaces, namely the shortest-path metrics on expanders (see also Remark 5 below), for which Theorem 3 holds. Obtaining this result for this concrete class of metric spaces is needed to answer the question of [ANRW16] that was quoted above. Finally, Matoušek’s approach based on the Milnor–Thom theorem uses the fact that the embedding has controlled bi-Lipschitz distortion, while our approach is robust in the sense that it deduces the stated lower bound on the dimension from an embedding with small average distortion.

Remark 4. The Ribe program aims to uncover an explicit “dictionary” between the local theory of Banach spaces and general metric spaces, inspired by an important rigidity theorem of Ribe [Rib76] that indicates that a dictionary of this sort should exist. See the introduction of [Bou86] as well as the surveys [Kal08, Nao12a, Bal13] and the monograph [Ost] for more on this topic. While more recent research on dimensionality reduction is most often motivated by the need to compress data, the initial motivation of the question of Johnson and Lindenstrauss [JL84] that we quoted above arose from the Ribe program. It seems simplest to include here a direct quotation of Matoušek’s explanation in [Mat96, page 334] for the origin of the investigations that led to Theorem 3.

...This investigation started in the context of the local Banach space theory, where the general idea was to obtain some analogs for general metric spaces of notions and results dealing with the structure of finite dimensional subspaces of Banach spaces. The distortion of a mapping should play the role of the norm of a linear operator, and the quantity log n, where n is the number of points in a metric space, would serve as an analog of the dimension of a normed space. Parts of this programme have been carried out by Bourgain, Johnson, Lindenstrauss, Milman and others...

Despite many previous successes of the Ribe program, not all of the questions that it raised turned out to have a positive answer (see e.g. [MN13a]). Theorem 3 is among the most extreme examples of failures of natural steps in the Ribe program, with the final answer being exponentially worse than the initial predictions. Corollary 2 provides a further explanation of this phenomenon.

Remark 5. The reasoning prior to Corollary 2 gives the following statement that applies to regular graphs that need not have bounded degree. Fix β > 0 and n ∈ ℕ. Suppose that G = ([n], E_{G}) is a connected regular graph that satisfies (1 − λ_{2}(G)) ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j) ⩾ βn^{2} log n. Then, dim_{D}(G) ≳ n^{Cβ/D} for every D ⩾ 1, where C > 0 is the universal constant of Theorem 1 and we use the notation dim_{D}([n], d_{G}) = dim_{D}(G). Let diam(G) be the diameter of ([n], d_{G}) and suppose (for simplicity) that G is vertex-transitive (e.g., G can be the Cayley graph of a finite group). Then, it is simple to check that n^{2} diam(G) ⩾ ∑_{i=1}^{n} ∑_{j=1}^{n} d_{G}(i, j) ⩾ n^{2} diam(G)/4 (see. e.g. equation (4.24) in [Nao14]), and therefore the above reasoning shows that every vertex-transitive graph satisfies

∀ D ⩾ 1,  dim_{D}(G) ≳ e^{\frac{C}{4D} (1−λ_{2}(G)) diam(G)}.  (5)

In particular, it follows from (5) that if ([n], d_{G}) embeds with distortion O(1) into some normed space of dimension (log n)^{O(1)}, then necessarily (1 − λ_{2}(G)) diam(G) ≲ log log n.

There are many examples of Cayley graphs G = ([n], E_{G}) for which λ_{2}(G) = 1 − Ω(1) and diam(G) ≳ log n (see e.g. [AR94, NR09]). In all such examples, (5) asserts that dim_{D}(G) ≳ n^{c/D} for some universal constant c > 0. The Cayley graph that was studied in [KN06] (a quotient of the Hamming cube by a good code) now shows that there exist arbitrarily large n-point metric spaces �_{n} with dim_{1}(�_{n}) ≲ log n (indeed, �_{n} embeds isometrically into ℓ_{1}^{k} for some k ≲ log n), yet �_{n} has a O(1)-Lipschitz quotient (see [BJL^{+}99] for the relevant definition) that does not embed with distortion O(1) into any normed space of dimension n^{o(1)}. To the best of our knowledge, it wasn’t previously known that the metric dimension dim_{D}(·) can become asymptotically larger (and even increase exponentially) under Lipschitz quotients, which is yet another major departure from the linear theory, in contrast to what one would normally predict in the context of the Ribe program.

1.2. Roadmap. Theorem 1 will be proven in Section 2, which starts with an informal overview of the main ideas that enter into the proof. Section 3 derives an additional example of an application of these ideas to metric embedding theory. We end with Section 4, which contains further discussion about dimensionality reduction questions and presents some important open problems.

Acknowledgements. I am grateful to Alex Andoni and Ilya Razenshteyn for encouraging me to work on the question that is addressed here. I also thank Gideon Schechtman for helpful discussions.

2. Proof of Theorem 1

Modulo the use of a theorem about nonlinear spectral gaps which is a main result of [Nao14], our proof of Theorem 1 is not long. We rely here on an argument that perturbs any finitedimensional normed space (by complex interpolation with its distance ellipsoid) so as to make the result of [Nao14] become applicable, and we proceed to show that by optimizing over the size of the perturbation one can deduce the desired dimensionality-reduction lower bound. This idea is the main conceptual contribution of the present work, and we derive an additional application of it to embedding theory in Section 3 below. We begin with an informal overview of this argument.

2.1. Overview. The precursors of our approach are the works [LN04] and [LMN05] about the impossibility of dimensionality reduction in ℓ_{1} and ℓ_{∞}, respectively. It was shown in [LN04] (respectively [LMN05]) that a certain n-point metric space �_{1} (respectively �_{∞}) does not admit a low-distortion embedding into X = ℓ_{1}^{k} (respectively X = ℓ_{∞}^{k}) with k small, by arguing that if k were indeed small then there would be a normed space Y that is “close” to X, yet any embedding of �_{1} (respectively �_{∞}) into Y incurs large distortion. This leads to a contradiction, provided that the assumed embedding of �_{1} (respectively �_{∞}) into X had sufficiently small distortion relative to the closeness of Y to X. In the setting of [LN04, LMN05], there is a natural one-parameter family of normed spaces that tends to X, namely the spaces ℓ_{p}^{k} with p → 1 or p → ∞, respectively, and indeed the space Y is taken to be an appropriate member of this family. For a general normed space X, it is a priori unclear how to perturb it so as to implement this strategy. Moreover, the arguments of [LN04, LMN05] rely on additional special properties of the specific normed spaces in question that hinder their applicability to general normed spaces: The example of [LN04] is unsuited to the question that we study here because it was shown in [KLMN05] that in fact dim_{D}(�_{1}) ≲ log n for some D = O(1)^{2}; and, the proof in [LMN05] of the non-embeddability of �_{∞} into Y is based on a theorem of Matoušek [Mat97] whose proof relies heavily on the coordinate structure of Y = ℓ_{p}^{k}. We shall overcome the former difficulty by using the complex interpolation method to perturb X, and we shall overcome the latter difficulty by invoking the theory of nonlinear spectral gaps.

2Specifically, the space considered in [LN04] was shown in [KLMN05] to embed with distortion O(1) into ℓ_{∞}^{O(log n)}, and by [Rab08] it even embeds with average distortion O(1) into the real line.

Suppose that (X, ∥ · ∥) is a finite-dimensional normed space. The perturbative step of our argument considers the Hilbert space H whose unit ball is an ellipsoid that is closest to the unit ball of X, i.e., a distance ellipsoid of X; see Section 2.2 below. We then use the complex interpolation method (see Section 2.4.3 below) to obtain a one-parameter family of normed spaces {[X_{ℂ}, H_{ℂ}]_{θ}}_{θ∈[0,1]} that intertwines the complexifications (see Section 2.4.2 below) of X and H, respectively. These intermediate spaces will serve as a proxy for the one-parameter family {ℓ_{p}^{n}}_{p∈[1,∞]} that was used in [LMN05]. In order to see how they fit into this picture we briefly recall the argument of [LMN05].

Suppose that G = ([n], E_{G}) is a O(1)-regular graph with λ_{2}(G) = 1 − Ω(1) (i.e., an expander). In [LMN05, Proposition 4.1] it was shown that for every D ⩾ 1 and k ∈ ℕ, if ([n], d_{G}) embeds with distortion D into ℓ_{∞}^{k}, then necessarily k ≳ n^{c/D} for some universal constant c > 0. This is so because Matoušek proved in [Mat97] that for any p ∈ [1, ∞), any embedding of ([n], d_{G}) into ℓ_{p} incurs distortion at least η(log n)/p, where η > 0 is a universal constant. The norms on ℓ_{∞}^{k} and ℓ_{log k}^{k} are within a factor of e of each other, so it follows that D ⩾ η(log n)/(e log k), i.e., k ⩾ n^{η/(eD)}.

The reason for the distortion lower bound of [Mat97] that was used above is that [Mat97] shows that there exists a universal constant C > 0 such that for every p ⩾ 1 we have

∀ t_{1}, …, t_{n} ∈ ℝ,  \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} |t_{i} − t_{j}|^{p} ⩽ \frac{(Cp)^{p}}{|E_{G}|} ∑_{\{i,j\}∈E_{G}} |t_{i} − t_{j}|^{p}.  (6)

The proof of (6) relies on the fact that the case p = 2 of (6) is nothing more than the usual Poincaré inequality that follows through elementary linear algebra from the fact that λ_{2}(G) is bounded away from 1, combined with an extrapolation argument that uses elementary inequalities for real numbers (see also the expositions in [BLMN05, NS11]). By summing (6) over coordinates we deduce that

∀ x_{1}, …, x_{n} ∈ ℓ_{p},  (\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{p}^{p})^{\frac{1}{p}} ≲ p(\frac{1}{|E_{G}|} ∑_{\{i,j\}∈E_{G}} ∥x_{i} − x_{j}∥_{p}^{p})^{\frac{1}{p}} .  (7)

This implies that any embedding of ([n], d_{G}) into ℓ_{p} incurs average distortion at least a constant multiple of (log n)/p via the same reasoning as the one that preceded Corollary 2.

The reliance on coordinate-wise inequalities in the derivation of (7) is problematic when it comes to the need to treat a general finite-dimensional normed space (X, | · ∥). This “scalar” way of reasoning also leads to the fact that in (7) the ℓ_{p} norm is raised to the power p. Since, even in the special case X = ℓ_{p}^{k}, (7) is applied in the above argument when p = log dim(X), this hinders our ability to deduce an estimate such as the conclusion (1) of Theorem 1.

To overcome this obstacle, we consider a truly nonlinear (quadratic) variant of (7) which is known as a nonlinear spectral-gap inequality. See Section 2.3 below for the formulation of this concept, based on a line of works in metric geometry that has been more recently investigated systematically in [MN13b, MN14, Nao14, MN15]. Our main tool is a result of [Nao14], which is quoted as Theorem 9 below. It provides an estimate in the spirit of (7) for n-tuples of vectors in each of the complex interpolation spaces {[X_{ℂ}, H_{ℂ}]_{θ}}_{θ∈(0,1]}, in terms of the parameter θ and the p-smoothness constant of the normed space [X_{ℂ}, H_{ℂ}]_{θ} (see Section 2.4.1 below for the relevant definition). We then implement the above perturbative strategy by estimating the closeness of X to a subspace of [X_{ℂ}, H_{ℂ}]_{θ}, and optimizing over the auxiliary interpolation parameter θ.

While the result of [Nao14] that we use here is substantial, we encourage readers to examine its proof rather than relying on it as a “black box,” because we believe that this proof is illuminating and accessible to non-experts. Specifically, the proof in [Nao14] of Theorem 9 below relies on Ball’s notion of Markov type [Bal92] p through the martingale method of [NPSS06], in combination with complex interpolation and a trick of V. Lafforgue that was used by Pisier in [Pis10]. It is interesting to observe that here we use the fact that the bound that is obtained in [Nao14] depends on the p-smoothness constant of [X_{ℂ}, H_{ℂ}]_{θ}, but it contains no other dependence on p. Since in our final optimization over θ we take p to be very close to 1, we can’t allow for an implicit dependence on p that is unbounded as p → 1. Such a p-independent bound is indeed obtained in [Nao14], but unlike the present application, it was a side issue in [Nao14], where only the case p = 2 was used.

2.2. Distance ellipsoids. Recall that given d ∈ [1, ∞), a Banach space (X, ∥ · ∥) is said to be d-isomorphic to a Hilbert space if it admits a scalar product ⟨·, ·⟩ : X × X → ℝ, such that if we denote its associated Hilbertian norm by |x| = \sqrt{⟨x, x⟩}, then

∀ x ∈ X,  |x| ⩽ ∥x∥ ⩽ d|x|.  (8)

The (Banach–Mazur) Euclidean distance of X, denoted d_{X} ∈ [1, ∞), is then defined to be the infimum over those d ∈ [1, ∞) for which (8) holds true. If X is not d-isomorphic to a Hilbert space for any d ∈ [1, ∞), then we write d_{X} = ∞. If X is finite-dimensional, then John’s theorem [Joh48] asserts that d_{X} ⩽ \sqrt{dim(X)} (and, in many settings asymptotically better bounds on d_{X} in terms of dim(X) are known; see [MW78, TJ89]). By a standard compactness argument, if X is finitedimensional, then the infimum in the definition of d_{X} is attained. In that case, the unit ball of the Hilbertian norm | · |, i.e., the set {x ∈ X : |x| ⩽ 1}, is commonly called a distance ellipsoid of X. Note that the distance ellipsoid need not be unique; see [Pra02] for more on this topic.

2.3. Nonlinear spectral gaps. Suppose that (�, d_{�} ) is a metric space, n ∈ ℕ and p ∈ (0, ∞). Following [MN14], the (reciprocal of) the nonlinear spectral gap with respect to d_{�}^{p} of a symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ), denoted γ(A, d_{�}^{p} ), is the smallest γ ∈ (0, ∞) such that

∀ x_{1}, …, x_{n} ∈ �, \frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} d_{�} (x_{i}, x_{j})^{p} ⩽ \frac{γ}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}d_{�} (x_{i}, x_{j})^{p}.

We refer to [MN14] for an extensive discussion of this notion; it suffices to state here that the reason for this nomenclature is that if we denote the standard metric on the real line by d_{ℝ} (i.e., d_{ℝ}(s, t) = |s−t| for every s, t ∈ ℝ), then it is straightforward to check that γ(A, d_{ℝ}^{2}) = 1/(1−λ_{2}(A)).

In general, nonlinear spectral gaps can differ markedly from the usual (reciprocal of) the gap in the (linear) spectrum, though [Nao14] is devoted to an investigation of various settings in which one can obtain comparison inequalities for nonlinear spectral gaps when the underlying metric is changed. Estimates on γ(A, d_{�}^{p} ) have a variety of applications in metric geometry, and here we establish their relevance to dimensionality reduction. Specifically, we shall derive below the following result, which will be shown to imply Theorem 1.

Theorem 6 (Nonlinear spectral gap for Hilbert isomorphs). Fix n ∈ ℕ and a symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ). Then for every Banach space (X, ∥ · ∥) with d_{X} < ∞, we have

γ(A, ∥ · ∥^{2}) ≲ \{ \begin{matrix}\frac{d_{X}^{2}}{1−λ_{2}(A)} & if d_{X} \sqrt{1 − λ_{2}(A)} ⩽ e, \\ (\frac{log(d_{X} \sqrt{1−λ_{2}(A)})}{1−λ_{2}(A)})2 & if d_{X} \sqrt{1 − λ_{2}(A)} > e. \end{matrix}  (9)

Proof of Theorem 1 assuming Theorem 6. We claim that (9) implies the following simpler bound.

γ(A, ∥ · ∥^{2}) ≲ (\frac{log (d_{X} \sqrt{2})}{1 − λ_{2}(A)})^{2} .  (10)

Indeed, if d_{X} \sqrt{1 − λ_{2}(A)} > e, then the right hand side of (10) is at least the right hand side of (9) due to the fact that, since A is symmetric and stochastic, λ_{2}(A) ⩾ −1, so that \sqrt{1 − λ_{2}(A)} ⩽ \sqrt{2}.

On the other hand, if d_{X} \sqrt{1 − λ_{2}(A)} ⩽ e then d_{X}^{2}/(1 − λ_{2}(A)) ⩽ e^{2}/(1 − λ_{2}(A))^{2}, which is at most a universal constant multiple of the right hand side of (10) because d_{X} ⩾ 1.

By the definition of γ(A, ∥ · ∥^{2}), it follows from (10) that there exists a universal constant α > 0 such that for every x_{1}, …, x_{n} ∈ X we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥^{2} ⩽ α (\frac{log (d_{X} \sqrt{2})}{1 − λ_{2}(A)})^{2} · \frac{1}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥^{2}.

This estimate simplifies to give

d_{X} ⩾ \frac{1}{\sqrt{2}} exp (\frac{1 − λ_{2}(A)}{\sqrt{αn}}(\frac{∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥^{2}}{∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥x_{i} − x_{j}∥^{2}} )^{\frac{1}{2}} ) .  (11)

The desired estimate (1) (with C = 2/\sqrt{α}) now follows because d_{X} ⩽ \sqrt{dim(X)} by [Joh48]. □

Remark 7. Suppose that G = ([n], E_{G}) is a Cayley graph of a finite group such that λ_{2}(G) = 1−Ω(1). The metric space ([n], d_{G}) embeds with distortion diam(G) into ℓ_{2}^{n−1} by considering any bijection between [n] and the vertices of the n-simplex. There is therefore no a priori reason why it wouldn’t be possible to embed ([n], d_{G}) with distortion O(1) into some normed space X whose Banach–Mazur distance from a Hilbert space is at least a sufficiently large multiple of diam(G). But this is not so if diam(G) is sufficiently large. Indeed, recalling Remark 5, it follows from (11) that any embedding of ([n], d_{G}) into X incurs distortion that is at least a universal constant multiple of diam(G)/ log(2d_{X}). Thus, even if we allow d_{X} to be as large as diam(G)^{O(1)}, then any embedding of ([n], d_{G}) into X incurs distortion that is at least a universal constant multiple of diam(G)/ log diam(G). Also, if diam(G) ≳ log n (e.g., if G has bounded degree) then this means that any embedding of ([n], d_{G}) into X incurs distortion that is at least a universal constant multiple of (log n)/ log(2d_{X}) and, say, even if we allow d_{X} to be as large as (log n)^{O(1)}, then any embedding of ([n], d_{G}) into X incurs distortion that is at least a universal constant multiple of (log n)/ log log n.

2.4. Proof of Theorem 6. We have seen that in order to prove Theorem 1 it suffices to prove Theorem 6. In order to do so, we shall first describe several ingredients that appear in its proof.

2.4.1. Uniform convexity and smoothness. Suppose that (X, ∥·∥) is a normed space and fix p, q > 0 satisfying 1 ⩽ p ⩽ 2 ⩽ q. Following Ball, Carlen and Lieb [BCL94], the p-smoothness constant of X, denoted 𝒮_{p}(X), is the infimum over those S > 0 such that

∀ x, y ∈ X,  ∥x + y∥^{p} + ∥x − y∥^{p} ⩽ 2∥x∥^{p} + 2S^{p}∥y∥^{p}.  (12)

(If no such S exists, then define 𝒮_{p}(X) = ∞.) By the triangle inequality we always have 𝒮_{1}(X) = 1. The q-convexity constant of X, denoted 𝒦_{q}(X), is the infimum over those K > 0 such that

∀ x, y ∈ X, 2∥x∥^{q} + \frac{2}{K^{q}} ∥y∥^{q} ⩽ ∥x + y∥^{q} + ∥x − y∥^{q}.

(As before, if no such K exists, then define 𝒦_{q}(X) = ∞.) We refer to [BCL94] for the relation of these parameters to more traditional moduli of uniform convexity and smoothness that appear in the literature. It is beneficial to work with the quantities 𝒮_{p}(X), 𝒦_{q}(X) rather than the classical moduli because they are well-behaved with respect to basic operations, an example of which is the duality 𝒦_{p/(p−1)}(X^{∗}) = 𝒮_{p}(X), as shown in [BCL94]. Another example that is directly relevant to us is their especially clean behavior under complex interpolation, as derived in Section 2.4.3 below.

2.4.2. Complexification. All of the above results were stated for normed spaces over the real numbers, but in the ensuing proofs we need to consider normed spaces over the complex numbers. We do so through the use of the standard notion of complexification. Specifically, for every normed space (X, ∥ · ∥_{X}) over ℝ one associates as follows a normed space (X_{ℂ}, ∥ · ∥_{X_{ℂ}}) over ℂ. The underlying vector space is X_{ℂ} = X × X, which is viewed as a vector space over ℂ by setting (α + βi)(x, y) = (αx − βy, βx + αy) for every α, β ∈ ℝ and x, y ∈ X. The norm on X_{ℂ} is given by

∀ x, y ∈ X,  ∥(x, y)∥_{X_{ℂ}} = (\frac{1}{π} ∫_{0}^{2π} ∥(cos θ)x − (sin θ)y∥_{X}^{2} dθ)^{\frac{1}{2}} .  (13)

The normalization in (13) ensures that x ↦ (x, 0) is an isometric embedding of X into X_{ℂ}. It is straightforward to check that for every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have γ(A, ∥ · ∥_{X}^{2}) = γ(A, ∥ · ∥_{X_{ℂ}}^{2}). Also, 𝒮_{2}(X_{ℂ}) = 𝒮_{2}(X) and 𝒦_{2}(X_{ℂ}) = 𝒦_{2}(X). When p ∈ (1, 2) and q ∈ (2, ∞) we have 𝒮_{p}(X_{ℂ}) ≍ 𝒮_{p}(X) and 𝒦_{q}(X_{ℂ}) ≍ 𝒦_{q}(X); if one were to allow the implicit constants in these asymptotic equivalences to depend on p, q then this follows from the results of [FP74, Fig76, BCL94], and the fact that these constants can actually be taken to be universal follows from carrying out the relevant arguments with more care, as done in [Nao12b, MN14] (see specifically Lemma 6.3 and Corollary 6.4 of [MN14]). Finally, we have d_{X_{ℂ}} = d_{X}.

2.4.3. Complex interpolation. We very briefly recall Calderón’s vector-valued complex interpolation method [Cal64]; see Chapter 4 of the monograph [BL76] for an extensive treatment. Two complex Banach spaces (Y, ∥ · ∥_{Y}), (Z, ∥ · ∥_{Z}) are said to be compatible if they are both linearly embedded into a complex linear space W with Y + Z = W. The space W is a complex Banach space under the norm ∥w∥_{W} = inf{∥y∥_{Y} + ∥z∥_{Z} : (y, z) ∈ Y × Z and y + z = w}. Let � (Y, Z) denote the space of all bounded continuous functions ψ : {ζ ∈ ℂ : 0 ⩽ ℜ(ζ) ⩽ 1} → W that are analytic on {ζ ∈ ℂ : 0 < ℜ(ζ) < 1}, such that for all t ∈ ℝ we have f(ti) ∈ Y and f(1 + ti) ∈ Z, the mappings t ↦ f(ti) and t ↦ f(1 + ti) are continuous relative to the norms ∥ · ∥_{Y} and ∥ · ∥_{Z}, respectively, and lim_{|t|→∞} ∥f(ti)∥_{Y} = lim_{|t|→∞} ∥f(1 + ti)∥_{Z} = 0. To each θ ∈ [0, 1] one associates a Banach space [Y, Z]_{θ} as follows. The underlying vector space is {ψ(θ) : ψ ∈ � (Y, Z)}, and the norm of w ∈ [Y, Z]_{θ} is given by ∥w∥_{[Y,Z]_{θ}} = inf_{{ψ∈� (Y,Z): ψ(θ)=w}} max{sup_{t∈ℝ} ∥ψ(ti)∥_{Y} , sup_{t∈ℝ} ∥ψ(1+ti)∥_{Z}}. This turns [Y, Z]_{θ} into a Banach space. By [BL76, Theorem 4.2.1] we have [Y, Y]_{θ} = Y for all θ ∈ [0, 1]. Also, by [BL76, Theorem 4.2.1], if Y ∩Z is dense in both Y and Z, then we have [Y, Z]_{0} = Y, [Y, Z]_{1} = Z.

Calderón’s vector-valued version [Cal64] of the Riesz–Thorin theorem [Rie27, Tho48] asserts that if (Y, ∥ · ∥_{Y}), (Z, ∥ · ∥_{Z}) and (U, ∥ · ∥_{U}), (V, ∥ · ∥_{V}) are two compatible pairs of complex Banach spaces and T : Y ∩Z → U ∩V is a linear operator that extends to a bounded linear operator from (Y, ∥·∥_{Y}) to (U, ∥ · ∥_{U}) and from (Z, ∥ · ∥_{Z}) to (V, ∥ · ∥_{V}), then the following operator norm bounds hold true.

∀ θ ∈ [0, 1],  ∥T ∥_{[Y,Z]_{θ} →[U,V]_{θ}} ⩽ ∥T ∥_{Y →U}^{1−θ}∥T ∥_{Z→V}^{θ} .  (14)

The ensuing proof of Theorem 6 uses the interpolation inequality (14) four times (one of which is within the proof of a theorem that we shall quote from [Nao14]; see Theorem 9 below). We shall now proceed to derive some preparatory estimates that will be needed in what follows.

For every p ⩾ 1, every complex Banach space (Z, ∥ · ∥_{Z}), and every weight ω : {1, 2} → [0, ∞) on the 2-point set {1, 2}, we denote (as usual) by L_{p}(ω; Z) the space Z × Z equipped with the norm that is given by setting ∥(a, b)∥_{L_{p}(ω;Z)}^{p} = ω(1)∥a∥_{Z}^{p} + ω(2)∥b∥_{Z}^{p} for every a, b ∈ Z.

If (Y, ∥ · ∥_{Y}), (Z, ∥ · ∥_{Z}) is a compatible pair of complex Banach spaces then by Calderón’s vectorvalued version of Stein’s interpolation theorem [Ste56, Theorem 2] (see part(i) of §13.6 in [Cal64] or Theorem 5.6.3 in [BL76]), for every p, q ∈ [1, ∞], θ ∈ [0, 1] and ω, τ : {1, 2} → [0, ∞) we have

[L_{p}(ω; Y), L_{q}(τ; Z)] _{θ} = L_{r}((ω^{\frac{1−θ}{p}} τ^{\frac{θ}{q}} )^{r}; [Y, Z]_{θ}), where r = \frac{pq}{θp + (1 − θ)q} .  (15)

The equality in (15) is in the sense of isometries, i.e., the norms on both sides coincide.

Suppose that p_{1}, p_{2} ∈ [1, 2] and that the smoothness constants 𝒮_{p_{1}}(Y), 𝒮_{p_{2}}(Z) are finite. Fix S_{1} > 𝒮_{p_{1}}(Y) and S_{2} > 𝒮_{p_{2}}(Z). Then by (12) we have

∀ y_{1}, y_{2} ∈ Y,  ∥y_{1} + y_{2}∥_{Y}^{p_{1}} + ∥y_{1} − y_{2}∥_{Y}^{p_{1}} ⩽ 2∥y_{1}∥_{Y}^{p_{1}} + 2S_{1}^{p_{1}}∥y_{2}∥_{Y}^{p_{1}},  (16)

and

∀ z_{1}, z_{2} ∈ Z, ∥z_{1} + z_{2}∥_{Z}^{p_{2}} + ∥z_{1} − z_{2}∥_{Z}^{p_{2}} ⩽ 2∥z_{1}∥_{Z}^{p_{2}} + 2S_{2}^{p_{2}}∥z_{2}∥_{Z}^{p_{2}}. (17)

For every S > 0 and p ⩾ 1 define ω(S, p) : {1, 2} → (0, ∞) by ω(S, p)(1) = 2 and ω(S, p)(2) = 2S^{p}. Also, denote the constant function 1_{{1,2}} by τ : {1, 2} → (0, ∞), i.e., τ(1) = τ(2) = 1. With this notation, if we consider the linear operator T : (Y + Z) × (Y + Z) → (Y + Z) × (Y + Z) that is given by setting T (w_{1}, w_{2}) = (w_{1} + w_{2}, w_{1} − w_{2}) for every w_{1}, w_{2} ∈ Y + Z, then

∥T ∥_{L_{p_{1}}(ω(S_{1},p_{1});Y)→L_{p_{1}}(τ;Y)} ⩽^{(16)} 1  and  ∥T ∥_{L_{p_{2}}(ω(S_{2},p_{2});Z)→L_{p_{2}}(τ;Z)} ⩽^{(17)} 1.  (18)

Denoting r = p_{1}p_{2}/(θp_{1} + (1 − θ)p_{2}), observe that ω(S_{1}, p_{1})^{(1−θ)r/p_{1}}ω(S_{2}, p_{2})^{θr/p_{2}} = ω(S_{1}^{1−θ}S_{2}^{θ}, r). Hence, by (15) we have [L_{p_{1}}(ω(S_{1}, p_{1}); Y), L_{p_{2}}(ω(S_{2}, p_{2}); Z)]_{θ} = L_{r}(ω(S_{1}^{1−θ}S_{2}^{θ}, r); [Y, Z]_{θ}) and also [L_{p_{1}}(τ; Y); L_{p_{2}}(τ; Z)]_{θ} = L_{r}(τ, [Y, Z]_{θ}). In combination with (14) and (18), these identities imply that the norm of T as an operator from L_{r}(ω(S_{1}^{1−θ}S_{2}^{θ}, r); [Y, Z]_{θ}) to L_{r}(τ, [Y, Z]_{θ}) is at most 1. In other words, every w_{1}, w_{2} ∈ [Y, Z]_{θ} satisfy

∥w_{1} + w_{2}∥_{[Y,Z]_{θ}}^{r} + ∥w_{1} − w_{2}∥_{[Y,Z]_{θ}}^{r} ⩽ 2∥w_{1}∥_{[Y,Z]_{θ}}^{r} + 2(S_{1}^{1−θ}S_{2}^{θ})^{r}∥w_{2}∥_{[Y,Z]_{θ}}^{r}.

Since S_{1} and S_{2} can be arbitrarily close to 𝒮_{p_{1}}(Y) and 𝒮_{p_{2}}(Z), respectively, we conclude that

𝒮_{\frac{p_{1}p_{2}}{θp_{1}+(1−θ)p_{2}}} ([Y, Z]_{θ}) ⩽ 𝒮_{p_{1}}(Y)^{1−θ}𝒮_{p_{2}}(Z)^{θ}.  (19)

By an analogous argument, if q_{1}, q_{2} ⩾ 2 and the convexity constants 𝒦_{q_{1}}(Y), 𝒦_{q_{2}}(Z) are finite, then

𝒦_{\frac{q_{1}q_{2}}{θq_{1}+(1−θ)q_{2}}} ([Y, Z]_{θ}) ⩽ 𝒦_{q_{1}}(Y)^{1−θ}𝒦_{q_{2}}(Z)^{θ}.  (20)

Remark 8. If one considers the traditional moduli of uniform convexity and smoothness (see e.g. [LT79] for the definitions), then interpolation statements that are analogous to (19), (20) are an old result of Cwikel and Reisner [CR82], with the difference that [CR82] involves implicit constants that depend on p_{1}, p_{2}, q_{1}, q_{2}. By [BCL94], this statement of [CR82] yields the estimates (19), (20) with additional factors in the right hand side that depend on p_{1}, p_{2}, q_{1}, q_{2}. For our present purposes, i.e., for the proof of Theorem 6, it is important to obtain universal constants here. We believe that by carrying out the proofs in [CR82] with more care this could be achieved, but by working instead with the quantities 𝒮_{p}(·), 𝒦_{q}(·) through the above simple (and standard) interpolation argument, we circumvented the need to do this and obtained the clean interpolation statements (19), (20).

Next, suppose that (X, ∥·∥) is a Banach space over ℝ with d_{X} < ∞. Fix d > d_{X} and a Hilbertian norm | · | : X → [0, ∞) that satisfies (8). Denote by H the Hilbert space that is induced by | · |. Consider the complexifications X_{ℂ} and H_{ℂ}. Observe that by (13) and (8) we have

∀ x, y ∈ X,  ∥(x, y)∥_{H_{ℂ}} = \sqrt{|x|^{2} + |y|^{2}} and ∥(x, y)∥_{H_{ℂ}} ⩽ ∥(x, y)∥_{X_{ℂ}} ⩽ d∥(x, y)∥_{H_{ℂ}}. (21)

Since X_{ℂ} and H_{ℂ} are isomorphic Banach space with the same underlying vector space (over ℂ), they are a compatible, and therefore for every θ ∈ [0, 1] we can consider the complex interpolation space [H_{ℂ}, X_{ℂ}]_{θ}. The formal identity operator I_{X×X} : X × X → X × X satisfies

∥I_{X×X}∥_{X_{ℂ}→X_{ℂ}} ⩽ 1, ∥I_{X×X}∥_{H_{ℂ}→H_{ℂ}} ⩽ 1, ∥I_{X×X}∥_{X_{ℂ}→H_{ℂ}} ⩽ 1, ∥I_{X×X}∥_{H_{ℂ}→X_{ℂ}} ⩽ d. (22)

The first two inequalities in (22) are tautological, and the final two inequalities in (22) are a consequence of the inequalities in (21). Hence,

∥I_{X×X}∥_{[X_{ℂ},H_{ℂ}]_{θ} →X_{ℂ}} = ∥I_{X×X}∥_{[X_{ℂ},H_{ℂ}]_{θ} →[X_{ℂ},X_{ℂ}]_{θ}} ⩽^{(14)} ∥I_{X×X}∥_{X_{ℂ}→X_{ℂ}}^{1−θ}∥I_{X×X}∥_{H_{ℂ}→X_{ℂ}}^{θ} ⩽^{(22)} d^{θ},

and

∥I_{X×X}∥_{X_{ℂ}→[X_{ℂ},H_{ℂ}]_{θ}} = ∥I_{X×X}∥_{[X_{ℂ},X_{ℂ}]_{θ} →[X_{ℂ},H_{ℂ}]_{θ}} ⩽^{(14)} ∥I_{X×X}∥_{X_{ℂ}→X_{ℂ}}^{1−θ}∥I_{X×X}∥_{X_{ℂ}→H_{ℂ}}^{θ} ⩽^{(22)} 1.

These two estimates can be restated as follows.

∀ x, y ∈ X,  ∥(x, y)∥_{[X_{ℂ},H_{ℂ}]_{θ}} ⩽ ∥(x, y)∥_{X_{ℂ}} ⩽ d^{θ}∥(x, y)∥_{[X_{ℂ},H_{ℂ}]_{θ}}.  (23)

In what follows, we will use crucially the following theorem, which relates nonlinear spectral gaps to complex interpolation and uniform smoothness; this result appears in [Nao14] as Corollary 4.7.

Theorem 9. Suppose that (�, ∥ · ∥_{�} ) and (Z, ∥ · ∥_{Z}) are a compatible pair of complex Banach spaces, with (�, ∥·∥_{�} ) being a Hilbert space. Suppose that q ∈ [1, 2] and θ ∈ (0, 1]. For every n ∈ ℕ and every symmetric stochastic matrix A ∈ M_{n}(ℝ) we have

γ (A, ∥ · ∥_{[Z,�]_{θ}}^{2} ) ≲ \frac{𝒮_{q} ([Z, �]_{θ}) ^{2}}{θ^{\frac{2}{q}} (1 − λ_{2}(A))^{\frac{2}{q}}} .  (24)

We note in passing that in [Nao14] (specifically, in the statement of [Nao14, Theorem 4.5]) we have the following misprint: (24) is stated there for the transposed interpolation space [�, X]_{θ} rather than the correct space [X, �]_{θ} as above. This misprint is not confusing when one reads [Nao14] in context rather the statement of [Nao14, Theorem 4.5] in isolation (e.g., clearly (24) should not deteriorate as the interpolation space approaches the Hilbert space �). Also, the proof itself in [Nao14] deals with the correct interpolation space [X, �]_{θ} throughout (see equation (4.14) in [Nao14]).

2.4.4. Completion of the proof of Theorem 6. Since for every Banach space (X, ∥ · ∥) we have 𝒮_{1}(X) = 1, Theorem 6 is the special case p = 1 of the following more refined theorem.

Theorem 10. Fix p ∈ [1, 2] and suppose that (X, ∥ · ∥) is a Banach space satisfying d_{X} < ∞ and 𝒮_{p}(X) < ∞. For every n ∈ ℕ and every symmetric stochastic matrix A = (a_{ij}) ∈ M_{n}(ℝ), we have

γ(A, ∥ · ∥^{2}) ≲ \{ \begin{matrix}\frac{d_{X}^{2}}{1−λ_{2}(A)} & if d_{X}^{p} (1 − λ_{2}(A))^{1− \frac{p}{2}} ⩽ e𝒮_{p}(X)^{p}, \\ \frac{𝒮_{p}(X)^{2}}{(1−λ_{2}(A))^{\frac{2}{p}}} (log (^{\frac{d_{X}^{p}(1−λ_{2}(A))^{1− \frac{p}{2}}}{𝒮_{p}(X)^{p}}} ))^{\frac{2}{p}} & if d_{X}^{p} (1 − λ_{2}(A))^{1− \frac{p}{2}} ⩾ e𝒮_{p}(X)^{p}. \end{matrix} (25)

Proof. Fix d > d_{X} and θ ∈ (0, 1]. Consider a Hilbertian norm | · | : X → [0, ∞) that satisfies (8) and denote by H the Hilbert space that is induced by | · |. As we explained in Section 2.4.2, the complexification X_{ℂ} satisfies 𝒮_{p}(X_{ℂ}) ≍ 𝒮_{p}(X). Also, by the parallelogram identity, the complex Hilbert space H_{ℂ} satisfies 𝒮_{2}(H_{ℂ}) = 1. Hence, by (19) with Y = X_{ℂ}, Z = H_{ℂ}, p_{1} = p and p_{2} = 2,

𝒮_{\frac{2p}{θp+2(1−θ)}} ([X_{ℂ}, H_{ℂ}]_{θ}) ⩽ 𝒮_{p}(X_{ℂ})^{1−θ} ≲ 𝒮_{p}(X)^{1−θ}.

We may therefore apply Theorem 9 with q = (2p)/(θp + 2(1 − θ)) to deduce that

γ (A, ∥ · ∥_{[X_{ℂ},H_{ℂ}]_{θ}}^{2}) ≲ \frac{𝒮_{p}(X)^{2(1−θ)}}{θ^{θ+ \frac{2(1−θ)}{p}} (1 − λ_{2}(A))^{θ+ \frac{2(1−θ)}{p}}} ≍ \frac{𝒮_{p}(X)^{2(1−θ)}}{θ^{\frac{2}{p}} (1 − λ_{2}(A))^{θ+ \frac{2(1−θ)}{p}}} .  (26)

By the definition of γ (A, ∥ · ∥_{[X_{ℂ},H_{ℂ}]_{θ}}^{2}), for every (x_{1}, y_{1}), …, (x_{n}, y_{n}) ∈ X × X we have

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥(x_{i} − x_{j}, y_{i} − y_{j})∥_{[X_{ℂ},H_{ℂ}]_{θ}}^{2} ⩽ \frac{γ (A, ∥ · ∥_{[X_{ℂ},H_{ℂ}]_{θ}}^{2})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥(x_{i} − x_{j}, y_{i} − y_{j})∥_{[X_{ℂ},H_{ℂ}]_{θ}}^{2}.

By (23), this implies that

\frac{1}{n^{2}} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥(x_{i} − x_{j}, y_{i} − y_{j})∥_{X_{ℂ}}^{2} ⩽ \frac{d^{2θ}γ (A, ∥ · ∥_{[X_{ℂ},H_{ℂ}]_{θ}}^{2})}{n} ∑_{i=1}^{n} ∑_{j=1}^{n} a_{ij}∥(x_{i} − x_{j}, y_{i} − y_{j})∥_{X_{ℂ}}^{2}.

Due to (26) and because X is isometric to a subspace of X_{ℂ}, this implies that

∀ θ ∈ (0, 1],  γ(A, ∥ · ∥^{2}) ≲ \frac{d_{X}^{2θ}𝒮_{p}(X)^{2(1−θ)}}{θ^{\frac{2}{p}} (1 − λ_{2}(A))^{θ+ \frac{2(1−θ)}{p}}} .  (27)

If d_{X}^{p} (1 − λ_{2}(A))^{1−p/2} ⩽ e𝒮_{p}(X)^{p}, then by substituting θ = 1 into (27) we obtain the first range of (25). When d_{X}^{p} (1 − λ_{2}(A))^{1−p/2} > e𝒮_{p}(X)^{p} the following value of θ minimizes the right hand side of (27) and belongs to the interval (0, 1].

θ_{opt} =^{def} \frac{1}{log (^{\frac{d_{X}^{p}(1−λ_{2}(A))^{1− \frac{p}{2}}}{𝒮_{p}(X)^{p}}} )}.

A substitution of θ_{opt} into (27) yields an estimate that simplifies to give the second range of (25). □

3. Worst-case to average-case logarithmic improvement of Euclidean distortion

Thus far we used only the case p = 1 of Theorem 10. The purpose of this short section is to establish the following consequence of the case p = 2 of Theorem 10.

Theorem 11. There is a universal constant β > 0 with the following property. Suppose that D ⩾ 1 and let (X, ∥·∥_{X}) be a normed space that embeds with bi-Lipschitz distortion D into a Hilbert space. Then every finite subset of X embeds with average distortion β𝒮_{2}(X)^{3} log(2D) into a Hilbert space.

A qualitative rephrasing of Theorem 11 is the following somewhat curious assertion that is nevertheless quite striking. If X is 2-smooth, then the fact that every finite subset of X admits an embedding into a Hilbert space with a worst-case pairwise requirement (i.e., bi-Lipschitz), automatically implies that every finite subset of X admits an embedding into a Hilbert space with an average-case guarantee that grows at most like the logarithm of the initial bi-Lipschitz distortion. It follows from the proof of [Nao14, Lemma 1.12] that this phenomenon does not hold true under the weaker assumption 𝒮_{p}(X) < ∞ for some p ∈ [1, 2). We do not know the extent to which the bound on the average distortion in Theorem 11 is sharp; it seems likely that the dependence on 𝒮_{2}(X) could be improved here. It is even conceivable that any finite subset of a Banach space X with 𝒮_{2}(X) < ∞ embeds with average distortion Ψ(𝒮_{2}(X)) into a Hilbert space, where Ψ(𝒮_{2}(X)) > 0 is a finite quantity that may depend only on 𝒮_{2}(X). We have no reason to conjecture that this is so, but if it were valid then it would be a remarkable geometric statement. We can show that this does hold true when X is a 2-smooth Banach lattice, as explained in Remark 12 below.

In the proof of Theorem 11 we shall use the following standard notation related to the Lipschitz extension problem. The Lipschitz extension constant of a pair of metric spaces (�, d_{�} ) and (�, d_{�} ), denoted e(�, �), is the infimum over those K ∈ [1, ∞] such that for every Ω ⊆ � and L ∈ (0, ∞), every L-Lipschitz function ϕ : Ω → � admits a (KL)-Lipschitz extension Φ : � → �.

Proof of Theorem 11. By a classical differentiation argument (see e.g. [BL00, Corollary 7.10]), the fact that X embeds with bi-Lipschitz distortion D into a Hilbert space implies that d_{X} ⩽ D. Since (by substituting x = 0 into (12)) we always have 𝒮_{2}(X) ⩾ 1, the conclusion of Theorem (10) implies that for every n ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ(A, ∥ · ∥^{2}) ≲ \frac{𝒮_{2}(X)^{2} log(2D)}{1 − λ_{2}(A)}.  (28)

By Corollary 1.4 in [Nao14], the validity of (28) for every symmetric stochastic matrix A implies that for every x_{1}, …, x_{n} ∈ X there exists a 1-Lipschitz mapping f : {x_{1}, …, x_{n}} → ℓ_{2} such that

( ∑_{i=1}^{n} ∑_{j=1}^{n} ∥f(x_{i}) − f(x_{j})∥_{2}^{2})^{\frac{1}{2}} ≳ \frac{1}{𝒮_{2}(X)\sqrt{log(2D)}}( ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{X}^{2})^{\frac{1}{2}} .  (29)

The estimate (29) is already an assertion that is similar to the conclusion of Theorem 11, except that one is preserving the average of squares of distances rather than the average of the distances themselves. And, the conclusion in (29) is even stronger, with the distortion being at most a constant multiple of 𝒮_{2}(X)\sqrt{log(2D)} rather than the claimed bound of 𝒮_{2}(X)^{3} log(2D).

One can pass from (29) to the usual notion of average distortion by combining the results of Section 7.4 in [Nao14] with the Lipschitz extension theorem of [Bal92, NPSS06]. Specifically, by inequality (7.39) in [Nao14] it follows from the validity of (29) for every n ∈ ℕ and every x_{1}, …, x_{n} ∈ X that there also exists a 1-Lipschitz mapping ϕ : X → ℓ_{2} such that

∑_{i=1}^{n} ∑_{j=1}^{n} ∥ϕ(x_{i}) − ϕ(x_{j})∥_{2} ≳ \frac{1}{e(X, ℓ_{2})𝒮_{2}(X)^{2} log(2D)} ∑_{i=1}^{n} ∑_{j=1}^{n} ∥x_{i} − x_{j}∥_{X}.

Since e(X, ℓ_{2}) ≲ 𝒮_{2}(X) by [NPSS06, Theorem 2.3], this concludes the proof of Theorem 11. □

Remark 12. Suppose that (�, ∥·∥_{�} ) and (Z, ∥·∥_{Z}) are a compatible pair of complex Banach spaces, with (�, ∥ · ∥_{�} ) being a Hilbert space. Suppose also that θ ∈ (0, 1] and that 𝒮_{2}([Z, �]_{θ}) < ∞. Then by Theorem 9 for every n ∈ ℕ, every symmetric stochastic matrix A ∈ M_{n}(ℝ) satisfies

γ (A, ∥ · ∥_{[Z,�]_{θ}}^{2} ) ≲ \frac{𝒮_{2} ([Z, �]_{θ}) ^{2}}{θ (1 − λ_{2}(A))} .

By combining [Nao14, Corollary 1.4] with [Nao14, (7.39)] and [NPSS06, Theorem 2.3], it follows from this that any finite subset of [Z, �]_{θ} embeds into ℓ_{2} with average distortion O(𝒮_{2} ([Z, �]_{θ}) ^{3} /θ).

Suppose next that X is a Banach lattice that satisfies 𝒮_{2}(X) < ∞. An extrapolation theorem of Pisier [Pis79] asserts that there exists θ ∈ (0, 1] and Banach spaces Z, � as above such that the complexification X_{ℂ} is isomorphic to [Z, �]_{θ}. An inspection of Pisier’s proof of this theorem (see also Appendix I in [BL00]), reveals that both θ and the isomorphism constant can be taken to be bounded by a function of 𝒮_{2}(X) alone (with more work it is possible to obtain explicit estimates here, but this is quite tedious and we will not include the argument). It therefore follows from the above discussion that any finite subset of a 2-smooth Banach lattice X embeds with average distortion Ψ(𝒮_{2}(X)) into ℓ_{2}, where Ψ(𝒮_{2}(X)) > 0 is a finite quantity that depends only on 𝒮_{2}(X).

4. Further discussion and open problems

Given D ⩾ 1 and a metric space (�, d), the definition in [LLR95] of the metric dimension dim_{D}(�) can be naturally refined by restricting the potential target spaces into which we wish to embed �. Specifically, suppose that ℱ is a family of finite-dimensional normed spaces. Define dim_{D}(�; ℱ) to be the minimum k ∈ ℕ for which � embeds with distortion D into some X ∈ ℱ of dimension at most k; if no such X ∈ ℱ exists then denote dim_{D}(�; ℱ) = ∞. The quantity dim_{D}(�) is then equal to dim_{D}(�; ℱ) when ℱ consists of all finite-dimensional normed spaces.

The question of estimating dim_{D}(�; ℱ) for various metric spaces � and various families ℱ of finite-dimensional normed spaces encompasses much of the research on dimensionality reduction, though not all of the work on dimensionality reduction belongs to this framework (examples of other directions include restrictions on the embeddings themselves, such as dimensionality reduction via linear mappings [JN10], requiring guarantees that are not necessarily bi-Lipschitz [IN07, ABN11] and complexity theoretic issues [MS10], among others). Notable special cases include ℱ = {ℓ_{2}^{k}}_{k=1}^{∞}, which was studied in [Mat90], or the Johnson–Lindenstrauss lemma [JL84] which asserts that

∀ ε > 0, ∀ n ∈ ℕ,  sup_{\begin{matrix}�⊆ℓ_{2} \\ |�|⩽n \end{matrix}} dim_{1+ε} (�; \{ℓ_{2}^{k}\}_{k=1}^{∞}) ≍_{ε} log n.  (30)

The implicit dependence on ε in (30) was unknown for many years, but it has been very recently determined in [LN16] (up to universal constant factors, and except for a small range of values of ε that tends to 0 as n → ∞); see also the slightly weaker result of Alon [Alo03], as well as the related work of Alon and Klartag [AK16]. These works include examples of methods to prove the impossibility of dimensionality reduction in the almost-isometric Euclidean setting, that differ from the analytic methods that are used here (they rely on linear algebra and certain coding arguments).

Another important example is when ℱ = {ℓ_{1}^{k}}_{k=1}^{∞} and the metric space � is a subset of ℓ_{1}. In this setting, the best-known bounds are that there exist universal constants c, C > 0 for which

∀ D ⩾ 1, ∀ n ∈ ℕ,  n^{\frac{c}{D^{2}}} ⩽ sup_{\begin{matrix}�⊆ℓ_{1} \\ |�|⩽n \end{matrix}} dim_{D} (�; \{ℓ_{1}^{k}\}_{k=1}^{∞}) ⩽ \frac{Cn}{D}.  (31)

The first inequality in (31) is a famous theorem of Brinkman and Charikar [BC05], whose proof devised a clever method for proving dimensionality reduction lower bounds through the use of linear programming; see also [ACNN11]. A different approach to the same lower bound, which we already discussed in Section 2.1, is due to [LN04]. See also the elegant entropy-based approach of Regev [Reg13] to the dimensionality reduction impossibility results of [BC05, ACNN11]. The upper bound in (31) is due to the forthcoming work [ANN16]. Of course, the gap between the bounds in (31) is large, and it would be of great interest to determine the correct asymptotic behavior here.

When ℱ = {ℓ_{p}^{k}}_{k=1}^{∞} for some p ∉ {1, 2, ∞}, remarkably little is known about the asymptotic behavior of the supremum of dim_{D}(�; {ℓ_{p}^{k}}_{k=1}^{∞}) over all � ⊆ ℓ_{p} with |�| ⩽ n. It is a tantalizing longstanding open problem to devise methods to address this question, i.e., for proving either positive results or impossibility results for dimensionality reduction in ℓ_{p}, when p ∉ {1, 2, ∞}.

In the setting of dimensionality reduction for subsets of ℓ_{1} when the target space can be a general normed space, we suspect that the lower bound on dim_{D}(·) of [Mat96] (as well as the bound obtained here) cannot occur for subsets of ℓ_{1}. Specifically, we have the following conjecture.

Conjecture 13. Every n-point subset of ℓ_{1} embeds with distortion O(1) into some normed space of dimension (log n)^{O(1)}.

See also Problem 3.5 in [Mat03], that was stated by Mendel, where it is speculated that one could even obtain a normed space of dimension O(log n) in Conjecture 13. Due to [KLMN05], it is conceivable that one could take the target space to be ℓ_{1}^{k} ⊕ ℓ_{∞}^{k} for some k = O(log n). In the forthcoming work [ANN16], an approach is devised for proving Conjecture (13). Namely, Conjecture (13) is established in [ANN16] under a yet unproven but plausible geometric hypothesis.

We indicated a small part of the extensive literature on dimensionality reduction, as well as a few of the basic questions that remain open. A comprehensive survey would exceed the scope of the present article, so we only state that by combining restrictions on the metric � (e.g. doubling metric spaces, planar graphs, series-parallel graphs, graphs of bounded bandwidth, trees, ultrametrics) with restrictions of the targets ℱ, leads to a rich body of work, as well as fundamental unsolved questions. To the best of our knowledge, we indicated in this section and in the Introduction all of the known methods for proving lower bounds on dimensionality reduction, with the present article contributing another such method. There is great need to obtain new approaches to these issues.

References

[ABN11] I. Abraham, Y. Bartal, and O. Neiman. Advances in metric embedding theory. Adv. Math., 228(6):3026– 3126, 2011.

[ACNN11] A. Andoni, M. S. Charikar, O. Neiman, and H. L. Nguyen. Near linear lower bound for dimension reduction in ℓ_{1}. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, pages 315–323. IEEE Computer Soc., Los Alamitos, CA, 2011. doi:10.1109/FOCS.2011.87.

[AdRRP92] J. Arias-de Reyna and L. Rodríguez-Piazza. Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces. Israel J. Math., 79(1):103–111, 1992.

[AFR85] N. Alon, P. Frankl, and V. Rödl. Geometrical realization of set systems and probabilistic communication complexity. In 26th Annual Symposium on Foundations of Computer Science, pages 277–280. IEEE Computer Society, 1985.

[AK16] N. Alon and B. Klartag. Optimal compression of approximate Euclidean distances, 2016. Preprint, avail-

           able at https://arxiv.org/abs/1610.00239.

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

[ANN16] A. Andoni, A. Naor, and O. Neiman. On isomorphic dimension reduction in ℓ_{1}, 2016. Preprint.

[ANRW16] A. Andoni, A. Nikolov, I. Razenshteyn, and E. Waingarten. Approximate near neighbors for general symmetric norms, 2016. Preprint, available at https://arxiv.org/pdf/1611.06222.

[AR94] N. Alon and Y. Roichman. Random Cayley graphs and expanders. Random Structures Algorithms, 5(2):271–284, 1994.

[Bal92] K. Ball. Markov chains, Riesz transforms and Lipschitz maps. Geom. Funct. Anal., 2(2):137–172, 1992.

[Bal13] K. Ball. The Ribe programme. Astérisque, (352):Exp. No. 1047, viii, 147–159, 2013. Séminaire Bourbaki. Vol. 2011/2012. Exposés 1043–1058.

[BC05] B. Brinkman and M. Charikar. On the impossibility of dimension reduction in l_{1}. J. ACM, 52(5):766–788 (electronic), 2005.

[BCL94] K. Ball, E. A. Carlen, and E. H. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math., 115(3):463–482, 1994.

[BJL^{+}99] S. Bates, W. B. Johnson, J. Lindenstrauss, D. Preiss, and G. Schechtman. Affine approximation of

Lipschitz functions and nonlinear quotients. Geom. Funct. Anal., 9(6):1092–1127, 1999.

[BL76] J. Bergh and J. Löfström. Interpolation spaces. An introduction. Springer-Verlag, Berlin-New York, 1976. Grundlehren der Mathematischen Wissenschaften, No. 223.

[BL00] Y. Benyamini and J. Lindenstrauss. Geometric nonlinear functional analysis. Vol. 1, volume 48 of American Mathematical Society Colloquium Publications. American Mathematical Society, Providence, RI, 2000.

[BLMN05] Y. Bartal, N. Linial, M. Mendel, and A. Naor. On metric Ramsey-type phenomena. Ann. of Math. (2), 162(2):643–709, 2005.

[Bou85] J. Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel J. Math., 52(1-2):46– 52, 1985.

[Bou86] J. Bourgain. The metrical interpretation of superreflexivity in Banach spaces. Israel J. Math., 56(2):222– 230, 1986.

[Cal64] A.-P. Calderón. Intermediate spaces and interpolation, the complex method. Studia Math., 24:113–190, 1964.

[CR82] M. Cwikel and S. Reisner. Interpolation of uniformly convex Banach spaces. Proc. Amer. Math. Soc., 84(4):555–559, 1982.

[Fig76] T. Figiel. On the moduli of convexity and smoothness. Studia Math., 56(2):121–155, 1976.

[FP74] T. Figiel and G. Pisier. Séries aléatoires dans les espaces uniformément convexes ou uniformément lisses. C. R. Acad. Sci. Paris Sér. A, 279:611–614, 1974.

[Fré06] M. Fréchet. Sur quelques points du calcul fonctionnel. Rend. Circ. Mat. Palermo, 22:1–74, 1906.

[HLW06] S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bull. Amer. Math. Soc. (N.S.), 43(4):439–561 (electronic), 2006.

[IN07] P. Indyk and A. Naor. Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms, 3(3):Art. 31, 12, 2007.

[JL84] 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), volume 26 of Contemp. Math., pages 189– 206. Amer. Math. Soc., Providence, RI, 1984.

[JLS87] W. B. Johnson, J. Lindenstrauss, and G. Schechtman. On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces. In Geometrical aspects of functional analysis (1985/86), volume 1267 of Lecture Notes in Math., pages 177–184. Springer, Berlin, 1987. doi:10.1007/BFb0078145.

[JN10] W. B. Johnson and A. Naor. The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. Discrete Comput. Geom., 43(3):542–553, 2010.

[Joh48] F. John. Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187–204. Interscience Publishers, Inc., New York, N. Y., 1948.

[Kal08] N. J. Kalton. The nonlinear geometry of Banach spaces. Rev. Mat. Complut., 21(1):7–60, 2008.

[KLMN05] R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor. Measured descent: a new embedding method for finite metrics. Geom. Funct. Anal., 15(4):839–858, 2005.

[KN06] S. Khot and A. Naor. Nonembeddability theorems via Fourier analysis. Math. Ann., 334(4):821–852, 2006.

[LLR95] N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215–245, 1995.

[LMN05] J. R. Lee, M. Mendel, and A. Naor. Metric structures in L_{1}: dimension, snowflakes, and average distortion. European J. Combin., 26(8):1180–1190, 2005.

[LN04] 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.

[LN16] K. G. Larsen and J. Nelson. Optimality of the Johnson-Lindenstrauss lemma, 2016. Preprint, available

           at https://arxiv.org/abs/1609.02094.

[LPS88] A. Lubotzky, R. Phillips, and P. Sarnak. Ramanujan graphs. Combinatorica, 8(3):261–277, 1988.

[LT79] J. Lindenstrauss and L. Tzafriri. Classical Banach spaces. II, volume 97 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas]. Springer-Verlag, Berlin-New York, 1979. ISBN 3-540-08888-1. Function spaces.

[Mar88] G. A. Margulis. Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators. Problemy Peredachi Informatsii, 24(1):51–60, 1988.

[Mat90] J. Matoušek. Bi-Lipschitz embeddings into low-dimensional Euclidean spaces. Comment. Math. Univ. Carolin., 31(3):589–600, 1990.

[Mat92] J. Matoušek. Note on bi-Lipschitz embeddings into normed spaces. Comment. Math. Univ. Carolin., 33(1):51–55, 1992.

[Mat96] J. Matoušek. On the distortion required for embedding finite metric spaces into normed spaces. Israel J. Math., 93:333–344, 1996.

[Mat97] J. Matoušek. On embedding expanders into l_{p} spaces. Israel J. Math., 102:189–197, 1997.

[Mat02] J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. ISBN 0-387-95373-6. doi:10.1007/978-1-4613-0039-7.

[Mat03] J. Matoušek. Open problems on embeddings of finite metric spaces, 2003. Available at

           http://kam.mff.cuni.cz/~matousek/metrop.ps.

[Mil64] J. Milnor. On the Betti numbers of real varieties. Proc. Amer. Math. Soc., 15:275–280, 1964.

[MN13a] M. Mendel and A. Naor. Markov convexity and local rigidity of distorted metrics. J. Eur. Math. Soc. (JEMS), 15(1):287–337, 2013.

[MN13b] M. Mendel and A. Naor. Spectral calculus and Lipschitz extension for barycentric metric spaces. Anal. Geom. Metr. Spaces, 1:163–199, 2013.

[MN14] M. Mendel and A. Naor. Nonlinear spectral calculus and super-expanders. Publ. Math. Inst. Hautes Études Sci., 119:1–95, 2014.

[MN15] M. Mendel and A. Naor. Expanders with respect to Hadamard spaces and random graphs. Duke Math. J., 164(8):1471–1548, 2015.

[MS10] J. Matoušek and A. Sidiropoulos. Inapproximability for metric embeddings into ℝ^{d}. Trans. Amer. Math. Soc., 362(12):6341–6365, 2010.

[MW78] V. D. Mil′man and H. Wolfson. Minkowski spaces with extremal distance from the Euclidean space. Israel J. Math., 29(2-3):113–131, 1978.

[Nao12a] A. Naor. An introduction to the Ribe program. Jpn. J. Math., 7(2):167–233, 2012.

[Nao12b] A. Naor. On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs. Combin. Probab. Comput., 21(4):623–634, 2012.

[Nao14] A. Naor. Comparison of metric spectral gaps. Anal. Geom. Metr. Spaces, 2:1–52, 2014.

[NPSS06] A. Naor, Y. Peres, O. Schramm, and S. Sheffield. Markov chains in smooth Banach spaces and Gromovhyperbolic metric spaces. Duke Math. J., 134(1):165–197, 2006.

[NR09] I. Newman and Y. Rabinovich. Hard metrics from Cayley graphs of abelian groups. Theory Comput., 5:125–134, 2009.

[NS11] A. Naor and L. Silberman. Poincaré inequalities, embeddings, and wild groups. Compos. Math., 147(5):1546–1572, 2011.

[Ost] M. I. Ostrovskii. Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces, volume 49 of De Gruyter Studies in Mathematics.

[Pis79] G. Pisier. Some applications of the complex interpolation method to Banach lattices. J. Analyse Math., 35:264–281, 1979.

[Pis10] G. Pisier. Complex interpolation between Hilbert, Banach and operator spaces. Mem. Amer. Math. Soc., 208(978):vi+78, 2010.

[Pra02] D. Praetorius. Remarks and examples concerning distance ellipsoids. Colloq. Math., 93(1):41–53, 2002.

[Rab08] Y. Rabinovich. On average distortion of embedding metrics into the line. Discrete Comput. Geom., 39(4):720–733, 2008.

[Reg13] O. Regev. Entropy-based bounds on dimension reduction in L_{1}. Israel J. Math., 195(2):825–832, 2013.

[Rib76] M. Ribe. On uniformly homeomorphic normed spaces. Ark. Mat., 14(2):237–244, 1976.

[Rie27] M. Riesz. Sur les maxima des formes bilinéaires et sur les fonctionnelles linéaires. Acta Math., 49(3-4):465–497, 1927.

[Ste56] E. M. Stein. Interpolation of linear operators. Trans. Amer. Math. Soc., 83:482–492, 1956.

[Tho48] G. O. Thorin. Convexity theorems generalizing those of M. Riesz and Hadamard with some applications. Comm. Sem. Math. Univ. Lund [Medd. Lunds Univ. Mat. Sem.], 9:1–58, 1948.

[Tho65] R. Thom. Sur l’homologie des variétés algébriques réelles. In Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), pages 255–265. Princeton Univ. Press, Princeton, N.J., 1965.

[TJ89] N. Tomczak-Jaegermann. Banach-Mazur distances and finite-dimensional operator ideals, volume 38 of Pitman Monographs and Surveys in Pure and Applied Mathematics. Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1989.

Mathematics Department, Princeton University, Fine Hall, Washington Road, Princeton, NJ 08544-1000, USA

   E-mail address: naor@math.princeton.edu