⚡
Walsh-Hadamard Transform
O(d log d) butterfly-style rotation with O(d) storage — the fast alternative to QR decomposition for random rotations.
Definition
The Walsh-Hadamard matrix of order is defined recursively:
The normalized Hadamard matrix is orthogonal: .
Butterfly Diagram
Analogous to FFT, the FWHT computes in time without materializing the full matrix. The butterfly pattern shows how elements combine at each stage:
8-point Fast Walsh-Hadamard Transform butterfly pattern (3 stages, O(n log n) operations)
Randomized Hadamard Rotation
A plain Hadamard matrix is deterministic. To get a random rotation, TurboQuant uses:
Forward rotation
Inverse rotation
QR vs Hadamard Comparison
| Property | QR (Haar) | Hadamard |
|---|---|---|
| Storage | O(d²) — full matrix | O(d) — just sign vector |
| Compute | O(d²) — matrix multiply | O(d log d) — FWHT |
| Randomness | Exact Haar distribution | Approximate (excellent) |
| Constraint | None | d must be power of 2 |
Benchmark: Identical Quality
On Qwen3.5-0.8B, Hadamard rotation matches QR quality exactly: PPL 14.30 vs 14.28 (4+4 residual), KLD 0.0020 for both. Use --rotation hadamard to enable.
Implementation
rotation.py → hadamard_rotate(), hadamard_rotate_inverse(), _fwht()