Access Restriction

Author Brinkman, Bo ♦ Charikar, Moses
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2005
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Metric spaces ♦ Dimension reduction ♦ Embedding
Abstract The Johnson--Lindenstrauss lemma shows that any $\textit{n}$ points in Euclidean space (i.e., $ℝ^{n}$ with distances measured under the ℓ2 norm) may be mapped down to $\textit{O}((log$ $n)/ε^{2})$ dimensions such that no pairwise distance is distorted by more than a (1 + ε) factor. Determining whether such dimension reduction is possible in ℓ1 has been an intriguing open question. We show strong lower bounds for general dimension reduction in ℓ1. We give an explicit family of $\textit{n}$ points in ℓ1 such that any embedding with constant distortion $\textit{D}$ requires $n^{Ω(1/D^{2})}$ dimensions. This proves that there is no analog of the Johnson--Lindenstrauss lemma for ℓ1; in fact, embedding with any constant distortion requires $n^{Ω(1)}$ dimensions. Further, embedding the points into ℓ1 with (1+ε) distortion requires $\textit{n}½™\textit{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 ℓ1.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 52
Issue Number 5
Page Count 23
Starting Page 766
Ending Page 788

Open content in new tab

   Open content in new tab
Source: ACM Digital Library