AFTD Auto-Formalizing Theoretical Domains

JLDistortion.of_not_bad

theoremverifiedimported Lean

Distortion bound from a controlled single-vector event. Let $\varepsilon \in \bbr$, let $u, v \in \bbr^d$, and let $A$ be a real $k \times d$ matrix, acting as a linear map $\bbr^d \to \bbr^k$. Suppose the difference $u - v$ does not trigger the bad distortion event for $A$; that is, the squared-norm distortion of $u-v$ stays within the allowed band, \[ \bigl|\,\norm{A(u-v)}^2 - \norm{u-v}^2\,\bigr| \;\le\; \varepsilon\,\norm{u-v}^2 . \] Then the images $Au$ and $Av$ satisfy the two-sided single-pair distortion bound \[ (1 - \varepsilon)\,\norm{u - v}^2 \;\le\; \norm{Au - Av}^2 \;\le\; (1 + \varepsilon)\,\norm{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
lemma JLDistortion.of_not_bad (ε : ℝ) (u v : EuclideanSpace ℝ (Fin d))
    (A : Matrix (Fin k) (Fin d) ℝ)
    (h : ¬ BadSingle ε A (u - v)) :
    JLDistortion ε u v (A.toEuclideanLin u) (A.toEuclideanLin v)
Source
TCSlib, `JLDistortion.of_not_bad`
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
Classical.choiceQuot.soundpropext
Built on 2
  • JLDistortionFor $\varepsilon \in \mathbb{R}$, vectors $u, v \in \mathbb{R}^d$, and their images $u', v' \in \mathbb{R}^k$, JLDistortion…
  • BadSingleFor a parameter $\varepsilon\in\mathbb{R}$, a matrix $A$, and a vector $x\in\mathbb{R}^d$, the predicate…
Used by 1
  • 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…

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory ProbabilityTheory Real NNReal Matrix Finset invariable {d k : ℕ} in/-- If the matrix `A` does not distort the difference vector `u − v` by more than a factor `ε` (the negation of `BadSingle ε A (u − v)`), then the pair `(u, v)` satisfies the `(1 ± ε)` distortion bound `JLDistortion` under `A`. -/lemma JLDistortion.of_not_bad (ε : ℝ) (u v : EuclideanSpace ℝ (Fin d))    (A : Matrix (Fin k) (Fin d) ℝ)    (h : ¬ BadSingle ε A (u - v)) :    JLDistortion ε u v (A.toEuclideanLin u) (A.toEuclideanLin v) := by  -- `BadSingle ε A (u-v)` says `ε ‖u-v‖² < |‖A(u-v)‖² - ‖u-v‖²|`.  -- Its negation plus `A.toEuclideanLin (u-v) = A.toEuclideanLin u - A.toEuclideanLin v`  -- gives both sides of `JLDistortion`.  unfold BadSingle at h  push_neg at h  rw [map_sub] at *  refine ⟨?_, ?_⟩  · -- (1 - ε) ‖u-v‖² ≤ ‖A(u-v)‖²    have := abs_le.mp h    have h1 := sq_nonneg ‖u - v‖    have h2 := sq_nonneg ‖A.toEuclideanLin u - A.toEuclideanLin v‖    linarith [this.1, this.2]  · -- ‖A(u-v)‖² ≤ (1 + ε) ‖u-v‖²    have := abs_le.mp h    linarith [this.1, this.2]
See it in the graphDiscuss this resultChallenge it