Random Projections and Johnson-Lindenstrauss
The Johnson-Lindenstrauss lemma says a random low-dimensional projection nearly preserves pairwise distances between points, giving a cheap alternative to PCA for shrinking very high-dimensional data.
Prerequisites: Probabilistic PCA
Reducing dimensions usually means computing something like PCA, which requires knowing the whole dataset's covariance structure. Random projections skip that entirely: multiply the data by a random matrix of the target lower dimension, and the Johnson-Lindenstrauss (JJ) lemma guarantees that, with high probability, pairwise distances between points are nearly preserved — no data-dependent computation required at all.
The Johnson-Lindenstrauss lemma says that projecting n points onto a random subspace of dimension roughly proportional to (not the original dimension) preserves all pairwise distances up to a small, controllable distortion — so a random matrix, requiring no knowledge of the data at all, can shrink dimensionality almost as reliably as a carefully-computed one for many tasks.
Why it's useful despite being "dumb"
Because the required target dimension only grows with the logarithm of the number of points, not the original number of features, random projection can compress a dataset with a million original features down to a few thousand dimensions while barely disturbing distances between a few thousand points — and it costs one matrix multiply, with no eigendecomposition or iterative fitting needed, making it attractive for very large or streaming datasets where PCA is too slow to run repeatedly.
Worked example
A text dataset represents each of 10,000 documents as a vector over 500,000 word features. The JL lemma suggests that projecting onto roughly 600–800 random dimensions (a function of and the desired distortion tolerance) should preserve pairwise document distances within about 10-20%. In practice, a nearest-neighbor search that used to require comparing 500,000-dimensional vectors can be done almost as accurately in the ~700-dimensional projected space, at a fraction of the memory and compute cost.
JL guarantees distances are preserved on average across all pairs with high probability, not that every single pairwise distance is preserved exactly — a small number of pairs can still see larger distortion, so random projection is a good fit for aggregate tasks like nearest-neighbor search but a poor substitute when one specific distance needs to be exact.
Related concepts
Practice in interviews
Further reading
- Johnson and Lindenstrauss, 'Extensions of Lipschitz Mappings into a Hilbert Space'