JLDistortion
defimported Lean
For $\varepsilon \in \mathbb{R}$, vectors $u, v \in \mathbb{R}^d$, and their
images $u', v' \in \mathbb{R}^k$, JLDistortion asserts the two-sided
squared-distance inequality
\[
(1 - \varepsilon)\,\|u - v\|^2 \;\le\; \|u' - 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 noncomputable def JLDistortion (ε : ℝ) (u v : EuclideanSpace ℝ (Fin d)) (u' v' : EuclideanSpace ℝ (Fin k)) : Prop
- Defined in
- TCSlib, `JLDistortion`
- 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.JLDistortion← JLDistortion (TCSlib/LearningTheory/JohnsonLindenstrauss/UnionBound.lean:72): verbatim
- Verified
- 07 Oct 2026
- Axioms
- none listed
- Used by 5
- 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…
- 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…
- BadPairGiven a $k \times d$ matrix $A$ and a finite set $V \subseteq \mathbb{R}^d$,
BadPair$\varepsilon\; V\; A$ holds when there… - 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…
- JLDistortion.of_not_badDistortion bound from a controlled single-vector event. Let $\varepsilon \in \bbr$, let $u, v \in \bbr^d$, and let $A$ be a real…
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 /-- The `(1 ± ε)` two-sided distortion bound for a single pair of points: the squared distance between the images `u'`, `v'` lies between `(1 − ε)` and `(1 + ε)` times the squared distance between `u` and `v` [DG03, Thm 2.1]; origin [JL84]. Deviation: stated for squared distances (the distance form is recovered in `JohnsonLindenstrauss.Main`). -/ noncomputable def JLDistortion (ε : ℝ) (u v : EuclideanSpace ℝ (Fin d)) (u' v' : EuclideanSpace ℝ (Fin k)) : Prop := (1 - ε) * ‖u - v‖ ^ 2 ≤ ‖u' - v'‖ ^ 2 ∧ ‖u' - v'‖ ^ 2 ≤ (1 + ε) * ‖u - v‖ ^ 2