jl_concentration_single
theoremverifiedimported Lean
Johnson–Lindenstrauss concentration for a single vector. Let $k \ge 1$ and let $A$ be a random $k \times d$ matrix whose entries $A_{ij}$ are independent Gaussian random variables, each distributed as $\mathcal{N}(0, 1/k)$. Then for every fixed vector $x \in \bbr^d$ and every $\varepsilon$ with $0 < \varepsilon < 1$, the probability that $A$ distorts the squared norm of $x$ by more than a factor $\varepsilon$ satisfies \[ \bbP\!\left[\, \bigl|\,\|Ax\|^2 - \|x\|^2\,\bigr| > \varepsilon\,\|x\|^2 \,\right] \;\le\; 2\,\exp\!\left(-\frac{k\,\varepsilon^2}{8}\right). \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in theorem jl_concentration_single (hk_pos : 0 < k) {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (A : Ω → Matrix (Fin k) (Fin d) ℝ) (hA_meas : Measurable A) (hA_law : ∀ (i : Fin k) (j : Fin d), Measure.map (fun ω => A ω i j) μ = gaussianReal 0 ⟨1 / k, by positivity⟩) (hRowEntryIndep : ∀ i : Fin k, iIndepFun (fun (j : Fin d) ω => A ω i j) μ) (hRowsIndep : iIndepFun (fun (i : Fin k) (ω : Ω) (j : Fin d) => A ω i j) μ) (x : EuclideanSpace ℝ (Fin d)) (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1) : (μ {ω | BadSingle ε (A ω) x}).toReal ≤ 2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)
- Source
- TCSlib, `jl_concentration_single`
- Lean proof
- By Ganesh Sankar, from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Copyright (c) 2026 Ganesh Sankar. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.jl_concentration_single← jl_concentration_single (TCSlib/LearningTheory/JohnsonLindenstrauss/UnionBound.lean:115): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- instMeasurableSpaceMatrixFinReal_tCSlibMatrices as
m → n → αinherit a Pi measurable space structure. - jl_concentration_single_via_chi_squaredJohnson–Lindenstrauss concentration for a single vector. Let $k \ge 1$, and let $A$ be a random $k \times d$ real matrix on a probability…
- BadSingleFor a parameter $\varepsilon\in\mathbb{R}$, a matrix $A$, and a vector $x\in\mathbb{R}^d$, the predicate…
- chi_squared_tailChi-squared tail bound for independent $N(0,1/k)$ variables. Let $\mu$ be a probability measure on $\Omega$, let $k \ge 1$, and let…
- centered_chi_squared_stepCentered chi-squared MGF bound. Let $(\Omega,\mu)$ be a probability space and let $k$ be a positive natural number. Suppose…
- instMeasurableSpaceMatrixFinReal_tCSlibMatrices as
- Used by 1
- johnson_lindenstrauss_of_gaussianJohnson–Lindenstrauss embedding from a Gaussian matrix. Fix dimensions $d$ and $k$ with $k \ge 1$, a distortion parameter…
Lean source view module on GitHub
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in /-- **JL concentration (single vector)** [DG03, Lemma 2.2]. If `A_ij ~ N(0, 1/k)` are i.i.d. Gaussian (with rows mutually independent and entries iid within each row), then for any fixed `x : ℝ^d` and any `0 < ε < 1`, `ℙ[ |‖Ax‖² − ‖x‖²| > ε · ‖x‖² ] ≤ 2 · exp(−k ε² / 8).` Deviation: the two-sided bound `2 exp(−kε²/8)` replaces the source's `exp(k/2 (1 − β + ln β))` tails (see `chi_squared_tail`). This is a wrapper around `jl_concentration_single_via_chi_squared` from `JohnsonLindenstrauss.ConcentrationBound`, fully proved (no axioms) via `centered_chi_squared_step` + a Bernstein/Chernoff argument. -/ theorem jl_concentration_single (hk_pos : 0 < k) {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (A : Ω → Matrix (Fin k) (Fin d) ℝ) (hA_meas : Measurable A) (hA_law : ∀ (i : Fin k) (j : Fin d), Measure.map (fun ω => A ω i j) μ = gaussianReal 0 ⟨1 / k, by positivity⟩) (hRowEntryIndep : ∀ i : Fin k, iIndepFun (fun (j : Fin d) ω => A ω i j) μ) (hRowsIndep : iIndepFun (fun (i : Fin k) (ω : Ω) (j : Fin d) => A ω i j) μ) (x : EuclideanSpace ℝ (Fin d)) (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1) : (μ {ω | BadSingle ε (A ω) x}).toReal ≤ 2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8) := jl_concentration_single_via_chi_squared hk_pos μ A hA_meas hA_law hRowEntryIndep hRowsIndep x ε hε_pos hε_lt