Lemma 7.2, p.17 — for expander walks,
ProvedDetANN.lemma_7_2approximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be an undirected -regular multigraph on () whose normalized adjacency matrix satisfies for every with , where . Fix an integer and let be the tuple of endpoints of all walks of length from . Choose uniformly in and a uniform occurrence from . For vectors let , and . With ,
It replaces Lemma 5.1: observing one block changes the expected location of the returned point only by an amount controlled by the expansion of .
Differences from the source:
- generalization: the answers x_v ∈ P of the local structures and a nearest neighbor x⋆ → arbitrary vectors x_v, x⋆ ∈ ℝ^d; reason: the argument uses no property of these vectors
- generalization: the graph of Lemma 7.1 (Δ ≥ 2, θ₀ ∈ (0, 1)) → any undirected Δ-regular multigraph on [d] with Δ ≥ 1 whose W contracts mean-zero vectors by some θ₀ ∈ [0, 1); reason: the graph of Lemma 7.1 is such a graph
- encoding: expectations over V and a uniform occurrence; ‖Wf‖₂ ≤ θ₀‖f‖₂ → finite uniform averages over [d] × walks; Σ_u (Wf)_u² ≤ θ₀² Σ_v f_v²; reason: the averages are the expectations; the squared bound is equivalent for θ₀ ≥ 0
Preamble
import Mathlib import Definitions.Def_DetANN_Multigraph import Definitions.Def_DetANN_TupleFamily
Formal statement
namespace DetANN
/-- **Lemma 7.2** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), p.17).
Let `W` be the normalized adjacency matrix of an undirected `Δ`-regular multigraph on `[d]` with
`‖W f‖ ≤ θ₀‖f‖` for every mean-zero `f`, `0 ≤ θ₀ < 1`, and let `ℓ ≥ 1`. For the walk family (tuple of
`v` = endpoints of all length-`ℓ` walks from `v`) and `ρ = θ₀^ℓ < 1`:
`E_I ‖a_I − a‖² ≤ ρ²/(1 − ρ²) · 𝒱`.
**Formalization Note.** The walk family is `S = walkEnd nbr ℓ : [d] → (Fin ℓ → Fin Δ) → [d]`;
expectations are finite averages as in `DetANN.TupleFamily`. The answers `x_v` and the point `x⋆` are
arbitrary vectors of `ℝ^d` (the argument uses no property of them), and `θ₀ = 0` and any `Δ ≥ 1`
are allowed (the paper: `θ₀ ∈ (0, 1)`, `Δ ≥ 2`). The spectral hypothesis is stated squared
(`DetANN.ContractsMeanZero`). -/
theorem lemma_7_2 {d Δ : ℕ} (nbr : Fin d → Fin Δ → Fin d) (hΔ : 1 ≤ Δ)
(hund : IsUndirected nbr) (θ₀ : ℝ) (hθ0 : 0 ≤ θ₀) (hθ1 : θ₀ < 1)
(hW : ContractsMeanZero (adjMatrix nbr) θ₀) (ℓ : ℕ) (hℓ : 1 ≤ ℓ)
(x : Fin d → EuclideanSpace ℝ (Fin d)) (xs : EuclideanSpace ℝ (Fin d)) :
betweenVar (walkEnd nbr ℓ) x xs ≤
(θ₀ ^ ℓ) ^ 2 / (1 - (θ₀ ^ ℓ) ^ 2) * withinVar (walkEnd nbr ℓ) x xs := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), Lemma 7.2, p.17 (PDF p.17)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.