IsJLEmbedding
defimported Lean
A 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 ordered
pair $(u, v) \in V \times V$, the pair $(f(u), f(v))$ satisfies
JLDistortion $\varepsilon\; u\; v$.
Statement
set_option relaxedAutoImplicit false in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in noncomputable def IsJLEmbedding (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d))) (f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k)) : Prop
- Defined in
- TCSlib, `IsJLEmbedding`
- 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.IsJLEmbedding← IsJLEmbedding (TCSlib/LearningTheory/JohnsonLindenstrauss/UnionBound.lean:81): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 1
- JLDistortionFor $\varepsilon \in \mathbb{R}$, vectors $u, v \in \mathbb{R}^d$, and their images $u', v' \in \mathbb{R}^k$,
JLDistortion…
- JLDistortionFor $\varepsilon \in \mathbb{R}$, vectors $u, v \in \mathbb{R}^d$, and their images $u', v' \in \mathbb{R}^k$,
- Used by 3
- 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…
- johnson_lindenstrauss_of_gaussianJohnson–Lindenstrauss embedding from a Gaussian matrix. Fix dimensions $d$ and $k$ with $k \ge 1$, a distortion parameter…
- 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 /-- A linear map `f : ℝ^d → ℝ^k` is an **ε-JL embedding** of the finite set `V` if it preserves all pairwise squared distances up to factor `(1 ± ε)`, i.e. `JLDistortion ε u v (f u) (f v)` for all `u, v ∈ V` [DG03, Thm 2.1]; origin [JL84]. Deviation: only linear maps are considered, and distances are squared. -/ noncomputable def IsJLEmbedding (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d))) (f : EuclideanSpace ℝ (Fin d) →ₗ[ℝ] EuclideanSpace ℝ (Fin k)) : Prop := ∀ u ∈ V, ∀ v ∈ V, JLDistortion ε u v (f u) (f v) -- `BadSingle` is defined in `JohnsonLindenstrauss.RowDistribution`; re-exported here.