Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions
For practitioners using structured rotations in applications like fast JL embeddings and AI compression, this provides a theoretical explanation of their empirical success while clarifying their limitations as drop-in replacements for true random rotations.
The paper studies the approximation quality of two-block structured Hadamard rotations as a surrogate for uniform random rotations in high dimensions. It proves that one-dimensional marginals converge uniformly with a Kolmogorov-distance bound of order d^{-1/5}, but the full vector distribution has a nonvanishing Wasserstein distance, showing a separation between marginal and global behavior.
Uniform random rotations are a useful primitive in applications such as fast Johnson-Lindenstrauss embeddings, kernel approximation, communication-efficient learning, and recent AI compression pipelines, but they are computationally expensive to generate and apply in high dimensions. A common practical replacement is repeated structured random rotations built from Walsh-Hadamard transforms and random sign diagonals. Applying the structured random rotation twice has been shown empirically to be useful, but the supporting theory is still limited. In this paper we study the approximation quality achieved when using this two-block structured Hadamard rotation. Our results are both positive and negative. On the positive side, we prove that every fixed coordinate of the two-block transform converges uniformly, over all inputs, to the corresponding coordinate of a uniformly rotated vector, with an explicit Kolmogorov-distance bound of order $d^{-1/5}$. On the negative side, we prove an explicit lower bound on the Wasserstein distance between the full vector distributions, showing that the two-block transform is not a globally accurate surrogate for a uniform random rotation in the worst case. For the extremal input used in the lower bound, we also prove a matching asymptotic upper bound, showing that the lower-bound scale is sharp for that input. Taken together, the results identify a clear separation between one-dimensional marginal behavior, where approximation improves with dimension, and full high-dimensional geometry, where a nonvanishing discrepancy remains. This provides a partial theoretical explanation for the empirical success of structured Hadamard rotations in some algorithms, while also clarifying the limitations of treating them as drop-in replacements for true uniform random rotations.