# When to use the Johnson-Lindenstrauss lemma over SVD?

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?

-

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.

-
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 en.wikipedia.org/wiki/Johnson%E2%80%93Lindenstrauss_lemma)? – Turbo Mar 11 '14 at 22:34
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 Mar 11 '14 at 23:40
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 Mar 22 '14 at 22:40
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 Mar 22 '14 at 23:09
Thank you for the comment answer – Turbo Mar 23 '14 at 11:59

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.

-
This is a very good point. – Paul Siegel Jul 4 '14 at 13:18

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/

-
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 Mar 12 '14 at 1:43
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 Mar 12 '14 at 2:48
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 Mar 12 '14 at 3:46
It's worth checking out Olivier Grisel's scikit-learn implementation – KLDavenport Mar 26 '14 at 3:12
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 Jul 4 '14 at 13:17