§6.1, p.14 — Parseval for every sign assignment
ProvedDetANN.parseval_signed_blocksapproximate-nearest-neighbordata-structuresderandomizationexpander-graphsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be a real matrix with (for instance the unnormalized Walsh–Hadamard matrix), , , and let be arbitrary. The signed blocks satisfy, for every ,
So property (8) of a balanced block system holds whatever signs are chosen, and only (9) remains to be arranged.
Differences from the source:
- generalization: h the Walsh–Hadamard matrix (entries ±1, d a power of two) → any real d × d matrix h with hᵀh = d·I, any d; reason: the Walsh–Hadamard matrix satisfies hᵀh = d·I
- encoding: sign vectors in {−1, +1}^d → booleans mapped to ±1; reason: same assignments
Preamble
import Mathlib import Definitions.Def_DetANN_SignedBlocks
Formal statement
namespace DetANN
/-- **Parseval for every sign choice** (Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §6.1, p.14).
For every assignment of the signs, the signed Hadamard blocks satisfy
`∑_j ‖A_j z‖² = (1/L) ∑_ℓ ‖H diag(ξ^(ℓ)) z‖² = ‖z‖²` for every `z ∈ ℝ^d`, where `H = d^{−1/2} h`.
**Formalization Note.** `h` is any real `d × d` matrix with `hᵀh = d·I` (the paper: the unnormalized
Walsh–Hadamard matrix, `d` a power of two, entries `±1`; it satisfies `hᵀh = d·I`). `L ≥ 1` (for
`L = 0` the blocks map into `ℝ^0`). The middle term is written out coordinatewise, with
`(H diag(ξ^(ℓ)) z)_j = d^{−1/2} ∑_r h_{jr} ξ^(ℓ)_r z_r`. -/
theorem parseval_signed_blocks {d : ℕ} (h : Matrix (Fin d) (Fin d) ℝ)
(hh : h.transpose * h = (d : ℝ) • (1 : Matrix (Fin d) (Fin d) ℝ)) (L : ℕ) (hL : 1 ≤ L)
(ξ : Fin L → Fin d → Bool) (z : EuclideanSpace ℝ (Fin d)) :
∑ j, ‖signedBlocks h L ξ j z‖ ^ 2 =
(1 / (L : ℝ)) * ∑ ℓ : Fin L, ∑ j : Fin d,
((Real.sqrt d)⁻¹ * ∑ r : Fin d, h j r * signOf (ξ ℓ r) * z r) ^ 2 ∧
∑ j, ‖signedBlocks h L ξ j z‖ ^ 2 = ‖z‖ ^ 2 := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), §6.1, p.14 (PDF p.14)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.