| Abstract |
|
The Johnson-Lindenstrauss Lemma shows that any n points in Euclidean space (with distances measured by the \ell norm) may be mapped down to 0((\log n)/\varepsilon) dimensions such that no pairwise distance is distorted by more than a (1+ \varepsilon) factor. Determining whether such dimension reduction is possible in \ell has been an intriguing open question. We show strong lower bounds for general dimension reduction in \ell. We give an explicit family of n points in \ell such that any embedding with distortion \delta requires n^{/\delta ^2} dimensions. This proves that there is no analog of the Johnson-Lindenstrauss Lemma for \ell; in fact embedding with any constant distortion requires n dimensions. Further, embedding the points into \ell with 1 + \varepsilon distortion requires n^{\frac{1}{2} - 0\varepsilon \frac{1}{\varepsilon}} 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 \ell.
|
 Additional Information
|
Citation:
Bo Brinkman, Moses Charikar,
"On the Impossibility of Dimension Reduction in \ell _1,"
focs,
p. 514,
44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03),
2003
|
