<p>SVD and JL also extrapolates to future points differently as well.</p>

<p>That is, if you assume your data comes from some underlying distribution, in principle the SVD should remain "good" for any future points so long as they are sampled from the same distribution.  On the other hand, the target dimension of JL depends on the number of points, meaning that applying a JL transform to additional points can increase the error probability.</p>

<p>This becomes relevant if, for instance, if you are using dimensionality reduction as a preprocessing step for some other algorithm.  SVD bounds for training data may hold on test data, but JL's will not.</p>

CC BY-SA 3.0
2014-07-04T13:18:56.957Z
This is a very good point.
Paul Siegel
CC BY-SA 3.0
2014-07-04T09:45:55.197Z
2014-07-04T09:45:55.197Z
Frumple
<p>This is a follow-up to Suresh's answer - I googled a bit after reading his answer, and came up with the following understanding. I was originally going to post this as a comment to his answer, but it kept on increasing. </p>

<p>Please point out errors in the answer, I'm no expert in this field.</p>

<p>In some sense, JL and SVD are like apples and oranges.</p>

<p>1) The problems they solve are completely different. One is concerned with pairwise distances, the other with the best representation. One is worst case, the other is average case.</p>

<p>The subspace JL returns <strike>(JL isn't constructive, but lets assume it returned a best subspace)</strike> is the solution to the following optimization 
$$\arg\min\limits_{P} \left\{\sup\limits_{u,v} \left(\Biggl\lvert 1- \frac{||Pu-Pv||_2}{||u-v||_2} \Biggl\rvert \right) \right\} \tag{1}$$</p>

<p>(This isn't precise, I'll comment more on this later)</p>

<p>The problem SVD is solving is (given a dimension $k$) 
$$\arg\min\limits_{P\text{ of dim k}} \left\{\text{Avg}\left(||u-Pu||_2\right)\right\} $$</p>

<p>2) Inputs: Although both algorithms output subspaces, the inputs they need are different. JL requires a tolerance $\epsilon$ (what is the max error you are willing to tolerate between actual distances and distances in the subspace), while SVD requires number of dimensions. </p>

<p><strike>
3) JL is nonconstructive, SVD is constructive - this point is a bit vague, as the term constructive is not precisely defined. There are deterministic algorithms for computing the SVD, but the algorithm for finding a JL space is a randomized one - do random projections, if you fail, try again. 
</strike></p>

<p>4) SVD is unique (the subspace may not be unique, but the objective value will be the same for all subspaces). Eqn(1) above isn't precise in the sense that JL doesn't actually talk about minimizing the discrepancy in the pairwise distances - it gives a guarantee about the existence of a smaller subspace where distances will be atmost $\epsilon$ different from their actual values. There could be many such subspaces, some better than the others.</p>

<p>(See comments for explanation regarding striked portions of the answer).</p>

<p>Edit: @john-myles-white has written a post about JL to verify its claims, and show how a projection can be constructed: <a href="http://www.johnmyleswhite.com/notebook/2014/03/24/a-note-on-the-johnson-lindenstrauss-lemma/" rel="nofollow">http://www.johnmyleswhite.com/notebook/2014/03/24/a-note-on-the-johnson-lindenstrauss-lemma/</a></p>

CC BY-SA 3.0
2014-03-12T01:43:54.843Z
There are a number of errors in your answer. (1) JL is extremely constructive: there are all kinds of algorithms for constructing the mapping (2) it doesn't preserve the difference but the relative difference (the ratio) (3) the JL lemma has been derandomized (4) JL works for *any* set of vectors: the construction is independent of the actual input. the only information needed is the *number* of vectors.
Suresh Venkat
CC BY-SA 3.0
2014-03-12T02:48:47.823Z
Thanks Suresh. I've incorporated all except your final suggestion. Feel free to edit the answer further. On the last point, I'm confused. You're saying the same map will work no matter what set of vectors I give you?
elexhobby
CC BY-SA 3.0
2014-03-12T03:46:58.713Z
That's a slightly subtle point. Once you fix the error and the number of vectors, there is a fixed *probability distribution* on maps which will work with high probability for any set of vectors. Of course there is not deterministically fixed linear map that satisfies this property.
Sasho Nikolov
CC BY-SA 3.0
2014-03-26T03:12:36.443Z
It's worth checking out Olivier Grisel's [scikit-learn implementation](http://scikit-learn.org/stable/auto_examples/plot_johnson_lindenstrauss_bound.html)
KLDavenport
CC BY-SA 3.0
2014-07-04T13:17:23.120Z
I'd like to add that not only is there no deterministic algorithm for constructing a JL embedding in general, it is typically computationally prohibitive to check that a matrix randomly generated according to the JL algorithm actually has the "almost isometry" property (even though it does with very high probability).  So I think it's reasonable to say that the JL theorem is not constructive.  Compare to the algorithm "choose a random real number between $0$ and $1$"; this gives a transcendental number with probability $1$, but I wouldn't call it constructive.
Paul Siegel
CC BY-SA 3.0
2014-03-12T00:13:39.260Z
2014-03-25T15:05:27.943Z
2014-03-25T15:05:27.943Z
elexhobby
<p>The two approaches provide very different guarantees. </p>

<p>The JL Lemma says essentially "you give me the error you want, and I'll give you a low dimensional space that captures the distances upto that error". It's also a <strong>worst-case</strong> pairwise guarantee: for <strong>each pair of points</strong>, etc etc</p>

<p>The SVD essentially promises "you tell me what dimension you want to live in, and I'll give you the best possible embedding", where "best" is defined as <strong>on average</strong>: the total error of true similarity versus projected similarity is minimum. </p>

<p>So from a theoretical perspective they solve very different problems. In practice, which one you want depends on your model for the problem, what parameters are more important (error or dimension), and what kind of guarantees you need. </p>

CC BY-SA 3.0
2014-03-11T22:34:37.357Z
Could someone tell me how exactly is $f(\cdot)$ obtained in (1-eps)|u-v|^2 <= |f(u)-f(v)|^2 <= (1+eps)|u-v|^2 (from http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)?
Turbo
CC BY-SA 3.0
2014-03-11T23:40:29.887Z
That's a whole other question. But in (very) brief, if you take a matrix $A$ and populate it with entries drawn from a standard normal, then $f(x)$ is defined as $Ax$.
Suresh Venkat
CC BY-SA 3.0
2014-03-22T22:40:43.680Z
Is there a JL scheme for finite fields too where the distortion is in the Hamming metric? If so, then what would $f$ be here?
Turbo
CC BY-SA 3.0
2014-03-22T23:09:34.543Z
You can't do dimensionality reduction this effectively for the Hamming metric. The $\ell_1$ structure is very different. In a very handwavy sense, admitting JL-style reductions is linked to living in a Hilbert space.
Suresh Venkat
CC BY-SA 3.0
2014-03-11T20:06:07.167Z
2014-03-11T20:06:07.167Z
Suresh Venkat
<p>The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to find the singular value decomposition and then take the subspace generated by the largest singular values. When is it of interest to use Johnson-Lindenstrauss over the SVD?</p>

<machine-learning>
When to use the Johnson-Lindenstrauss lemma over SVD?
user09128323
# When to use the Johnson-Lindenstrauss lemma over SVD?

(Asked by: username_0 on 2014-03-11)

The Johnson-Lindenstrauss lemma allows one to represent points in a high dimensional space into points in lower dimension. When finding lower dimensional spaces of best fit, a standard technique is to find the singular value decomposition and then take the subspace generated by the largest singular values. When is it of interest to use Johnson-Lindenstrauss over the SVD?

**Tags:** machine-learning


---

## 3 answers

### Answer by username_4 on 2014-03-11. Score: 20 | Accepted answer

The two approaches provide very different guarantees.

The JL Lemma says essentially "you give me the error you want, and I'll give you a low dimensional space that captures the distances upto that error". It's also a **worst-case** pairwise guarantee: for **each pair of points**, etc etc

The SVD essentially promises "you tell me what dimension you want to live in, and I'll give you the best possible embedding", where "best" is defined as **on average**: the total error of true similarity versus projected similarity is minimum.

So from a theoretical perspective they solve very different problems. In practice, which one you want depends on your model for the problem, what parameters are more important (error or dimension), and what kind of guarantees you need.

> **Comments:**
> **username_7**: Could someone tell me how exactly is $f(\cdot)$ obtained in (1-eps)|u-v|^2 <= |f(u)-f(v)|^2 <= (1+eps)|u-v|^2 (from http://en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)?  
> **username_4**: That's a whole other question. But in (very) brief, if you take a matrix $A$ and populate it with entries drawn from a standard normal, then $f(x)$ is defined as $Ax$.  
> **username_7**: Is there a JL scheme for finite fields too where the distortion is in the Hamming metric? If so, then what would $f$ be here?  
> **username_4**: You can't do dimensionality reduction this effectively for the Hamming metric. The $\ell_1$ structure is very different. In a very handwavy sense, admitting JL-style reductions is linked to living in a Hilbert space.  

---

### Answer by username_1 on 2014-07-04. Score: 4

SVD and JL also extrapolates to future points differently as well.

That is, if you assume your data comes from some underlying distribution, in principle the SVD should remain "good" for any future points so long as they are sampled from the same distribution. On the other hand, the target dimension of JL depends on the number of points, meaning that applying a JL transform to additional points can increase the error probability.

This becomes relevant if, for instance, if you are using dimensionality reduction as a preprocessing step for some other algorithm. SVD bounds for training data may hold on test data, but JL's will not.

> **Comments:**
> **username_2**: This is a very good point.  

---

### Answer by username_3 on 2014-03-12. Score: 3

This is a follow-up to Suresh's answer - I googled a bit after reading his answer, and came up with the following understanding. I was originally going to post this as a comment to his answer, but it kept on increasing.

Please point out errors in the answer, I'm no expert in this field.

In some sense, JL and SVD are like apples and oranges.

1) The problems they solve are completely different. One is concerned with pairwise distances, the other with the best representation. One is worst case, the other is average case.

The subspace JL returns (JL isn't constructive, but lets assume it returned a best subspace) is the solution to the following optimization
$$\arg\min\limits\_{P} \left\{\sup\limits\_{u,v} \left(\Biggl\lvert 1- \frac{||Pu-Pv||\_2}{||u-v||\_2} \Biggl\rvert \right) \right\} \tag{1}$$

(This isn't precise, I'll comment more on this later)

The problem SVD is solving is (given a dimension $k$)
$$\arg\min\limits\_{P\text{ of dim k}} \left\{\text{Avg}\left(||u-Pu||\_2\right)\right\} $$

2) Inputs: Although both algorithms output subspaces, the inputs they need are different. JL requires a tolerance $\epsilon$ (what is the max error you are willing to tolerate between actual distances and distances in the subspace), while SVD requires number of dimensions.

3) JL is nonconstructive, SVD is constructive - this point is a bit vague, as the term constructive is not precisely defined. There are deterministic algorithms for computing the SVD, but the algorithm for finding a JL space is a randomized one - do random projections, if you fail, try again.

4) SVD is unique (the subspace may not be unique, but the objective value will be the same for all subspaces). Eqn(1) above isn't precise in the sense that JL doesn't actually talk about minimizing the discrepancy in the pairwise distances - it gives a guarantee about the existence of a smaller subspace where distances will be atmost $\epsilon$ different from their actual values. There could be many such subspaces, some better than the others.

(See comments for explanation regarding striked portions of the answer).

Edit: @john-myles-white has written a post about JL to verify its claims, and show how a projection can be constructed: <http://www.johnmyleswhite.com/notebook/2014/03/24/a-note-on-the-johnson-lindenstrauss-lemma/>

> **Comments:**
> **username_4**: There are a number of errors in your answer. (1) JL is extremely constructive: there are all kinds of algorithms for constructing the mapping (2) it doesn't preserve the difference but the relative difference (the ratio) (3) the JL lemma has been derandomized (4) JL works for *any* set of vectors: the construction is independent of the actual input. the only information needed is the *number* of vectors.  
> **username_3**: Thanks Suresh. I've incorporated all except your final suggestion. Feel free to edit the answer further. On the last point, I'm confused. You're saying the same map will work no matter what set of vectors I give you?  
> **username_5**: That's a slightly subtle point. Once you fix the error and the number of vectors, there is a fixed *probability distribution* on maps which will work with high probability for any set of vectors. Of course there is not deterministically fixed linear map that satisfies this property.  
> **username_6**: It's worth checking out Olivier Grisel's [scikit-learn implementation](http://scikit-learn.org/stable/auto_examples/plot_johnson_lindenstrauss_bound.html)  
> **username_2**: I'd like to add that not only is there no deterministic algorithm for constructing a JL embedding in general, it is typically computationally prohibitive to check that a matrix randomly generated according to the JL algorithm actually has the "almost isometry" property (even though it does with very high probability).  So I think it's reasonable to say that the JL theorem is not constructive.  Compare to the algorithm "choose a random real number between $0$ and $1$"; this gives a transcendental number with probability $1$, but I wouldn't call it constructive.  

---

