johnson_lindenstrauss
theoremverifiedformalizationimported Lean
Johnson–Lindenstrauss flattening lemma. Let $0 < \varepsilon < 1$ and let $n \ge 2$ be an integer. Suppose the target dimension $k$ satisfies $k \ge 32\,\log n / \varepsilon^2$. Then for every finite set $V \subseteq \bbr^d$ of at most $n$ points there exists a linear map $f : \bbr^d \to \bbr^k$ that is an $\varepsilon$-JL embedding of $V$; that is, \[ (1 - \varepsilon)\,\norm{u - v}^2 \;\le\; \norm{f(u) - f(v)}^2 \;\le\; (1 + \varepsilon)\,\norm{u - v}^2 \] for all $u, v \in V$.
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 (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1) (n : ℕ) (hn : 2 ≤ n) (hk : (32 : ℝ) * Real.log n / ε ^ 2 ≤ k) (V : Finset (EuclideanSpace ℝ (Fin d))) (hV : V.card ≤ n) : ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k), IsJLEmbedding ε V f
- Formalizes
- Johnson–Lindenstrauss flattening lemma, as formalized in TCSlib (`johnson_lindenstrauss`)
- 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← johnson_lindenstrauss (TCSlib/LearningTheory/JohnsonLindenstrauss/Main.lean:328): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- johnson_lindenstrauss_of_gaussianJohnson–Lindenstrauss embedding from a Gaussian matrix. Fix dimensions $d$ and $k$ with $k \ge 1$, a distortion parameter…
- instMeasurableSpaceMatrixFinReal_tCSlibMatrices as
m → n → αinherit a Pi measurable space structure. - measurableSet_badSingleMeasurability of the single-vector distortion event. Fix a vector $x\in\bbr^d$ and a real number $\varepsilon$, and let…
- exists_iid_gaussian_matrixExistence of a Gaussian matrix with independent entries. Let $k \ge 1$ and $d \ge 0$ be integers. Then there is a probability space…
- jl_failure_bound_of_dimNumerical failure-probability bound for Johnson–Lindenstrauss. Let $\varepsilon > 0$ and let $n \ge 2$ be an integer, and suppose the…
- 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…
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 /-- **Johnson–Lindenstrauss flattening lemma (standard form)** [DG03, Thm 2.1]; [Ver18, Thm 5.3.1]; origin [JL84, Lemma 1]. For any `0 < ε < 1`, any `n ≥ 2`, and target dimension `k` with `k ≥ 32 · log n / ε²`, every finite set `V` of at most `n` points in `ℝ^d` admits a linear embedding `f : ℝ^d → ℝ^k` preserving pairwise squared distances up to factor `(1 ± ε)`. The embedding is a realization of a matrix with iid `N(0, 1/k)` entries; the proof is axiom-free. Deviation: the dimension bound is `k ≥ 32 · log n / ε²`, whereas [DG03] obtains `k ≥ 4 (ε²/2 − ε³/3)⁻¹ log n` and [Ver18] states `k ≥ C ε⁻² log n` for an unspecified constant; the conclusion is stated for squared distances (see `johnson_lindenstrauss_dist` for the distance form). The `32` is not tight: it is chosen for cleanness of the numerical bookkeeping, giving `|V|² · 2 · exp(-kε²/8) ≤ 1/2`. **Proof sketch.** Step 1: numerical bookkeeping (`jl_failure_bound_of_dim`): the dimension hypothesis gives `k > 0` and the union-bound failure probability `|V|² · 2 · exp(−kε²/8)` is strictly less than `1`. Step 2: realize an iid `N(0, 1/k)` matrix `A` on a probability space (`exists_iid_gaussian_matrix`) and check that its per-pair bad events are measurable (`measurableSet_badSingle`). Step 3: the structural theorem `johnson_lindenstrauss_of_gaussian` (single-vector concentration, union bound, probabilistic method) extracts a good realization. -/ theorem johnson_lindenstrauss (ε : ℝ) (hε_pos : 0 < ε) (hε_lt : ε < 1) (n : ℕ) (hn : 2 ≤ n) (hk : (32 : ℝ) * Real.log n / ε ^ 2 ≤ k) (V : Finset (EuclideanSpace ℝ (Fin d))) (hV : V.card ≤ n) : ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k), IsJLEmbedding ε V f := by -- Step 1: numerical bookkeeping: k > 0 and union-bound failure prob < 1. obtain ⟨hk_pos, hFail⟩ := jl_failure_bound_of_dim ε hε_pos n hn hk V hV -- Step 2: obtain a Gaussian probability space; the per-pair bad events are measurable. obtain ⟨Ω, _, μ, _, A, hA_meas, hA_law, hRowEntryIndep, hRowsIndep⟩ := exists_iid_gaussian_matrix hk_pos d have hBadMeas : ∀ u ∈ V, ∀ v ∈ V, MeasurableSet {ω | BadSingle ε (A ω) (u - v)} := fun u _ v _ => measurableSet_badSingle A hA_meas (u - v) ε -- Step 3: invoke the structural theorem `_of_gaussian`. exact johnson_lindenstrauss_of_gaussian hk_pos μ A hA_meas hA_law hRowEntryIndep hRowsIndep ε hε_pos hε_lt V hBadMeas hFail