jl-sparse-moment-bound-stochastic-domination
IN premise — summaries/2026/08/24/wiki-JohnsonE28093Lindenstrauss_lemma-chunk-2.md
Created 2026-08-24T17:11:13+00:00
In Achlioptas's sparse JL, the key step is the moment bound E[Qᵢ^{2k}] ≤ E[Z^{2k}] = (2k−1)!! for each row-sum Qᵢ, where Z ~ N(0,1), establishing stochastic domination that enables the Chernoff concentration argument.
Summary
In Achlioptas's sparse random projection scheme, each row's sum is shown to have tail behavior no worse than a Gaussian, which is the single inequality that lets the whole construction inherit the strong concentration guarantees needed to preserve high-dimensional distances after projection. Without this domination, the Chernoff-style bound that makes the embedding reliable simply doesn't go through.