jl-proof-chi-square-concentration-union-bound

IN premise — summaries/2026/08/24/wiki-JohnsonE28093Lindenstrauss_lemma.md

Created 2026-08-24T17:11:14+00:00

The classical JL proof relies on three steps: (1) the squared norm ratio ‖ĥx‖²/‖x‖² is χ²(k)-distributed under random orthogonal projection, (2) a chi-square concentration inequality bounds Pr(r ∈ (1±ε)·k) ≥ 1 − 2e^(−(k/2)(ε²/2 − ε³/3)), and (3) a union bound over all N(N−1)/2 pairs ensures simultaneous preservation.

Summary

This captures the three-part reasoning chain behind the Johnson-Lindenstrauss guarantee: a distributional fact about how projection affects distances, a probability bound showing individual distances are preserved with high likelihood, and a union-bound step that stitches those individual guarantees together so that every single pair of points in the dataset is preserved simultaneously, not just on average. The practical upshot is that you can project high-dimensional data into far fewer dimensions while keeping all pairwise relationships intact, which is what makes random projection a valid dimensionality-reduction tool.