The Sylvester–Hadamard matrix (§6.1)
DefinitionDetANN_Sylvesterapproximate-nearest-neighbordata-structuresderandomizationexpander-graphs
For , let be the number of bit positions at which both and have a . The Sylvester–Hadamard matrix on is
Index of the lower half of is , and of the upper half is .
This is the unnormalized Walsh–Hadamard matrix used to build the signed blocks of §6.1, in the dimension .
Definition code
import Mathlib
namespace DetANN
/-!
# The Sylvester–Hadamard matrix (§6.1)
Y. Feng, P. Indyk, *Deterministic Approximate Nearest Neighbors in High Dimensions*, STOC 2027
submission (manuscript sha256 96f0ad57…), §6.1, p.14: the (unnormalized) Walsh–Hadamard matrix on
`d = 2^k` coordinates, used to build the signed blocks.
-/
/-- The bitwise inner product `⟨j, r⟩ = #{b < k : bit b of j and bit b of r are both 1}`. -/
def bitDot (k j r : ℕ) : ℕ := ((Finset.range k).filter fun b => j.testBit b && r.testBit b).card
/-- The Sylvester–Hadamard matrix on `Fin (2^k)`: `(H_k)_{jr} = (−1)^{⟨j, r⟩}`. -/
def sylvester (k : ℕ) : Matrix (Fin (2 ^ k)) (Fin (2 ^ k)) ℝ := fun j r => (-1) ^ bitDot k j r
/-- Index `i` of the lower half of `Fin (2^(k+1))`. -/
def loIdx (k : ℕ) (i : Fin (2 ^ k)) : Fin (2 ^ (k + 1)) := ⟨i, by rw [pow_succ]; omega⟩
/-- Index `2^k + i` of the upper half of `Fin (2^(k+1))`. -/
def hiIdx (k : ℕ) (i : Fin (2 ^ k)) : Fin (2 ^ (k + 1)) := ⟨2 ^ k + i, by rw [pow_succ]; omega⟩
end DetANN
Source
Feng, Indyk, Deterministic Approximate Nearest Neighbors in High Dimensions, STOC 2027 submission (manuscript sha256 96f0ad57b9d12ba3ac6f9e61c88ddfd6b621e077d7e2a9821906e5b4ff0d0e82), §6.1, p.14