johnson_lindenstrauss_of_gaussian
theoremverifiedimported Lean
Johnson–Lindenstrauss embedding from a Gaussian matrix. Fix dimensions $d$ and $k$ with $k \ge 1$, a distortion parameter $\varepsilon \in (0,1)$, and a finite set of points $V \subseteq \bbr^d$. Let $A$ be a random $k \times d$ matrix whose entries $A_{ij}$ are independent Gaussian random variables, each with mean $0$ and variance $1/k$. If the union-bound quantity satisfies \[ |V|^2 \cdot 2\exp\!\left(-\,k\varepsilon^2/8\right) < 1, \] then there exists a linear map $f : \bbr^d \to \bbr^k$ that is an $\varepsilon$-JL embedding of $V$: for every pair $u, v \in V$, \[ (1-\varepsilon)\,\|u-v\|^2 \;\le\; \|f(u)-f(v)\|^2 \;\le\; (1+\varepsilon)\,\|u-v\|^2. \]
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in theorem johnson_lindenstrauss_of_gaussian (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) μ) (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1) (V : Finset (EuclideanSpace ℝ (Fin d))) (hBadMeas : ∀ u ∈ V, ∀ v ∈ V, MeasurableSet {ω | BadSingle ε (A ω) (u - v)}) (hFail : (V.card : ℝ) ^ 2 * (2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) < 1) : ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k), IsJLEmbedding ε V f
- Source
- TCSlib, `johnson_lindenstrauss_of_gaussian`
- 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.johnson_lindenstrauss_of_gaussian← johnson_lindenstrauss_of_gaussian (TCSlib/LearningTheory/JohnsonLindenstrauss/UnionBound.lean:319): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- exists_isJLEmbedding_of_pair_boundProbabilistic method for JL embeddings. Let $\mu$ be a probability measure on $\Omega$, let $A : \Omega \to \mathbb{R}^{k\times d}$ be a…
- instMeasurableSpaceMatrixFinReal_tCSlibMatrices as
m → n → αinherit a Pi measurable space structure. - jl_concentration_singleJohnson–Lindenstrauss concentration for a single vector. Let $k \ge 1$ and let $A$ be a random $k \times d$ matrix whose entries $A_{ij}$…
- BadSingleFor a parameter $\varepsilon\in\mathbb{R}$, a matrix $A$, and a vector $x\in\mathbb{R}^d$, the predicate…
- IsJLEmbeddingA linear map $f : \mathbb{R}^d \to_L[\mathbb{R}] \mathbb{R}^k$ is an $\varepsilon$-JL embedding of a finite set $V$ if, for every…
- Used by 1
- johnson_lindenstraussJohnson–Lindenstrauss flattening lemma. Let $0 < \varepsilon < 1$ and let $n \ge 2$ be an integer. Suppose the target dimension $k$…
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 /-- **Structural JL via the probabilistic method (Gaussian)** [DG03, proof of Thm 2.1]; [Ver18, proof of Thm 5.3.1]. Given a random matrix with iid `N(0, 1/k)` entries on a probability space (rows independent, entries independent within each row) AND that the union-bound failure probability `|V|² · 2 · exp(-kε²/8)` is strictly less than `1`, there exists a realization of the random matrix that is an `ε`-JL embedding of `V`. **Proof sketch.** Step 1: the single-vector concentration bound `jl_concentration_single`, applied to each difference `u − v` with `u, v ∈ V`, gives the per-pair bound `2·exp(−kε²/8)`. Step 2: the shared probabilistic-method lemma `exists_isJLEmbedding_of_pair_bound` (union bound, failure probability `< 1`, extraction of a good sample) produces the embedding. -/ theorem johnson_lindenstrauss_of_gaussian (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) μ) (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1) (V : Finset (EuclideanSpace ℝ (Fin d))) (hBadMeas : ∀ u ∈ V, ∀ v ∈ V, MeasurableSet {ω | BadSingle ε (A ω) (u - v)}) (hFail : (V.card : ℝ) ^ 2 * (2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) < 1) : ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k), IsJLEmbedding ε V f := by -- Step 1: Concentration per pair (Gaussian single-vector bound). have hPair : ∀ u ∈ V, ∀ v ∈ V, (μ {ω | BadSingle ε (A ω) (u - v)}).toReal ≤ 2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8) := fun u _ v _ => jl_concentration_single hk_pos μ A hA_meas hA_law hRowEntryIndep hRowsIndep (u - v) ε hε_pos hε_lt -- Step 2: Union bound and probabilistic method. exact exists_isJLEmbedding_of_pair_bound μ A hA_meas ε V hBadMeas hPair hFail