### On the impossibility of dimension reduction in $l_{1}$On the impossibility of dimension reduction in $l_{1}$

Access Restriction
Subscribed

 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

Source: ACM Digital Library