exists_isJLEmbedding_of_pair_bound
Probabilistic method for JL embeddings. Let $\mu$ be a probability measure on $\Omega$, let $A : \Omega \to \mathbb{R}^{k\times d}$ be a measurable random matrix, let $\varepsilon\in\mathbb{R}$, and let $V$ be a finite subset of $\mathbb{R}^d$. Suppose that for every ordered pair $u, v \in V$ the bad event $\{\omega \mid \texttt{BadSingle}\,\varepsilon\,(A\,\omega)\,(u-v)\}$ is measurable and has probability at most $2\exp(-k\varepsilon^2/8)$, and that the union-bound failure probability satisfies \[ |V|^2 \cdot 2\exp(-k\varepsilon^2/8) < 1 . \] Then there exists a linear map $f : \mathbb{R}^d \to \mathbb{R}^k$ which is an $\varepsilon$-JL embedding of $V$, i.e.\ $(1-\varepsilon)\|u-v\|^2 \le \|f u - f v\|^2 \le (1+\varepsilon)\|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 exists_isJLEmbedding_of_pair_bound {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (A : Ω → Matrix (Fin k) (Fin d) ℝ) (hA_meas : Measurable A) (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d))) (hBadMeas : ∀ u ∈ V, ∀ v ∈ V, MeasurableSet {ω | BadSingle ε (A ω) (u - v)}) (hPair : ∀ u ∈ V, ∀ v ∈ V, (μ {ω | BadSingle ε (A ω) (u - v)}).toReal ≤ 2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) (hFail : (V.card : ℝ) ^ 2 * (2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) < 1) : ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k), IsJLEmbedding ε V f
- Source
- TCSlib, `exists_isJLEmbedding_of_pair_bound`
- 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.exists_isJLEmbedding_of_pair_bound← exists_isJLEmbedding_of_pair_bound (TCSlib/LearningTheory/JohnsonLindenstrauss/UnionBound.lean:270): verbatim
- Verified
- 16 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- instMeasurableSpaceMatrixFinReal_tCSlibMatrices as
m → n → αinherit a Pi measurable space structure. - jl_union_boundUnion bound for Johnson–Lindenstrauss distortion. Let $(\Omega,\mu)$ be a probability space, and let $A\colon\Omega\to\bbr^{k\times d}$ be…
- BadSingleFor a parameter $\varepsilon\in\mathbb{R}$, a matrix $A$, and a vector $x\in\mathbb{R}^d$, the predicate…
- BadPairGiven a $k \times d$ matrix $A$ and a finite set $V \subseteq \mathbb{R}^d$,
BadPair$\varepsilon\; V\; A$ holds when there… - 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…
- JLDistortionFor $\varepsilon \in \mathbb{R}$, vectors $u, v \in \mathbb{R}^d$, and their images $u', v' \in \mathbb{R}^k$,
JLDistortion…
- 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 /-- **Probabilistic method for JL (shared tail)** [DG03, proof of Thm 2.1]; [Ver18, proof of Thm 5.3.1]. Given a random matrix `A` whose per-pair distortion events `{ω | BadSingle ε (A ω) (u − v)}` are measurable and each have probability at most `2·exp(−kε²/8)`, and such that the union-bound failure probability `|V|² · 2 · exp(−kε²/8)` is strictly less than `1`, some realization `A ω` is an `ε`-JL embedding of `V`. This is the common tail of `johnson_lindenstrauss_of_gaussian` and `johnson_lindenstrauss_of_subgaussian`. **Proof sketch.** Step 1: the union bound `jl_union_bound` bounds the probability of the bad-pair event by `|V|² · 2 · exp(−kε²/8)`. Step 2: by hypothesis this is strictly less than `1`. Step 3: hence some sample `ω` is not bad — otherwise the bad-pair event would be the whole space, of probability `1`. Step 4: the linear map `(A ω).toEuclideanLin` of that witness is an `ε`-JL embedding of `V`, since every pair satisfies the distortion bound. -/ theorem exists_isJLEmbedding_of_pair_bound {Ω : Type*} [MeasurableSpace Ω] (μ : Measure Ω) [IsProbabilityMeasure μ] (A : Ω → Matrix (Fin k) (Fin d) ℝ) (hA_meas : Measurable A) (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d))) (hBadMeas : ∀ u ∈ V, ∀ v ∈ V, MeasurableSet {ω | BadSingle ε (A ω) (u - v)}) (hPair : ∀ u ∈ V, ∀ v ∈ V, (μ {ω | BadSingle ε (A ω) (u - v)}).toReal ≤ 2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) (hFail : (V.card : ℝ) ^ 2 * (2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) < 1) : ∃ f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k), IsJLEmbedding ε V f := by -- Step 1: Union bound over pairs. have hBP : (μ {ω | BadPair ε V (A ω)}).toReal ≤ (V.card : ℝ) ^ 2 * (2 * Real.exp (-(k : ℝ) * ε ^ 2 / 8)) := jl_union_bound μ A hA_meas V ε hBadMeas hPair -- Step 2: Failure probability strictly less than 1. have hBadLT1 : (μ {ω | BadPair ε V (A ω)}).toReal < 1 := lt_of_le_of_lt hBP hFail -- Step 3: Therefore some ω is *not* bad. have hGood : ∃ ω, ¬ BadPair ε V (A ω) := by by_contra hNG push_neg at hNG have hUniv : {ω | BadPair ε V (A ω)} = Set.univ := Set.eq_univ_of_forall hNG rw [hUniv, measure_univ] at hBadLT1 simp at hBadLT1 -- Step 4: Extract witness, produce embedding. obtain ⟨ω, hω⟩ := hGood refine ⟨(A ω).toEuclideanLin, ?_⟩ intro u hu v hv by_contra hbd exact hω ⟨u, hu, v, hv, hbd⟩