On the impossibility of dimension reduction in ℓ1

The Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances measured by the ℓ₂ norm) may be mapped down to O((log n)/ε²) dimensions such that no pairwise distance is distorted by more than a (1+ ε) factor. Determining whether such dimension reduction is possible in ℓ₁ has been an intriguing open question. We show strong lower bounds for general dimension reduction in ℓ₁. We give an explicit family of n points in ℓ₁ such that any embedding with distortion δ requires n^Ω(1δ2)/ dimensions. This proves that there is no analog of the Johnson-Lindenstrauss Lemma for ℓ₁; in fact embedding with any constant distortion requires n^Ω(1) dimensions. Further, embedding the points into ℓ₁ with 1 + ε distortion requires n¹2 -O(εlog(1/ε))/ dimensions. Our proof establishes this lower bound for shortest path metrics of series-parallel graphs. We make extensive use of linear programming and duality in devising our bounds. We expect that the tools and techniques we develop will be useful for future investigations of embeddings into ℓ₁.