Distributional Johnson–Lindenstrauss norm preservation

Combining the two one-sided chi-squared tail bounds of JL.ChiSquared via a union bound gives the two-sided distributional JL guarantee, stated here in its core chi-squared form: with S = ∑ gᵢ² a sum of k i.i.d. squared standard Gaussians,

P( S ∉ ((1-ε)k, (1+ε)k) ) ≤ 2·exp(-(ε² - ε³) k / 4).

Since ‖f x‖² / ‖x‖² = S / k for the Gaussian random projection f (Gaussian rotation invariance), this is exactly the statement that f preserves the squared norm of any fixed vector to within a factor 1 ± ε, except with the stated failure probability.

theorem JL.chiSq_concentration (k : ℕ) {ε : ℝ} (h0 : 0 < ε) (h1 : ε < 1) : (gaussianVec k).real {ω : Fin k → ℝ | (1 + ε) * ↑k ≤ chiSq k ω ∨ chiSq k ω ≤ (1 - ε) * ↑k} ≤ 2 * Real.exp (-(ε ^ 2 - ε ^ 3) * ↑k / 4)

Two-sided chi-squared concentration / JL norm preservation. The probability that the chi-squared sum leaves the window ((1-ε)k, (1+ε)k) is at most 2·exp(-(ε² - ε³) k / 4).

theorem JL.jl_norm_preservation (k : ℕ) (hk : 0 < k) {ε : ℝ} (h0 : 0 < ε) (h1 : ε < 1) : (gaussianVec k).real {ω : Fin k → ℝ | ε ≤ |chiSq k ω / ↑k - 1|} ≤ 2 * Real.exp (-(ε ^ 2 - ε ^ 3) * ↑k / 4)

The same guarantee phrased through the normalised squared norm S / k: the relative deviation |S/k - 1| reaches ε with probability at most 2·exp(-(ε² - ε³) k / 4).