<p>See the <a href="http://cims.nyu.edu/~neiman/slack_conf.pdf" rel="nofollow">Metric Embeddings with Relaxed Guarantees</a> paper which has results on $\ell_1$ (under the conditions of "gracefully degrading distortion") and general $\ell_p$ embeddings.</p>

<p>Also look at the <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.307&amp;rep=rep1&amp;type=pdf" rel="nofollow">Practical Procedures for Dimension Reduction</a> in $\ell_1$ paper.</p>

CC BY-SA 2.5
2010-08-26T14:58:15.723Z
2011-01-05T01:42:21.590Z
2011-01-05T01:42:21.590Z
spinxl39
<p>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.</p>

CC BY-SA 2.5
2011-01-04T20:21:13.710Z
2011-01-05T01:45:02.120Z
2011-01-05T01:45:02.120Z
Yair
<p>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 <a href="http://www.jstor.org/pss/2048283" rel="nofollow">proved</a> 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$. </p>

<p>Very recently, <a href="http://www.almaden.ibm.com/cs/people/dpwoodru/sw.pdf" rel="nofollow">Woodruff and Sohler</a> 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.  </p>

CC BY-SA 3.0
2011-05-02T17:12:06.053Z
2011-05-02T17:12:06.053Z
Sasho Nikolov
<p>The standard reference for such a positive result is Piotr Indyk's paper on stable distributions:</p>

<p><a href="http://people.csail.mit.edu/indyk/st-fin.ps">http://people.csail.mit.edu/indyk/st-fin.ps</a></p>

<p>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$.</p>

<p>There are probably follow up works that I'm not aware of.</p>

CC BY-SA 2.5
2010-08-26T14:56:04.293Z
2010-08-26T14:56:04.293Z
Moritz
<p>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"?</p>

<ds.algorithms><approximation-algorithms><cg.comp-geom><metrics><embeddings>
Dimensionality reduction with slack?
Aaron Roth
# Dimensionality reduction with slack?

(Asked by: username_0 on 2010-08-26)

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

**Tags:** ds.algorithms, approximation-algorithms, cg.comp-geom, metrics, embeddings


---

## 4 answers

### Answer by username_4 on 2010-08-26. Score: 9 | Accepted answer

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.


---

### Answer by username_1 on 2010-08-26. Score: 8

See the [Metric Embeddings with Relaxed Guarantees](http://cims.nyu.edu/~neiman/slack_conf.pdf) 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](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.62.307&rep=rep1&type=pdf) in $\ell\_1$ paper.


---

### Answer by username_2 on 2011-01-04. Score: 7

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.


---

### Answer by username_3 on 2011-05-02. Score: 4

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](http://www.jstor.org/pss/2048283) 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](http://www.almaden.ibm.com/cs/people/dpwoodru/sw.pdf) 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.


---

