Metric structures in L_{1}: Dimension, snowflakes, and average distortion

James R. Lee

U.C. Berkeley and Microsoft Research

         jrl@cs.berkeley.edu

Manor Mendel Hebrew University

                                      mendelma@cs.huji.ac.il

Assaf Naor Microsoft Research

                      anaor@microsoft.com

Abstract

We study the metric properties of finite subsets of L_{1}. The analysis of such metrics is central to a number of important algorithmic problems involving the cut structure of weighted graphs, including the Sparsest Cut Problem, one of the most compelling open problems in the field of approximation. We present some new observations concerning the relation of L_{1} to dimension, topology, and Euclidean distortion. In particular, we offer new insights into the four main open problems surrounding the metric structure of L_{1}.

1 Introduction

This paper is devoted to the analysis of metric properties of finite subsets of L_{1}. Such metrics occur in many important algorithmic contexts, and their analysis is key to progress on some fundamental problems. For instance, an O(log n)-approximate max-flow/min-cut theorem proved elusive for many years until, in [15, 2], it was shown to follow from a theorem of Bourgain stating that every metric on n points embeds into L_{1} with distortion O(log n).

The importance of L_{1} metrics has given rise to many problems and conjectures that have attracted a lot of attention in recent years. Four basic problems of this type are as follows.

I. Is there an L_{1} analog of the Johnson-Lindenstrauss dimension reduction lemma [9]?

II. Are all n-point subsets of L_{1} O (\sqrt{log n})-embeddable into Hilbert space?

III. Are all squared-ℓ_{2} metrics O(1)-embeddable into L_{1}?

IV. Are all planar graphs O(1)-embeddable into L_{1}?

Each of these questions has been asked many times before; we refer to [18, 19, 14, 8], in particular. Despite an immense amount of interest and effort, the metric properties of L_{1} have proved quite elusive; hence the name “The mysterious L_{1}” appearing in a survey of Linial at the ICM in 2002 [14]. In this paper, we offer new insights into each of the above problems and touch on some relationships between them.

1.1 Results and techniques

Dimension reduction. In [3], and soon after in [13], it was shown that if the Newman-Rabinovich diamond graph on n vertices α-embeds into ℓ_{1}^{d} then d ≥ n^{Ω(1/α^{2})}. The proof in [3] is based on a linear programming argument, while the proof in [13] uses a geometric argument which reduces the problem to bounding from below the distortion required to embed the diamond graph in ℓ_{p}, 1 < p < 2. These results settle the long standing open problem whether there is an L_{1} analog of the Johnson-Lindenstrauss dimension reduction lemma [9]. (In other words, they show that the answer to problem (I) above is No.). In Section 2, we show that the method of proof in [13] can be used to provide an even more striking counter example to this problem.

A metric space X is called doubling with constant C if every ball in X can be covered by C balls of half the radius. Doubling metrics with bounded doubling constants are widely viewed as low dimensional (see [6, 10] for some practical and theoretical applications of this viewpoint). In fact, they have bounded Assouad dimension (see [7] for the definition). On the other hand, the doubling constant of the diamond graphs is Ω(\sqrt{n}) (where n is the number of points). Based on a fractal construction due to Laakso [11] and the method developed in [13], we prove the following theorem, which shows a strong lower bound on the dimension required to represent uniformly doubling subsets of L_{1}.

Theorem 1.1. There are arbitrarily large n-point subsets X ⊆ L_{1} which are doubling with constant 6 but such that every α-embedding of X into ℓ_{1}^{d} requires d ≥ n^{Ω(1/α^{2})}.

In [12, 6] it was asked whether any subset of ℓ_{2} which is doubling well-embeds into ℓ_{2}^{d} (with bounds on the distortion and the dimension that depend only on the doubling constant). In [6], it was shown that a similar property cannot hold for ℓ_{1}. Our lower bound exponentially strengthens this result.

Planar metrics. The next result addresses problems (III) and (IV). Our motivation was an attempt to generalize the argument in [13] to prove that dimension reduction is impossible in L_{p} for any 1 < p < 2. A natural approach to this problem is to consider the point set used in [3, 13] (namely, a natural realization of the diamond graph, G, in L_{1}) with the metric induced by the L_{p} norm instead of the L_{1} norm. This is easily seen to amount to proving lower bounds on the dimension required to embed the metric space (G, d_{G}^{1/p}) in ℓ_{p}^{d}. Unfortunately, this approach cannot work since we show that, for any planar metric (X, d) and any 0 < ε < 1, the metric space (X, d^{1−ε}) embeds in Hilbert space with distortion O (1/\sqrt{ε}). The proof of this interesting fact is a straightforward application of Assouad’s classical embedding theorem [1] and Rao’s embedding method [23]. The O (1/\sqrt{ε}) upper bound is shown to be tight for every value 0 < ε < 1. The case ε = 1/2 has been previously observed by A. Gupta in his (unpublished) thesis. It follows that any planar metric embeds into squared-ℓ_{2} with O(1) distortion so that a positive solution to problem (III) above implies a positive solution to problem (IV).

Euclidean distortion. Our final result addresses problem (II) stated above (and for more subtle reasons, problem (III)). We show that the answer to this question is positive on average, in the following sense.

Theorem 1.2. For every f_{1}, …, f_{n} ∈ L_{1} there is a linear operator T : L_{1} → L_{2} such that

\frac{1}{(8 log n)^{1/3}} ≤ min_{1≤i<j≤n} (\frac{∥T (f_{i}) − T (f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} )^{2/3} ≤ \frac{1}{\binom{n}{2}} ∑_{1≤i<j≤n} (\frac{∥T (f_{i}) − T (f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} )^{2/3} ≤ 10.

In other words, for any n-point subset in L_{1}, there exists a map into L_{2} such that distances are contracted by at most O(\sqrt{log n}) and the average expansion is O(1). We remark that a different notion of average embedding was recently studied by Rabinovich [22]. In [22] one tries to embed (planar) metrics into the line such that the average distance does not change too much.

The exponent 2/3 above has no significance, and we can actually obtain the same result for any power 1 − ε, ε > 0 (we refer to Section 4 for details). The proof of Theorem 1.2 follows from the following probabilistic lemma, which is implicit in [16]. We believe that this result is of independent interest.

Lemma 1.3. There exists a distribution over linear mappings T : L_{1} → L_{2} such that for every x ∈ L_{1} \ \{0\} the random variable \frac{∥T (x)∥_{2}}{∥x∥_{1}} has density \frac{e^{−1/(4x^{2})}}{x^{2}\sqrt{π}}.

In contrast to Theorem 1.2, we show that problem (II) cannot be resolved positively using linear mappings. Specifically, we show that there are arbitrarily large n-point subsets of L_{1} such that any linear embedding of them into L_{2} incurs distortion Ω(\sqrt{n}). As a corollary we settle the problem left open by Charikar and Sahai in [4], whether linear dimension reduction is possible in L_{p}, p ∉ {1, 2}. The case p = 1 was proved in [4] via linear programming techniques, and it seems impossible to generalize their lower bound to arbitrary L_{p}. We show that there are arbitrarily large n-point subsets X ⊆ L_{p} (namely, the same point set used in [4] to handle the case p = 1), such that any linear embedding of X into ℓ_{p}^{d} incurs distortion Ω [(n/d)^{|1/p−1/2|}], thus linear dimension reduction is impossible in any L_{p}, p ≠ 2. Additionally, we show that there are arbitrarily large n-point subsets X ⊆ L_{1} such any linear embedding of X into any d-dimensional normed space incurs distortion Ω (\sqrt{n/d}). This generalizes the Charikar-Sahai result to arbitrary low dimensional norms.

2 An inherently high-dimensional doubling metric in L_{1}

This section is devoted to the proof of Theorem 1.1. The case p = 2 of the proof below reduces to the argument in [11, 12, 21].

Proof of Theorem 1.1. Consider the Laakso graphs, {G_{i}}_{i=0}^{∞}, which are defined as follows. G_{0} is the graph on two vertices with one edge. To construct G_{i}, take six copies of G_{i−1} and scale their metric by a factor of \frac{1}{4}. We glue four of them cyclicly by identifying pairs of endpoints, and attach at two opposite gluing points the remaining two copies. See Figure 1 below.

G_{1} G_{0} G_{2} G_{3}

Figure 1: The Laakso graphs.

As shown in [11], the graphs {G_{i}}_{i=0}^{∞} are uniformly doubling (see also [12], for a simple argument showing they are doubling with constant 6). Moreover, since the G_{i}’s are series parallel graphs, they embed uniformly in L_{1} (see [5]).

We will show below that any embedding of G_{i} in L_{p}, 1 < p ≤ 2 incurs distortion at least

\sqrt{1 + \frac{p−1}{4}i}. We then conclude as in [13] by observing that ℓ_{1}^{d} is 3-isomorphic to ℓ_{p}^{d} when

p = 1 + \frac{1}{log d}, so that if G_{i} embeds with distortion α in ℓ_{1}^{d} then α ≥ \sqrt{\frac{i}{40 log d}}. This implies the required result since i ≈ log |G_{i}|.

The proof of the lower bound for the distortion required to embed G_{i} into L_{p} is by induction on i. We shall prove by induction that whenever f : G_{i} → L_{p} is non-contracting then there

exist two adjacent vertices u, v ∈ G_{i} such that ∥f(u) − f(v)∥_{p} ≥ d_{G_{i}}(u, v)\sqrt{1 + \frac{p−1}{4}i} (observe that for u, v ∈ G_{i−1}, d_{G_{i−1}}(u, v) = d_{G_{i}}(u, v)). For i = 0 there is nothing to prove. For i ≥ 1, since G_{i} contains an isometric copy of G_{i−1}, there are u, v ∈ G_{i} corresponding to two adjacent vertices in G_{i−1} such that ∥f(u) − f(v)∥_{p} ≥ d_{G_{i}}(u, v)\sqrt{1 + \frac{p−1}{4}(i − 1)}. Let a, b be the two midpoints between u and v in G_{i}. By Lemma 2.1 in [13],

∥f(u) − f(v)∥_{p}^{2} + (p − 1)∥f(a) − f(b)∥_{p}^{2}
≤ ∥f(u) − f(a)∥_{p}^{2} + ∥f(a) − f(v)∥_{p}^{2} + ∥f(v) − f(b)∥_{p}^{2} + ∥f(b) − f(u)∥_{p}^{2}.

Hence:

max{∥f(u) − f(a)∥_{p}^{2}, ∥f(a) − f(v)∥_{p}^{2}, ∥f(v) − f(b)∥_{p}^{2}, ∥f(b) − f(u)∥_{p}^{2}}
≥ \frac{1}{4}∥f(u) − f(v)∥_{p}^{2} + \frac{1}{4}(p − 1)∥f(a) − f(b)∥_{p}^{2}
≥ \frac{1}{4} (1 + \frac{p − 1}{4}(i − 1)) d_{G_{i}}(u, v)^{2} + \frac{p − 1}{4}d_{G_{i}}(a, b)^{2}
= \frac{1}{4} (1 + \frac{p − 1}{4}i) d_{G_{i}}(u, v)^{2}
= (1 + \frac{p − 1}{4}i) max\{d_{G_{i}}(u, a)^{2}, d_{G_{i}}(a, v)^{2}, d_{G_{i}}(v, b)^{2}, d_{G_{i}}(b, u)^{2}\}.

We end this section by observing that the above approach also gives a lower bound on the dimension required to embed expanders in ℓ_{∞}.

Proposition 2.1. Let G be an n-point constant degree expander which embeds in ℓ_{∞}^{d} with distortion at most α. Then d ≥ n^{Ω(1/α)}.

Proof. By Matoušek’s lower bound for the distortion required to embed expanders in ℓ_{p} [17], any embedding of G into ℓ_{p} incurs distortion Ω (\frac{log n}{p}). Since ℓ_{∞}^{d} is O(1)-equivalent to ℓ_{log d}^{d},

we deduce that α ≥ Ω (\frac{log n}{log d}).

We can also obtain a lower bound on the dimension required to embed the Hamming cube {0, 1}^{k} into ℓ_{∞}. Our proof uses a simple concentration argument. An analogous concentration argument yields an alternative proof of Proposition 2.1.

Proposition 2.2. Assume that {0, 1}^{k} embeds into ℓ_{∞}^{d} with distortion α. Then d ≥ 2^{kΩ(1/α^{2})}.

Proof. Let f = (f_{1}, …, f_{d}) : {0, 1}^{k} → ℓ_{∞}^{d} be a contraction such that for every u, v ∈ {0, 1}^{d}, ∥f(u) − f(v)∥_{∞} ≥ \frac{1}{α}d(u, v) (where d(·, ·) denotes the Hamming metric). Denote by P the uniform probability measure on {0, 1}^{k}. Since for every 1 ≤ i ≤ k, f_{i} is 1-Lipschitz, the standard isoperimetric inequality on the hypercube implies that P (|f_{i}(u) − 𝔼f_{i}| ≥ k/(4α)) ≤ e^{−Ω(k/α^{2})}. On the other hand, if u, v ∈ {0, 1}^{k} are such that d(u, v) = k then there exist 1 ≤ i ≤ d for which |f_{i}(u) − f_{i}(v)| ≥ k/α, implying that max{|f_{i}(u) − 𝔼f_{i}|, |f_{i}(v) − 𝔼f_{i}|} > k/(4α). By the union bound it follows that de^{−Ω(k/α^{2})} ≥ 1, as required.

3 Snowflake versions of planar metrics

The problem of whether there is an analog of the Johnson-Lindenstrauss dimension reduction lemma in L_{p}, 1 < p < 2, is an interesting one which remains open. In view of the above proof and the proof in [13], a natural point set which is a candidate to demonstrate the impossibility of dimension reduction in L_{p} is the realization of the diamond graph in ℓ_{1} which appears in [3], equipped with the ℓ_{p} metric. Since this point set consists of 0, 1 vectors, this amounts to considering the diamond graph with its metric raised to the power \frac{1}{p}. Unfortunately, this approach cannot work; we show below that any planar graph whose metric is raised to the power 1 − ε has Euclidean distortion O (1/\sqrt{ε}).

Given a metric space (X, d) and ε > 0, the metric space (X, d^{1−ε}) is known in geometric analysis (see e.g. [7]) as the 1 − ε snowflake version of (X, d). Assouad’s classical theorem [1] states that any snowflake version of a doubling metric space is bi-Lipschitz equivalent to a subset of some finite dimensional Euclidean space. A quantitative version of this result (with bounds on the distortion and the dimension) was obtained in [6]. The following theorem is proved by combining embedding techniques of Rao [23] and Assouad [1]. A similar analysis is also used in [6]. In what follows we call a metric K_{r}-excluded if it is the metric on a subset of a weighted graph which does not admit a K_{r} minor. In particular, planar metrics are all K_{5}-excluded.

Theorem 3.1. For any r ∈ ℕ there exists a constant C(r) such that for every 0 < ϵ < 1, a 1 − ε snowflake version of a K_{r}-excluded metric embeds into ℓ_{2} with distortion at most C(r)/\sqrt{ε}.

Our argument is based on the following lemma, the proof of which is contained in [23].

Lemma 3.2. For every r ∈ ℕ there is a constant δ = δ(r) such that for every ρ > 0 and every K_{r}-excluded metric (X, d) there exists a finitely supported probability distribution μ on partitions of X with the following properties:

1. For every P ∈ supp(μ), and for every C ∈ P, diam(C) ≤ ρ.

2. For every x ∈ X, 𝔼_{μ} ∑_{C∈P} d(x, X \ C) ≥ δρ.

Observe that the sum under the expectation in (2) above actually consists of only one summand.

Proof of Theorem 3.1. Let X be a K_{r}-excluded metric. For each n ∈ ℤ, we define a map ϕ_{n} as follows. Let μ_{n} be the probability distribution on partitions of X from Lemma 3.2 with ρ = 2^{n/(1−ε)}. Fix a partition P ∈ supp(μ_{n}). For any σ ∈ {−1, +1}^{|P |}, consider σ to be indexed by C ∈ P so that σ_{C} has the obvious meaning. Following Rao [23], define

ϕ_{P} (x) = ⨁_{σ∈\{−1,+1\}^{|P |}} \sqrt{\frac{1}{2^{|P |}}} ∑_{C∈P} σ_{C} · d(x, X \ C),

and write ϕ_{n} = ⨁_{P ∈supp(μ_{n})} \sqrt{μ_{n}(P)} ϕ_{P} (here the symbol ⊕ refers to the concatenation operator).

Now, following Assouad [1], let {e_{i}}_{i∈ℤ} be an orthonormal basis of ℓ_{2}, and set

Φ(x) = ∑_{n∈ℤ}2^{−nε/(1−ε)}ϕ_{n}(x) ⊗ e_{n}

Claim 3.3. For every n ∈ ℤ, and x, y ∈ X, we have ||ϕ_{n}(x)−ϕ_{n}(y)||_{2} ≤ 2·min {d(x, y), 2^{n/(1−ε)}}. Additionally, if d(x, y) > 2^{n/(1−ε)}, then ||ϕ_{n}(x) − ϕ_{n}(y)||_{2} ≥ δ 2^{n/(1−ε)}.

Proof. For any partition P ∈ supp(μ_{n}), let C_{x}, C_{y} be the clusters of P containing x and y, respectively. Note that since for every C ∈ P, diam(C) ≤ 2^{n/(1−ε)}, when d(x, y) > 2^{n/(1−ε)}, we have C_{x} ≠ C_{y}. In this case,

||ϕ_{P} (x) − ϕ_{P} (y)||_{2}^{2} = 𝔼_{σ∈{−1,+1}^{|P |}}|σ_{C_{x}}d(x, X \ C_{x}) − σ_{C_{y}}d(y, X \ C_{y})|^{2}
≥ \frac{d(x, X \ C_{x})^{2} + d(y, X \ C_{y})^{2}}{2} .

It follows that

||ϕ_{n}(x) − ϕ_{n}(y)||_{2}^{2} = 𝔼_{μ_{n}}||ϕ_{P} (x) − ϕ_{P} (y)||_{2}^{2}
≥ \frac{𝔼_{μ_{n}}d(x, X \ C_{x})^{2} + 𝔼_{μ_{n}}d(y, X \ C_{y})^{2}}{2} ≥ (δ 2^{n/(1−ε)})^{2} .

On the other hand, for every x, y ∈ X, since d(x, X \ C_{x}), d(y, X \ C_{y}) ≤ 2^{n/(1−ε)}, we have that ||ϕ_{P} (x) − ϕ_{P} (y)||_{2} ≤ 2 · min {d(x, y), 2^{n/(1−ε)}}, hence ||ϕ_{n}(x) − ϕ_{n}(y)||_{2} ≤ 2 · min {d(x, y), 2^{n/(1−ε)}}.

To finish the analysis, let us fix x, y ∈ X and let m be such that d(x, y)^{1−ε} ∈ (2^{m}, 2^{m+1}]. In this case,

||Φ(x) − Φ(y)||_{2}^{2} = ∑_{n∈ℤ}2^{−2nε/(1−ε)} ∥ϕ_{n}(x) − ϕ_{n}(y)∥_{2}^{2}
≤ 4 ∑_{n<m} 2^{2n} + 4d(x, y)^{2} ∑_{n≥m} 2^{−2nϵ/(1−ε)}

= 2^{2m+1} + 4d(x, y)^{2} \frac{2^{−2mε/(1−ε)}}{1 − 2^{−2ε/(1−ε)}}
= O (1/ε) · d(x, y)^{2(1−ε)}

On the other hand,

∥Φ(x) − Φ(y)||_{2} ≥ 2^{−mϵ/(1−ε)}∥ϕ_{m}(x) − ϕ_{m}(y)∥_{2} ≥ δ2^{m} ≥ \frac{δ}{2}d(x, y)^{1−ε}.

The proof is complete.

Remark 3.4. The O (1/\sqrt{ε}) upper bound in Theorem 3.1 is tight. In fact, for i ≈ 1/ε, the 1 − ε snowflake version of the Laakso graph G_{i} (presented in Section 2) has Euclidean distortion Ω (1/\sqrt{ε}). To see this, let f : G_{i} → ℓ_{2} be any non-contracting embedding of (G_{i}, d_{G_{i}}^{1−ε}) into ℓ_{2}. For j ≤ i denote by K_{j} the Lipschitz constant of the restriction of f to (G_{j}, d_{G_{i}}^{1−ε}) (as before, we think of G_{j} as a subset of G_{i}). Clearly K_{0} = 1, and the same

reasoning as in the proof of Theorem 1.1 shows that for j ≥ 1, K_{j}^{2} ≥ \frac{K_{j−1}^{2}}{4^{ε}} + \frac{1}{4}. This implies that K_{i}^{2} ≥ \frac{1}{4} + \frac{1}{4^{ε}} + … + \frac{1}{4^{iε}} = Ω(1/ε), as required.

4 Average distortion Euclidean embedding of subsets of L_{1}

The heart of our argument is the following lemma which is implicit in [16], and which seems to be of independent interest.

Lemma 4.1. For every 0 < p ≤ 2 there is a probability space (Ω, P) such that for every ω ∈ Ω there is a linear operator T_{ω} : L_{p} → L_{2} such that for every x ∈ L_{p} \ {0} the random variable X = \frac{∥T_{ω}(x)∥_{2}}{∥x∥_{p}} satisfies for every a ∈ ℝ, 𝔼e^{−aX^{2}} = e^{−a^{p/2}}. In particular, for p = 1 the density

of X is \frac{e^{−1/(4x^{2})}}{x^{2}\sqrt{π}}.

Proof. Consider the following three sequences of random variables, {Y_{j}}_{j≥1}, {θ_{j}}_{j≥1}, {g_{j}}_{j≥1}, such that each variable is independent of the others. For each j ≥ 1, Y_{j} is uniformly distributed on [0, 1], g_{j} is a standard Gaussian and θ_{j} is an exponential random variable, i.e. for λ ≥ 0, P (θ_{j} > λ) = e^{−λ}. Set Γ_{j} = θ_{1} + ⋯ + θ_{j}. By Proposition 1.5. in [16], there is a constant C = C(p) such that if we define for f ∈ L_{p}

V (f) = C ∑_{j≥1} \frac{g_{j}}{Γ_{j}^{1/p}} f(Y_{j}),

then 𝔼e^{iV (f)} = e^{−∥f∥_{p}^{p}}.

Assume that the random variables {Y_{j}}_{j≥1} and {Γ_{j}}_{j≥1} are defined on a probability space (Ω, P) and that {g_{j}}_{j≥1} are defined on a probability space (Ω′, P′), in which case we use the notation V (f) = V (f; ω, ω′). Define for ω ∈ Ω a linear operator T_{ω} : L_{p} → L_{2}(Ω′, P′) by T_{ω}(f) = V (f; ω, ·). Since for every fixed ω ∈ Ω the random variable V (f; ω, ·) is Gaussian with variance ∥T_{ω}(f)∥_{2}^{2}, for every a ∈ ℝ, 𝔼_{P′}e^{iaV (s;ω,·)} = e^{−a^{2}∥T_{ω}(f)∥_{2}^{2}}. Taking expectation with respect to P we find that, 𝔼_{P} e^{−a^{2}∥T_{ω}(f)∥_{2}^{2}} = e^{−a^{p}∥f∥_{p}^{p}}. This implies the required identity. The explicit distribution in the case p = 1 follows from the fact that the inverse Laplace transform of x ↦ e^{−\sqrt{x}} is y ↦ \frac{e^{−1/(4y)}}{2\sqrt{πy^{3}}} (see for example [24]).

Theorem 4.2. For every f_{1}, …, f_{n} ∈ L_{1} there is a linear operator T : L_{1} → L_{2} such that:

\frac{1}{(8 log n)^{1/3}} ≤ min_{1≤i<j≤n} (\frac{∥T (f_{i}) − T (f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} )^{2/3} ≤ \frac{1}{\binom{n}{2}} ∑_{1≤i<j≤n} (\frac{∥T (f_{i}) − T (f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} )^{2/3} ≤ 10.

Proof. Using the notation of lemma 4.1 (in the case p = 1) we find that for every a > 0, 𝔼e^{−aX^{2}} = e^{−\sqrt{a}}. Hence, for every a, ε > 0 and every 1 < i < j ≤ n,

P (\frac{∥T_{ω}(f_{i}) − T_{ω}(f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} ≤ ε) = P (e^{−aX^{2}} ≥ e^{−aε^{2}}) ≤ e^{aε^{2}−\sqrt{a}}.

Choosing a = \frac{1}{4ε^{4}} the above upper bound becomes e^{−1/(4ε^{2})}. Consider the set

A = ⋂_{1≤i<j≤n} \{\frac{∥T_{ω}(f_{i}) − T_{ω}(f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} ≥ \frac{1}{\sqrt{8 log n}}\} ⊆ Ω.

By the union bound, P (A) > \frac{1}{2}, so that

\frac{1}{P (A)}𝔼 [\frac{1}{\binom{n}{2}} ∑_{1≤i<j≤n} (\frac{∥T_{ω}(f_{i}) − T_{ω}(f_{j})∥_{2}}{∥f_{i} − f_{j}∥_{1}} )^{2/3}] ≤ 2𝔼X^{2/3} = \frac{2}{\sqrt{π}} ∫_{0}^{∞} x^{2/3} · \frac{e^{−1/(4x^{2})}}{x^{2}} dx < 10.

It follows that there exists ω ∈ A for which the operator T = T_{ω} has the desired properties.

Remark 4.3. There is nothing special about the choice of the the power 2/3 in Corollary 4.2. When p = 1, 𝔼X = ∞ but 𝔼X^{1−ε} < ∞ for every 0 < ε < 1, so we may write the above average with the power 1−ε replacing the exponent 2/3. Obvious generalizations of Corollary 4.2 hold true for every 1 < p < 2, in which case the average distortion is of order C(p)(log n)^{1/p−1/2} (and the power can be taken to be 1).

5 The impossibility of linear dimension reduction in L_{p}, p ≠ 2

The above method cannot yield a O (\sqrt{log n}) bound on the Euclidean distortion of n-point subsets of L_{1}. In fact, there are arbitrarily large n-point subsets of L_{1} on which any linear embedding into L_{2} incurs distortion at least \sqrt{\frac{n−1}{2}}. This follows from the following simple lemma:

Lemma 5.1. For every 1 ≤ p ≤ ∞ there are arbitrarily large n-point subsets of L_{p} on which any linear embedding into L_{2} incurs distortion at least (\frac{n−1}{2})^{|1/p−1/2|}.

Proof. Let w_{1}, …, w_{2^{k}} be the rows of the 2^{k} × 2^{k} Walsh matrix. Write w_{i} = ∑_{j=1}^{2^{k}} w_{ij}e_{j} where e_{1}, …, e_{2^{k}} are the standard unit vectors in ℝ^{2^{k}}. Consider the set A = {0}∪{w_{i}}_{i=1}^{2^{k}} ∪{e_{i}}_{i=1}^{2^{k}} ⊂ ℓ_{p}. Let T : ℓ_{p} → L_{2} be any linear operator which is non contracting and L-Lipschitz on A. Assume first of all that 1 ≤ p < 2. Then:

2^{k(1+2/p)} = ∑_{i=1}^{2^{k}} ∥w_{i}∥_{p}^{2} ≤ ∑_{i=1}^{2^{k}} ∥T w_{i}∥_{2}^{2} = ∑_{i=1}^{2^{k}} ∥∑_{j=1}^{2^{k}} w_{ij}T (e_{j})∥_{2}^{2}

= ∑_{i=1}^{2^{k}} ∑_{j=1}^{2^{k}} ⟨w_{i}, w_{j}⟩ ⟨T (e_{i}), T (e_{j})⟩ = 2^{k} ∑_{j=1}^{2^{k}} ∥T (e_{j})∥_{2}^{2} ≤ 4^{k} · L^{2},

which implies that L ≥ 2^{k(1/p−1/2)} = (\frac{|A|−1}{2})^{1/p−1/2}. When p > 2 apply the same reasoning, with the inequalities reversed.

We remark that the above point set was also used by Charikar and Sahai [4] to give a lower bound on linear dimension reduction in L_{1}. Their proof used a linear programming argument, which doesn’t seem to be generalizable to the the case of L_{p}, p > 1. Lemma 5.1 formally implies their result (with a significantly simpler proof), and in fact proves the impossibility of linear dimension reduction in any L_{p}, p ≠ 2. Indeed, if there were a linear operator which embeds A into ℓ_{p}^{d} with distortion D then it would also be a D · d^{|1/p−1/2|} embedding into

ℓ_{2}^{d}. It follows that D ≥ (\frac{|A|−1}{2d})^{|1/p−1/2|}. Similarly, since by John’s theorem (see e.g. [20])

any d-dimensional normed space is \sqrt{d} equivalent to Hilbert space, we deduce that there are arbitrarily large n-point subsets of L_{1}, any embedding of which into any d-dimensional normed space incurs distortion at least \sqrt{\frac{n−1}{2d}}.

References

[1] Patrice Assouad. Plongements lipschitziens dans R^{n}. Bull. Soc. Math. France, 111(4):429– 448, 1983.

[2] Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM J. Comput., 27(1):291–301, 1998.

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

[4] M. Charikar and A. Sahai. Dimension reduction in the ℓ_{1} norm. In Proceedings of the 43rd Annual IEEE Conference on Foundations of Computer Science. ACM, 2002.

[5] A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and ℓ_{1} embeddings. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999.

[6] Anupam Gutpa, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the 44th Annual Symposium on Foundations of Computer Science, to appear, 2003.

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

[8] P. Indyk. Algorithmic applications of low-distortion geometric embeddings. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, pages 10–33. October 2001.

[9] William B. Johnson and Joram 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.

[10] R. Krauthgamer and J. R. Lee. Navigating nets: Simple algorithms for proximity search. Submitted, 2003.

[11] T. J. Laakso. Ahlfors Q-regular spaces with arbitrary Q > 1 admitting weak Poincaré inequality. Geom. Funct. Anal., 10(1):111–123, 2000.

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

[13] J. R. Lee and A. Naor. Embedding the diamond graph in L_{p} and dimension reduction in L_{1}. Geom. Funct. Anal., to appear.

[14] N. Linial. Finite metric spaces - combinatorics, geometry and algorithms. In Proceedings of the International Congress of Mathematicians III, pages 573–586, 2002.

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

[16] M. B. Marcus and G. Pisier. Characterizations of almost surely continuous p-stable random Fourier series and strongly stationary processes. Acta Math., 152(3-4):245–301, 1984.

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

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

[19] J. Matoušek. Open problems, workshop on discrete metric spaces and their algorithmic appl ications. Haifa, March 2002.

[20] Vitali D. Milman and Gideon Schechtman. Asymptotic theory of finite-dimensional normed spaces, volume 1200 of Lecture Notes in Mathematics. Springer-Verlag, Berlin, 1986. With an appendix by M. Gromov.

[21] I. Newman and Y. Rabinovich. A lower bound on the distortion of embedding planar metrics into euclidean space. Discrete Computational Geometry, 29(1):77–81, 2003.

[22] Y. Rabinovich. On average distorsion of embedding metrics into the line and into l_{1}. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing. ACM, 2003.

[23] S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In Proceedings of the 15th Annual Symposium on Computational Geometry, pages 300–306. ACM, 1999.

[24] David Vernon Widder. The Laplace Transform. Princeton Mathematical Series, v. 6. Princeton University Press, Princeton, N. J., 1941.