AFTD Auto-Formalizing Theoretical Domains

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