Theorem 3.2: the greedy choice of signs gives
ProvedDetANN.theorem_3_2_greedyapproximate-nearest-neighbordata-structuresderandomizationexpander-graphs
There is such that the following holds for every . Let , let be a matrix with entries and , let , and let be finite with , , and or for all distinct . Put and , and let be the greedy signs (definition DetANN_SignChoice) scored by the Lemma 6.2 expression. Then
and the blocks built from form a -balanced block system for .
The milestone balanced_signs_exist gives the existence of such signs. This theorem identifies the deterministic choice the algorithm makes: each sign takes the value that does not increase the conditional expectation of Lemma 6.2.
Preamble
import Mathlib import Definitions.Def_DetANN_SignedBlocks import Definitions.Def_DetANN_BalancedBlocks import Definitions.Def_DetANN_SignChoice
Formal statement
namespace DetANN
/-- **Theorem 3.2, the deterministic construction.** Expose the `Ld` signs in the order
`(ℓ, r) ↦ ℓ·d + r` and fix each to the value that does not increase the conditional expectation of
Lemma 6.2 (`lemma62Expr`). With `p₀ = ⌈log₄(8Nd)⌉` and `L = ⌈C₀τ⁻²p₀⌉` for `C₀` large enough, the
resulting signs have `Φ ≤ 1/8`, are balanced on every difference in `𝒟`, and give a `τ`-balanced
block system for `P`. -/
theorem theorem_3_2_greedy :
∃ C₀s : ℝ, 0 < C₀s ∧ ∀ C₀ : ℝ, C₀s ≤ C₀ → ∀ d : ℕ, 1 ≤ d →
∀ h : Matrix (Fin d) (Fin d) ℝ, (∀ j r, h j r = 1 ∨ h j r = -1) →
h.transpose * h = (d : ℝ) • (1 : Matrix (Fin d) (Fin d) ℝ) →
∀ τ : ℝ, 0 < τ → τ < 1 →
∀ P D : Finset (EuclideanSpace ℝ (Fin d)), (∀ v ∈ D, v ≠ 0) →
(∀ x ∈ P, ∀ y ∈ P, x ≠ y → x - y ∈ D ∨ y - x ∈ D) → 1 ≤ D.card →
potential h (numReps C₀ τ (momentOrder D.card d))
(greedySigns (lemma62Expr h (numReps C₀ τ (momentOrder D.card d)) τ
(momentOrder D.card d) D) (numReps C₀ τ (momentOrder D.card d) * d))
τ (momentOrder D.card d) D ≤ 1 / 8 ∧
(∀ v ∈ D, ∀ j : Fin d,
|(d : ℝ) * ‖signedBlocks h (numReps C₀ τ (momentOrder D.card d))
(greedySigns (lemma62Expr h (numReps C₀ τ (momentOrder D.card d)) τ
(momentOrder D.card d) D) (numReps C₀ τ (momentOrder D.card d) * d)) j v‖ ^ 2
- ‖v‖ ^ 2| < τ * ‖v‖ ^ 2) ∧
IsBalancedBlockSystem τ P (signedBlocks h (numReps C₀ τ (momentOrder D.card d))
(greedySigns (lemma62Expr h (numReps C₀ τ (momentOrder D.card d)) τ
(momentOrder D.card d) D) (numReps C₀ τ (momentOrder D.card d) * d))) := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), proof of Theorem 3.2, p.16