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

Abstract: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 Wasserstein-1 distance for corresponding coordinates scaled by $\sqrt d$, uniformly over unit inputs and coordinates. For the input $u=e_1$, 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=e_1$. 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.

Machine Learning (cs.LG); Performance (cs.PF)

arXiv:2604.23418 [cs.LG]

(or arXiv:2604.23418v2 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2604.23418 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.