The Sylvester–Hadamard matrix and its butterfly identity
ProvedDetANN.sylvester_hadamardapproximate-nearest-neighbordata-structuresderandomizationexpander-graphs
Let be the Sylvester–Hadamard matrix on , (definition DetANN_Sylvester). Then:
- every entry of is ;
- ;
- for with lower half and upper half ,
Items 1 and 2 are the hypotheses on the matrix in the block theorems of §6. The butterfly identity 3 evaluates with additions, the evaluation behind the query bound of Theorem 1.1.
Preamble
import Mathlib import Definitions.Def_DetANN_Sylvester
Formal statement
namespace DetANN
/-- **The Sylvester–Hadamard matrix** (§6.1). `H_k` has entries `±1`, satisfies `H_kᵀ H_k = 2^k I`,
and obeys the butterfly identity `H_{k+1}(z', z'') = (H_k(z' + z''), H_k(z' − z''))`, where `z'` and
`z''` are the lower and upper halves of `z ∈ ℝ^{2^{k+1}}`. -/
theorem sylvester_hadamard (k : ℕ) :
(∀ j r, sylvester k j r = 1 ∨ sylvester k j r = -1) ∧
(sylvester k).transpose * sylvester k =
((2 ^ k : ℕ) : ℝ) • (1 : Matrix (Fin (2 ^ k)) (Fin (2 ^ k)) ℝ) ∧
∀ (z : Fin (2 ^ (k + 1)) → ℝ) (i : Fin (2 ^ k)),
(sylvester (k + 1)).mulVec z (loIdx k i) =
(sylvester k).mulVec (fun r => z (loIdx k r) + z (hiIdx k r)) i ∧
(sylvester (k + 1)).mulVec z (hiIdx k i) =
(sylvester k).mulVec (fun r => z (loIdx k r) - z (hiIdx k r)) i := by sorry
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), §6.1, p.14 (the Walsh–Hadamard matrix and multiplication by H)