Similarity & High-Dimensional Search

Johnson–Lindenstrauss

Squash high-dimensional points into far fewer dimensions by random projection — and keep every pairwise distance almost exactly.

Each dot is a pair of points: true distance (x) vs distance after projection (y). The green diagonal is perfect preservation; the dashed lines are the ±ε band. Scrub to raise k and watch the cloud tighten.

What you're seeing

Start with n points living in 80 dimensions — far too many to plot or to search quickly. Multiply each by a random k×80 matrix (Gaussian entries, scaled by 1/√k) to land in just k dimensions. The scatter compares every pair's original distance (x-axis) with its distance after that projection (y-axis). At small k the dots scatter loosely around the diagonal; scrub the timeline to increase k and they snap onto it — distances barely change, even though almost all the dimensions are gone.

The rule

choose target dimension k ≈ (8 / ε²)·ln n
R = k×D matrix of i.i.d. N(0,1) entries
project: x ↦ (1/√k)·R·x          # D dims → k dims
claim:   ‖proj(x) − proj(y)‖ ≈ ‖x − y‖   for every pair

Strikingly, k depends on the number of points (logarithmically) but not on the original dimension D at all.

The guarantee

For a fixed vector u, the squared length of its projection, ‖(1/√k)Ru‖², has expectation exactly ‖u‖² — the scaling is chosen to make the projection length-preserving on average. The content of the lemma is concentration: that random quantity is a scaled chi-squared with k degrees of freedom, so its relative spread shrinks like 1/√k, and it lands within (1±ε) of the mean except with probability ≈ e^{−kε²/8}. Apply that to the u = x−y of all \binom{n}{2} pairs and union-bound: choosing k ≈ (8/ε²)·ln n makes every pairwise distance preserved within (1±ε) simultaneously, with high probability. On screen, "spread shrinks like 1/√k" is the cloud collapsing onto the diagonal as you raise k. Honest caveat: that bound is worst-case and pessimistic — in practice (as here) the distances concentrate noticeably faster than the formula promises.

The cost

In D dimsAfter JL (k dims) Store n pointsO(nD)O(nk) Distance / dot productO(D)O(k) Project (one-time)—O(n·k·D)

Because k is independent of D, JL collapses million-dimensional vectors to a few hundred coordinates while keeping the geometry any distance-based algorithm relies on. Every downstream operation — nearest-neighbor search, clustering, SVMs — then runs in the small dimension. Faster projections exist (sparse / Fast-JL using the Hadamard transform) that cut the O(kD) per-point cost.

In the wild

JL is the theoretical license behind "just use random projection": dimensionality reduction for nearest-neighbor search and LSH preprocessing, speeding up clustering and kernel methods, compressed sensing and sketching for numerical linear algebra (randomized SVD/least-squares), and privacy-preserving data release. Whenever someone reduces dimensions without looking at the data — no PCA, no training — and still trusts the distances, JL is why it works. It pairs naturally with the rest of this family: project with JL, then index with LSH.

Try this

Drag the timeline from k=2 up to k=64 and watch the orange (out-of-band) dots turn green and collapse onto the diagonal — concentration in action. Then loosen or tighten ε: a wider band forgives more, so fewer dimensions suffice; a tighter band demands a larger k for the same fraction preserved.

References

  1. Johnson, W. B. & Lindenstrauss, J. "Extensions of Lipschitz mappings into a Hilbert space." Contemporary Mathematics 26:189–206, 1984. The original lemma.
  2. Dasgupta, S. & Gupta, A. "An elementary proof of a theorem of Johnson and Lindenstrauss." Random Structures & Algorithms 22(1):60–65, 2003.
  3. Ailon, N. & Chazelle, B. "The Fast Johnson–Lindenstrauss Transform." STOC, 2006 — faster projections.
  4. Andoni, A. Advanced Algorithms (Columbia COMS 4995-8, 2021), Lectures 7–8 (dimension reduction). course materials.