Abstract
We show that any embedding of the level k diamond graph of Newman and Rabinovich [NR] into Lp, 1 < p ≤ 2, requires distortion at least √k(p - 1) + 1. An immediate corollary is that there exist arbitrarily large n-point sets X ⊆ L1 such that any D-embedding of X into ℓ1d requires d ≥ n Ω(1/D2). This gives a simple proof of a recent result of Brinkman and Charikar [BrC] which settles the long standing question of whether there is an L1 analogue of the Johnson-Lindenstrauss dimension reduction lemma [JL].
Original language | English (US) |
---|---|
Pages (from-to) | 745-747 |
Number of pages | 3 |
Journal | Geometric and Functional Analysis |
Volume | 14 |
Issue number | 4 |
DOIs | |
State | Published - 2004 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Analysis
- Geometry and Topology