jl-sparse-achlioptas-entry-distributions

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

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

Achlioptas's sparse JL transform (2003) uses matrix entries from {+1 w.p. 1/2, 0 w.p. 1/2, −1 w.p. 1/2} or {+√3 w.p. 1/6, 0 w.p. 2/3, −√3 w.p. 1/6}, stochastically dominated by Gaussians in even moments, reducing non-zeros per column to O(1) while preserving the same concentration guarantees.

Summary

Achlioptas showed that a dimensionality-reduction matrix can be filled with mostly zeros and a few small random values instead of dense random numbers, yet still preserve distances just as reliably as the full matrix. The practical payoff is that each column only needs a constant number of multiplications rather than a whole column's worth, making the transform dramatically cheaper to run without sacrificing the accuracy guarantees.