Embedding the diamond graph in L_{p} and dimension reduction in L_{1}

James R. Lee^{∗} U.C. Berkeley and Microsoft Research

Assaf Naor Microsoft Research

Abstract

We show that any embedding of the level k diamond graph of Newman and Rabinovich [6] into L_{p}, 1 < p ≤ 2, requires distortion at least \sqrt{k(p − 1) + 1}. An immediate corollary is that there exist arbitrarily large n-point sets X ⊆ L_{1} such that any D-embedding of X into ℓ_{1}^{d} requires d ≥ n^{Ω(1/D^{2})}. This gives a simple proof of a recent result of Brinkman and Charikar [2] which settles the long standing question of whether there is an L_{1} analogue of the Johnson-Lindenstrauss dimension reduction lemma [4].

1 The diamond graphs, distortion, and dimension

We recall the definition of the diamond graphs {G_{k}}_{k=0}^{∞} whose shortest path metrics are known to be uniformly bi-lipschitz equivalent to a subset of L_{1} (see [3] for the L_{1} embeddability of general series-parallel graphs). The diamond graphs were used in [6] to obtain lower bounds for the Euclidean distortion of planar graphs and similar arguments were previously used in a different context by Laakso [5].

G_{0} consists of a single edge of length 1. G_{i} is obtained from G_{i−1} as follows. Given an edge (u, v) ∈ E(G_{i−1}), it is replaced by a quadrilateral u, a, v, b with edge lengths 2^{−i}. In what follows, (u, v) is called an edge of level i − 1, and (a, b) is called the level i anti-edge corresponding to (u, v). Our main result is a lower bound on the distortion necessary to embed G_{k} into L_{p}, for 1 < p ≤ 2.

Theorem 1.1. For every 1 < p ≤ 2, any embedding of G_{k} into L_{p} incurs distortion at least \sqrt{1 + (p − 1)k}.

The following corollary shows that the diamond graphs cannot be well-embedded into lowdimensional ℓ_{1} spaces. In particular, an L_{1} analogue of the Johnson-Lindenstrauss dimension reduction lemma does not exist. The same graphs were used in [2] as an example which shows the impossibility of dimension reduction in L_{1}. Our proof is different and, unlike the linear programming based argument appearing there, relies on geometric intuition. We proceed by observing that a lower bound on the rate of decay of the distortion as p → 1 yields a lower bound on the required dimension in ℓ_{1}.

Corollary 1.2. For every n ∈ ℕ, there exists an n-point subset X ⊆ L_{1} such that for every D > 1, if X D-embeds into ℓ_{1}^{d}, then d ≥ n^{Ω(1/D^{2})}.

∗Work partially supported by NSF grant CCR-0121555 and an NSF Graduate Research Fellowship.

Proof. Since ℓ_{1}^{d} is O(1)-isomorphic to ℓ_{p}^{d} when p = 1 + \frac{1}{log d} and G_{k} is O(1)-equivalent to a

subset X ⊆ L_{1}, it follows that \sqrt{1 + \frac{k}{log d}} = O(D). Noting that k = Ω(log n) completes the proof.

2 Proof

The proof is based on the following inequality. The case p = 2 is the well known “short diagonals lemma” which was central to the argument in [5, 6].

Lemma 2.1. Fix 1 < p ≤ 2 and x, y, z, w ∈ L_{p}. Then,

∥y − z∥_{p}^{2} + (p − 1)∥x − w∥_{p}^{2} ≤ ∥x − y∥_{p}^{2} + ∥y − w∥_{p}^{2} + ∥w − z∥_{p}^{2} + ∥z − x∥_{p}^{2}.

Proof. For every a, b ∈ L_{p}, ||a + b||_{p}^{2} + (p − 1)||a − b||_{p}^{2} ≤ 2(||a||_{p}^{2} + ||b||_{p}^{2}). A simple proof of this classical fact can be found, for example, in [1]. Now,

||y − z||_{p}^{2} + (p − 1)||y − 2x + z||_{p}^{2} ≤ 2||y − x||_{p}^{2} + 2||x − z||_{p}^{2}

and

||y − z||_{p}^{2} + (p − 1)||y − 2w + z||_{p}^{2} ≤ 2||y − w||_{p}^{2} + 2||w − z||_{p}^{2}.

Averaging these two inequalities yields

||y − z||_{p}^{2} + (p − 1)\frac{||y − 2x + z||_{p}^{2} + ||y − 2w + z||_{p}^{2}}{2} ≤ ∥x − y∥_{p}^{2} + ∥y − w∥_{p}^{2} + ∥w − z∥_{p}^{2} + ∥z − x∥_{p}^{2}.

The required inequality follows by convexity.

Lemma 2.2. Let A_{i} denote the set of anti-edges at level i and let {s, t} = V (G_{0}), then for 1 < p ≤ 2 and any f : G_{k} → L_{p},

||f(s) − f(t)||_{p}^{2} + (p − 1) ∑_{i=1}^{k} ∑_{(x,y)∈A_{i}} ||f(x) − f(y)||_{p}^{2} ≤ ∑_{(x,y)∈E(G_{k})} ||f(x) − f(y)||_{p}^{2}.

Proof. Let (a, b) be an edge of level i and (c, d) its corresponding anti-edge. By Lemma 2.1, ||f(a) − f(b)||_{p}^{2} + (p − 1)||f(c) − f(d)||_{p}^{2} ≤ ||f(a) − f(c)||_{p}^{2} + ||f(b) − f(c)||_{p}^{2} + ||f(d) − f(a)||_{p}^{2} + ||f(d) − f(b)||_{p}^{2}. Summing over all such edges and all i = 0, …, k − 1 yields the desired result by noting that the terms ||f(x) − f(y)||_{p}^{2} corresponding to (x, y) ∈ E(G_{i}) cancel for i = 1, …, k − 1.

The main theorem now follows easily.

Proof of Theorem 1.1. Let f : G_{k} → L_{p} be a non-expansive D-embedding. Since |A_{i}| = 4^{i−1} and the length of a level i anti-edge is 2^{1−i}, applying Lemma 2.2 yields \frac{1+(p−1)k}{D^{2}} ≤ 1.

References

[1] K. Ball, E. A. Carlen and E. Lieb. Sharp uniform convexity and smoothness inequalities for trace norms. Invent. Math. 115, 463-482 (1994).

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

[3] 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. ACM, 1999.

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

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

[6] I. Newman and Y. Rabinovich. A Lower Bound on the Distortion of Embedding Planar Metrics into Euclidean Space. Discrete Computational Geometry, 29 no. 1, 77-81 (2003).