BadPair
defimported Lean
Given a $k \times d$ matrix $A$ and a finite set
$V \subseteq \mathbb{R}^d$, BadPair $\varepsilon\; V\; A$ holds when
there exists some ordered pair $(u, v) \in V \times V$ whose images under $A$
fail the distortion predicate, i.e.\ the projection distorts that pair by
more than a factor of $\varepsilon$.
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 BadPair (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d))) (A : Matrix (Fin k) (Fin d) ℝ) : Prop
- Defined in
- TCSlib, `BadPair`
- 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.BadPair← BadPair (TCSlib/LearningTheory/JohnsonLindenstrauss/UnionBound.lean:90): 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 2
- 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…
- 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 in set_option autoImplicit false in open MeasureTheory ProbabilityTheory Real NNReal Matrix Finset in variable {d k : ℕ} in /-- The "bad event" for the whole set `V` under the matrix `A`: some ordered pair `(u, v) ∈ V × V` fails the `(1 ± ε)` distortion bound `JLDistortion` under `A` [DG03, proof of Thm 2.1]. -/ noncomputable def BadPair (ε : ℝ) (V : Finset (EuclideanSpace ℝ (Fin d))) (A : Matrix (Fin k) (Fin d) ℝ) : Prop := ∃ u ∈ V, ∃ v ∈ V, ¬ JLDistortion ε u v (A.toEuclideanLin u) (A.toEuclideanLin v)