AFTD Auto-Formalizing Theoretical Domains

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.
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
See it in the graphDiscuss this resultChallenge it