the Johnson-Lindenstrauss lemma
/ JON-son LIN-den-strowss /
Here is a fact that sounds too good to be true: if you have a cloud of points living in a thousand-dimensional space, you can squash it down into just a few dozen dimensions, AT RANDOM, and almost all the distances between points survive nearly unchanged. The shape of the cloud — who is near whom, how far apart things are — is preserved even though you threw away most of the coordinates. The Johnson-Lindenstrauss lemma is the precise, provable statement of this near-miracle, and it underlies a whole toolbox of dimension reduction.
The lemma says: for any set of n points in high-dimensional space and any tolerance epsilon, there is a linear map into a target dimension k of order (log n) / epsilon^2 that preserves every pairwise distance to within a factor of 1 plus or minus epsilon. Strikingly, the target dimension k depends on the NUMBER of points n (only logarithmically) and the accuracy epsilon — but NOT on the original dimension, however huge. Even more striking, the map can be a simple RANDOM projection: multiply each point by a random matrix (Gaussian entries, or even random plus-or-minus-1 entries) and rescale; with high probability that random map works. The proof is a concentration-of-measure argument — a random projection of a fixed vector has length tightly concentrated around its expected value, so distances barely move.
This lemma is the theoretical bedrock under random projections, sketching, and much of randomized numerical linear algebra (including randomized SVD): it certifies that you can compress data first and compute later, with controlled distortion. The honest fine print: the 1/epsilon^2 dependence is steep — halving the allowed distortion quadruples the needed dimension — so for high accuracy k is not tiny. The guarantee preserves pairwise EUCLIDEAN distances (and approximately dot products), not arbitrary structure, and it is a probabilistic, worst-case bound: a given random projection works with high probability, not certainty, and the log n factor means it is most useful when you have many points but want to keep distances, not when you need exact geometry.
You have n = 10,000 documents each represented as a 100,000-dimensional word-count vector and want to cluster by similarity. Choosing epsilon = 0.2, the lemma promises a random projection into k of order (log 10000) / 0.04 = about 230 dimensions that keeps every pairwise distance within 20%. Clustering then runs hundreds of times faster on the 230-dimensional data with essentially the same result.
A random projection shrinks dimension while preserving all pairwise distances within 1 +/- epsilon.
The target dimension depends on the NUMBER of points (logarithmically) and on 1/epsilon^2, not on the original dimension — but the 1/epsilon^2 cost is steep, and the guarantee preserves Euclidean distances with high probability, not exact geometry with certainty.