# Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions

arXiv: https://arxiv.org/abs/2604.23418 · HTML: https://mlsanity.com/paper/2604.23418/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 18 references that are in the map.
- First posted on arXiv 25 Apr 2026.

## Builds on (most cited first, 7 of 7)

- [TurboQuant: Online Vector Quantization with Near-optimal Distortion Rate](https://mlsanity.com/paper/2504.19874/) (2025)
- [Orthogonal Random Features](https://mlsanity.com/paper/1610.09072/) (2016)
- [Fastfood: Approximate Kernel Expansions in Loglinear Time](https://mlsanity.com/paper/1408.3060/) (2014)
- [EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning](https://mlsanity.com/paper/2108.08842/) (2021)
- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search](https://mlsanity.com/paper/2405.12497/) (2024)
- [The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings](https://mlsanity.com/paper/1703.00864/) (2017)

## Built on by (most cited first, 2 of 2)

- [Provable Quantization with Randomized Hadamard Transform](https://mlsanity.com/paper/2605.13810/) (2026)
- [TORQUE: Optimizing What (not) to Quantize Before and After Rotation](https://mlsanity.com/paper/2609.36032/) (2026)

## Abstract (arXiv)

Uniform random rotations are useful in fast Johnson--Lindenstrauss embeddings, kernel approximation, communication-efficient learning, and recent AI compression pipelines, but are computationally expensive to generate and apply in high dimensions. A practical alternative repeats Walsh--Hadamard transforms with random sign diagonals. Applying this structured rotation twice has shown empirical benefits, but supporting theory remains limited. We study the approximation quality of the two-stage structured Hadamard rotation. Here d is the dimension of the rotated vector. On the positive side, we prove explicit, nonasymptotic upper bounds of order √log d/d in both Kolmogorov and Wasserstein-1 distance for corresponding coordinates scaled by √ d, uniformly over unit inputs and coordinates. For the input u=e1, both distances also have lower bounds of order d-1/2 at every coordinate. On the negative side, we prove an explicit lower bound on the Wasserstein-1 distance between the full vector distributions, showing a substantial discrepancy that does not vanish as d grows for the input u=e1. For the same input, we also prove a matching asymptotic upper bound, showing that the lower-bound scale is sharp. Taken together, the results identify a separation between one-dimensional marginal behavior, where approximation improves with dimension, and the full-vector law, where a nonvanishing Wasserstein-1 discrepancy remains. The marginal bounds control coordinate threshold probabilities and expected scalar Lipschitz losses, including expected averages over coordinates. They do not establish joint-coordinate approximation, and the full-vector separation does not imply failure of a particular algorithm. Connecting these distributional results to performance guarantees for specific algorithms remains open.