§7.4: correctness of the Theorem 1.1 data structure
ProvedDetANN.theorem_1_1_correctnessapproximate-nearest-neighbordata-structuresderandomizationexpander-graphs
There is such that the following holds for every . Let with , let be distinct and . Build the blocks and walk tuples of the definition DetANN_Construction for the zero-padded points in . Let , and for each tuple let be one of the points such that the padded points satisfy the local guarantee (25) with . Then
This is the correctness part of the proof of Theorem 1.1: if every local structure returns a -approximate neighbor in its projected space, the best returned point is a -approximate nearest neighbor.
Formalization Note. The statement holds for every power of two , including ; the assumption of Theorem 1.1 matters only for the resource bounds. The minimum over is expressed as the existence of with for every .
Preamble
import Mathlib import Definitions.Def_DetANN_Construction import Definitions.Def_DetANN_TupleFamily
Formal statement
namespace DetANN
/-- **§7.4, correctness of the Theorem 1.1 data structure.** Pad `P` with zeros to `ℝ^{2^k}`
(`d ≤ 2^k`), build the blocks of the greedy Theorem 3.2 construction (Sylvester matrix,
`τ = ε²/10⁶`) and the walk tuples of the Lemma 7.1 graph on `Fin (2^k)` with walk length
`⌈log_{1/θ₀}(200/ε)⌉`. If the points `x_v` satisfy the local guarantee with `α = 1 + ε/100`, then
one of them is a `(1 + ε)`-approximate nearest neighbor of `q`. -/
theorem theorem_1_1_correctness :
∃ C₀s : ℝ, 0 < C₀s ∧ ∀ C₀ : ℝ, C₀s ≤ C₀ → ∀ (d n k : ℕ), d ≤ 2 ^ k →
∀ P : Fin n → EuclideanSpace ℝ (Fin d), Function.Injective P →
∀ ε : ℝ, 0 < ε → ε < 1 →
∀ (q : EuclideanSpace ℝ (Fin d)) (x : Fin (2 ^ k) → Fin n),
LocalGuarantee (annBlocks C₀ k P ε) (annTuples k ε) (paddedSet k P)
(padVec (2 ^ k) q) (fun v => padVec (2 ^ k) (P (x v))) (1 + ε / 100) →
∃ v, ∀ i, ‖q - P (x v)‖ ≤ (1 + ε) * ‖q - P i‖ := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), §7.4, proof of Theorem 1.1, p.19