Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions
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 $\sqrt{\log d/d}$ in both Kolmogorov and Wass...
| Authors | Tomer Zilca, Gal Mendelson |
|---|---|
| Primary category | cs.LG |
| Published | 25 April 2026 |
| Last updated at source | 8 October 2026 |
Silytics shows public metadata from arXiv and links to the original. Information may be incomplete or out of date. Last refreshed 17 October 2026. Licenses and terms of the original apply to the work itself. Not financial, legal or professional advice.