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"?
4 Answers
The standard reference for such a positive result is Piotr Indyk's paper on stable distributions:
http://people.csail.mit.edu/indyk/st-fin.ps
He 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.
See the Metric Embeddings with Relaxed Guarantees paper which has results on $\ell_1$ (under the conditions of "gracefully degrading distortion") and general $\ell_p$ embeddings.
Also look at the Practical Procedures for Dimension Reduction in $\ell_1$ paper.
It has been recently shown by Newman and Rabinovich that for n points in $\ell_1$ there is dimension reduction to dimension $O(n/\epsilon)$. Using a theorem of Abraham et al. (Metric embedding with relaxed guarantees, mentioned above) one can get dimension reduction in dimension $O(1/(\delta\epsilon))$ that works for a $1-\delta$ fraction of the pairs.
Another relaxation of $\ell_1$ dimension reduction is to require that $S$ lies in a $c$-dimensional subspace of $\mathbb{R}^d$ and make $k$ depend on $c$. Talagrand proved that given a $c$-dimensional subspace $V$ of $\ell_1^d$ (he even proves it for $L_1$), there exists a map $f:\ell_1^d \rightarrow \ell_1^k$ for $k = O(\epsilon^{-2}c\log c)$ such that for all $x, y \in V$, $(1-\epsilon)\|f(x) - f(y)\|_1 \leq \|x - y\|_1 \leq (1+\epsilon)\|f(x) - f(y)\|_1$. His embedding is a simple randomized procedure, but it proceeds in steps and each step succeeds with constant probability; after each step you need to check that the step indeed has been successful and repeat if it hasn't. So Talagrand's embedding lacks a crucial feature of JLT: the fact that $f$ can be picked from a distribution that is independent of $S$.
Very recently, Woodruff and Sohler have proved a result analogous to Talagrand's, but with the added feature that $f$, just like in JLT, is a linear mapping picked from a distribution independent of $S$: you need to pick a $k \times d$ matrix where each entry is an iid Cauchy random variable. This is in the spirit of Indyk's stable projections: Cauchy is 1-stable.
