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 √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.