Embedding the diamond graph in $L_p$ and dimension reduction in $L_1$

Abstract

We show that any embedding of the level-k diamond graph of Newman and Rabinovich into $L_p$, $1<p\le 2$, requires distortion at least $\sqrt{k(p-1)+1}$. An immediate consequence is that there exist arbitrarily large n-point sets $X\subseteq L_1$ such that any D-embedding of X into ${\ell }_1^d$ requires $d\ge n^{\Omega (1/D^2)}$. This gives a simple proof of the recent result of Brinkman and Charikar which settles the long standing question of whether there is an $L_1$ analogue of the Johnson-Lindenstrauss dimension reduction lemma.

3 pages. To appear in Geometric and Functional Analysis (GAFA)

Cited by in corpus (7)

• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors
• A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs
• On some low distortion metric Ramsey problems
• Metric structures in L_1: Dimension, snowflakes, and average distortion
• Maximum gradient embeddings and monotone clustering
• Sketching, Embedding, and Dimensionality Reduction for Information Spaces
• Improving the Johnson-Lindenstrauss Lemma