Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

up vote 19 down vote accepted

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.

share|improve this answer
    
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)? –  J.A Mar 11 at 22:34
2  
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 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? –  J.A Mar 22 at 22:40
1  
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 at 23:09
    
Thank you for the comment answer –  J.A Mar 23 at 11:59

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/

share|improve this answer
5  
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 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 at 2:48
3  
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 at 3:46
    
It's worth checking out Olivier Grisel's scikit-learn implementation –  KLDavenport Mar 26 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 at 13:17

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.

share|improve this answer
    
This is a very good point. –  Paul Siegel Jul 4 at 13:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.