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

arXiv:2604.23418 · cs.LG, cs.PF · Submitted 2026-04-25 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions".

Tom: The gist The two-block structured Hadamard rotation provides a partial theoretical explanation for why structured random rotations are empirically successful in some algorithms,

Jane: First, who's behind it and why it matters.

Paper summary: Tom: So we’re wrapping up this look at "Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions." It really boils down to this split personality the authors found in these structured rotations <ref:2604.23418#pg3>.

Jane: They are good for one dimension, where the approximation quality actually gets better as the dimension increases, but they fail when you look at the whole vector distribution because there's this persistent gap in the Wasserstein distance <ref:2604.23418#pg3>.

Lu: The authors show this by proving that for every power of two dimension d greater than or equal to thirty-two thousand seven hundred sixty-eight the lower bound on that Wasserstein distance is strictly larger than zero point six <ref:2604.23418#pg3>.

Meng: It means if you're designing a system where the global spherical properties are important, you can't just use this cheap method without analyzing its actual output instead of assuming it mimics the uniform rotation <ref:2604.23418#pg1>.

Lalam: From an AI culture perspective, this suggests that when training models or building embeddings, if your success depends on global geometry, you should favor methods that respect that structure rather than just relying on fast coordinate approximations <ref:2604.23418#pg3>.

Tom: The title itself pretty much explains the whole thing: it’s about approximating uniform random rotations using two-stage structured Hadamard rotations in high dimensions <ref:2604.23418#pg1>.

Jane: So the implication is that these transforms are useful fast surrogates for uniform random rotations, but they must be used as task-dependent approximations, not as universal replacements for a true random rotation <ref:2604.23418#pg3>.

Lu: They found that for every single coordinate of the vector, the structured transform gets close to the real one-dimensional behavior with an error bound of order d minus one over five <ref:2604.23418#pg3>.

Meng: So, on paper, it’s good at individual components if you just look at them separately. But then they show that for the whole vector distribution, there’s a persistent gap in the Wasserstein distance <ref:2604.23418#pg3>.

Lalam: That gap means if your algorithm relies on how the whole vector is shaped on a sphere—like concentration or geometric regularity—this structured method isn't a perfect stand-in for the true uniform rotation, especially in higher dimensions <ref:2604.23418#pg3>.

Tom: So to wrap up, this paper shows that structured rotations are good fast guesses for individual parts of a vector but they don't perfectly capture the global geometry of high-dimensional space <ref:2604.23418#pg1>.

Jane: That's the core message: it’s useful because it’s cheap and fast, but you have to know what you’re approximating for your specific task.

Lu: It suggests that in AI, if you're doing stuff where coordinate statistics matter most, this is a solid tool. But for anything relying on global properties, you still need to be careful about that nonvanishing discrepancy <ref:2604.23418#pg3>.

Meng: From an engineering standpoint, it means we don't just throw this in as a drop-in replacement for a full random rotation without checking if our problem needs those global properties preserved <ref:2604.23418#pg3>.

Lalam: It helps us build better AI systems by giving us a clearer picture of when these structured methods are actually beneficial and when they aren't.

Tom: That’s the gist of it—it’s like having a really good pair of tools that excel at one job but aren't great at the whole toolbox.

Jane: And that means next time you use one, you better know exactly what kind of approximation you’re actually getting for your specific application.

Conclusion: Tom: So to close out, this paper is about taking those expensive uniform random rotations and trying to fake them using these two-stage structured Hadamard rotations in high dimensions <ref:2604.23418#pg1>.

Jane: It really boils down to the authors finding a big split in how well these structured transforms work. They found that they are pretty good at approximating individual parts of a vector, but they don't capture the whole geometric picture <ref:2604.23418#pg3>.

Lu: The two main things they prove are that for every single coordinate, the approximation gets better as the dimension grows, with an error bound tied to d minus one over five <ref:2604.23418#pg3>.

Meng: But for the full vector distribution, there’s a gap in that Wasserstein distance when comparing it to a true uniform rotation <ref:2604.23418#pg3>. They give an explicit lower bound on this difference <ref:2604.23418#pg3>.

Tom: That means the authors are saying these structured rotations aren't just perfect replacements for uniform ones, especially when you need global properties preserved <ref:2604.23418#pg1>.

Jane: Exactly. So the core message here is that these transforms are fast and cheap, which is a huge win for computation <ref:2604.23418#pg3>. But you have to be smart about what kind of approximation you're actually getting for your specific task <ref:2604.23418#pg3>.

Lu: This suggests that if your AI work focuses mostly on coordinate statistics, this structured method is a solid tool to use <ref:2604.23418#pg3>. But for anything relying on global properties, you still need to be careful about that nonvanishing discrepancy <ref:2604.23418#pg3>.

Meng: From an engineering standpoint, this means we don't just throw this in as a drop-in replacement for a full random rotation without checking if our problem needs those global properties preserved <ref:2604.23418#pg3>.

Lalam: This helps us build better AI systems by giving us a clearer picture of when these structured methods are actually beneficial and when they aren't <ref:2604.23418#pg3>.

Tom: So to wrap up, this paper is about taking those expensive uniform random rotations and trying to fake them using these two-stage structured Hadamard rotations in high dimensions <ref:2604.23418#pg1>.

Tom: That means the authors are saying these structured rotations aren't just perfect replacements for uniform ones, especially when you need global properties preserved <ref:2604.23418#pg1>.

Lalam: This helps us build better AI systems by giving us a clearer picture of when these structured methods are actually beneficial and when they aren't <ref:2604.23418#pg3>.

Tomer Zilca, Gal Mendelson

Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology · Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University

cs.LG, cs.PF

Submitted: 2026-04-25

Updated: 2026-10-08

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 81/100

The gist: The gist The two-block structured Hadamard rotation provides a partial theoretical explanation for why structured random rotations are empirically successful in some algorithms, while simultaneously

Key concepts

Uniform Random Rotation (Ru): This is the ideal transformation where a vector is spread perfectly and randomly across the entire surface of a sphere. It is used in many algorithms like Johnson–Lindenstrauss embeddings because it guarantees maximum randomness for high-dimensional data.
Two-Block Structured Hadamard Transform (T(u)): This is a practical, computationally cheap approximation method built using Walsh–Hadamard transforms and random sign matrices. It is used instead of true uniform rotations because it avoids the computational expense of dense matrices while offering some structural benefits.
Kolmogorov Distance: This metric measures how close two probability distributions are. The paper uses it to show that for individual coordinates, the structured transform's distribution is very close to the uniform one, with a bound related to dimension d.
Wasserstein Distance (W1): This distance measures the 'cost' or difference between two probability distributions. The paper finds that this distance remains significantly larger than zero for the full vector distribution, indicating a persistent global inaccuracy compared to the uniform rotation.

Terminology

Embeddings — 1× in this paper · explained in 2 episodes
Wasserstein Distance — 1× in this paper · explained in 5 episodes

Summary

The gist The two-block structured Hadamard rotation provides a partial theoretical explanation for why structured random rotations are empirically successful in some algorithms, while simultaneously clarifying their limitations as drop-in replacements for true uniform random rotations.

Approximation Quality and Metrics

The paper investigates the approximation quality of the two-block structured transform T(u) = 1/d HD(1)HD(2)u compared to a uniformly rotated vector Ru. For one-dimensional marginals, the positive result proves that for every coordinate, the marginal distribution under the two-block structured rotation converges to the corresponding marginal under the uniform rotation, with an explicit Kolmogorov-distance bound of order d − 1/5 The negative result shows that for the full vector distribution, there is a nonvanishing discrepancy in Wasserstein distance; specifically, for every power-of-two dimension d ≥ 32768, the lower bound is shown to be strictly larger than 0.6.

One-Dimensional Marginal Behavior

The positive result establishes that each coordinate of the structured rotation approaches the corresponding coordinate of the uniform rotation uniformly over the input vector. This convergence is quantified by Theorem 4.1, which states that for every dimension d that is a power of two, sup u∈Sd−1 sup 1≤k≤d K([T(u)]k, [X(u)]k) ≤ Cpos d − 1/5. This result is significant because it demonstrates that the structured transform reproduces the correct one-dimensional marginal behavior.

Global Distribution Discrepancy

Conversely, for the full vector distribution, the picture is fundamentally different, and a persistent lower bound on the Wasserstein distance shows that the two-block transform is not a globally accurate surrogate for a uniform rotation in the worst case. Theorem 5.2 provides explicit nonvanishing bounds such as sup u∈Sd−1 W1(T(u), X(u)) > 0.6 for every power-of-two d ≥ 32768. Furthermore, the limit inferior of this discrepancy as d approaches infinity is bounded below by at least a constant of about 0.6358.

Sharpness and Separability

The paper sharpens the negative result for the extremal input u = e1, proving a matching asymptotic upper bound on the full Wasserstein distance, showing that the lower-bound scale is sharp for that input. This separation between marginal and joint distributional behavior suggests that when an algorithm depends mainly on coordinate-wise statistics, approximation improves with dimension, but when it relies on global spherical properties, a nonvanishing discrepancy remains

Implications for Algorithms

The results suggest two distinct interpretations for applying structured Hadamard rotations in preprocessing steps. First, if an algorithm applies a rotation and then processes coordinates separately through scalar nonlinearities, the positive result justifies the use of structured Hadamard rotations because accurate marginal approximation is relevant. Second, if a guarantee relies on global properties like concentration or geometric regularity on the sphere, the negative result warns that one must analyze the structured transform directly rather than appealing to uniform-rotation intuition. The main takeaway is that structured Hadamard rotations are well motivated as fast surrogates for uniform random rotations but should be viewed as task-dependent approximations.

Numerical Illustrations

The theory is complemented by numerical illustrations visualizing these two phenomena Figure 1 examines the empirical one-coordinate Kolmogorov distance versus dimension, showing a clear decrease with dimension, while the confidence intervals are visually negligible. Figure 2 visualizes the lower-bound phenomenon from theorem 5.1, illustrating persistent global discrepancy across dimensions and parameter values.

Auxiliary Lemmas

The proof relies on several auxiliary lemmas to bridge the gap between structured transforms and uniform rotations, including Lemma 3.1 regarding first and second moments, Lemma 4.3 defining the structure of T(u) as a sum of independent Rademacher variables, and Lemma 5.7 establishing the Lipschitz property for distance to a fixed set. The proof of theorem 5.8 shows that for u = e1, the upper bound matches the lower bound asymptotically, indicating sharpness for that specific input. The paper concludes by showing that W1(X(e1), T(e1)) ≤ s squared − 2√d EX1 which yields the final asymptotic bound.

The paper is a scientific study on approximating uniform random rotations using two-stage structured Hadamard rotations in high dimensions, and it matters because it provides a theoretical separation between the success of these transforms for one-dimensional marginals and their failure to approximate the full high-dimensional spherical law.

--- Page 1 ---

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

Tomer Zilca∗ Gal Mendelson†

April 28, 2026

Abstract

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. Keywords. structured random rotation, Hadamard transform, random orthogonal transform, Kolmogorov distance, Wasserstein distance, randomized algorithms

1 Introduction

Uniform random rotations are a natural tool when one wishes to spread a deterministic vector evenly across directions. If u ∈ R d and R is sampled from the Haar distribution on the orthogonal group, then Ru is uniformly distributed on the sphere of radius ∥u∥2. This symmetry is useful in a range of applications, including randomized numerical linear algebra, dimension reduction, derivative-free optimization, random feature generation, and communication-efficient learning [1].

∗Faculty of Data and Decision Sciences, Technion – Israel Institute of Technology, Haifa, Israel (tomerzilca@campus.technion.ac.il)

†Edward P. Fitts Department of Industrial and Systems Engineering, North Carolina State University, Raleigh, NC, USA (gmendel@ncsu.edu)

1 arXiv:2604.23418v1 [cs.LG] 25 Apr 2026

--- Page 2 ---

The difficulty is computational. Generating and storing a dense random orthogonal matrix is expensive, and multiplying it by a vector costs O(d2) operations. In large-scale settings, this is often prohibitive. A practical alternative is to use structured random rotations, built from cheap orthogonal transforms and a small amount of randomness. A particularly common construction uses Walsh–Hadamard matrices and diagonal random sign matrices. These transforms can be applied in O(d log d) time via the Fast Walsh–Hadamard Transform and require only O(d) random bits [7, 1, 10].

A first question is whether a single-block Hadamard-sign transform can already approximate a uniform random rotation. For an input vector u, this is given by √1/d HDu, where d is the dimension, H is a deterministic Hadamard matrix, and D is a diagonal matrix with i.i.d. Radamacher random variables on the diagonal. As shown in [16], the answer is no. If u = ei is a basis vector, then √1/d HDu is supported on only two antipodal points, namely the ± version of the ith column of H scaled by 1/√d. A uniformly rotated basis vector, by contrast, is distributed over the entire sphere. Thus a one-block transform cannot approximate a uniform rotation globally. This obstruction is consistent with the use of two-block Hadamard rotations in practice, for example in DRIVE and EDEN [16, 15], where one additional randomized mixing layer is introduced precisely to avoid such degenerate behavior on sparse inputs.

Improvements for AI systems

Improved coordinate-wise quantization systems can leverage structured Hadamard rotations by applying them before coordinate-wise nonlinearities such as scalar quantization, clipping, thresholding because for every dimension d that is a power of two, sup u∈Sd−1 sup 1≤k≤d K([T(u)]k, [Ru]k) ≤ Cpos d −1/5.
Enhanced vector compression pipelines can utilize the two-block structured Hadamard transform to spread information more evenly across coordinates before quantization, as this is useful in applications such as fast Johnson–Lindenstrauss embeddings, kernel approximation, communication-efficient learning, and recent AI compression pipelines.
Distributed mean estimation algorithms can benefit from using structured Hadamard rotations to improve estimator behavior while remaining computationally efficient, as structured orthogonal constructions can improve estimator behavior while remaining computationally efficient in Monte Carlo settings.

Sources

The Unreasonable Effectiveness of Structured Random Orthogonal Embeddings