The Johnson-Lindenstrauss lemma says roughly that for any collection $S$ of $n$ points in $\mathbb{R}^d$, there exists a map $f:\mathbb{R}^d \rightarrow \mathbb{R}^k$ where $k = O(\log n/\epsilon^2)$ such that for all $x, y \in S$:$$(1-\epsilon)||f(x)-f(y)||_2 \leq ||x-y||_2 \leq (1+\epsilon)||f(x)-f(y)||_2$$It is known that similar statements are not possible for the $\ell_1$ metric, but is it known if there is any way of getting around such lower bounds by offering weaker guarantees? For example, can there be a version of the above lemma for the $\ell_1$ metric that only promises to preserve the distances of most points, but might leave some arbitrarily distorted? One that makes no multiplicative guarantee for points that are too close?
Dimensionality reduction with slack?
ds.algorithms;approximation algorithms;cg.comp geom;metrics;embeddings
The standard reference for such a positive result is Piotr Indyk's paper on stable distributions:http://people.csail.mit.edu/indyk/st-fin.psHe shows a dimension reduction technique for $\ell_1$ where the distance between any pair of points does not increase (by more than factor $1+\epsilon$) with constant probability and distances do not decrease (by more than factor $1-\epsilon$) with high probability. The dimension of the embedding will be exponential in $1/\epsilon$.There are probably follow up works that I'm not aware of.