# Dimensionality reduction with slack?

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"?

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.