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

• URL: http://arxiv.org/abs/2604.23418v1
• Date: Sat, 25 Apr 2026 19:22:42 GMT
• Title: Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions
• Abstract summary: 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.<n>A common practical replacement is repeated structured random rotations built from Walsh-Hadamard transforms and random signs.<n>Applying the structured random rotation twice has been shown empirically to be useful, but the supporting theory is still limited.
• Score: 0.8307668828380427
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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. 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.

Related papers

• A Note on Scaling in Randomly Rotated Quantization and Its Connection to the CDEF +1 Pythagorean Relation [3.841157091833951]
  We point out the connection to classical results in statistical signal processing and communication theory.<n>The two reconstruction scales used in the EDEN line of work admit a natural interpretation as finite-dimensional, realization-dependent counterparts of the Wiener and unbiased coefficients.
  arXiv  Detail & Related papers  (2026-09-08T13:55:15Z)
• Restricted Dynamic Geometric Complexity: Path-Space Reduction and Möbius--Jacobi Response [0.0]
  We study restricted dynamic geometric complexity as a path-space value problem.<n>The main response result is global on a Hadamard state space.
  arXiv  Detail & Related papers  (2026-07-08T09:36:45Z)
• Quantizing With Randomized Hadamard Transforms: Efficient Heuristic Now Proven [16.408056537803308]
  Uniform random rotations (URRs) are a common preprocessing step in modern quantization approaches.<n>In practice, URRs are often replaced by randomized Hadamard transforms (RHTs)<n>We show that two RHTs achieve performance thatally matches URRs, but two RHTs may not be sufficient for Vector Quantization (VQ)<n>We propose a linear-time $O(d)$ check on the input's moments to dynamically adapt the number of RHTs used at runtime to improve performance.
  arXiv  Detail & Related papers  (2026-05-07T11:11:54Z)
• Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral [17.319855487817257]
  We show that the maximum expected inner product between a random vector and the standard normal vector is equivalent to a truncated integral involving the rate-distortion function.<n>The proof is based on a lifting technique, which constructs a Gaussian process indexed by a random subset of the type class of the probability distribution involved in the information-theoretic inequality.
  arXiv  Detail & Related papers  (2026-04-15T16:37:00Z)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Relative Wasserstein Angle and the Problem of the $W_2$-Nearest Gaussian Distribution [4.042425236692822]
  We study the problem of quantifying how far an empirical distribution deviates from Gaussianity under the framework of optimal transport.<n>By exploiting the cone geometry of the relative translation invariant quadratic Wasserstein space, we introduce two novel geometric quantities.<n>We prove that the filling cone generated by any two rays in this space is flat, ensuring angles, projections, and inner products are rigorously well-defined.
  arXiv  Detail & Related papers  (2026-01-29T22:03:10Z)
• Revisiting Zeroth-Order Optimization: Minimum-Variance Two-Point Estimators and Directionally Aligned Perturbations [57.179679246370114]
  We identify the distribution of random perturbations that minimizes the estimator's variance as the perturbation stepsize tends to zero.<n>Our findings reveal that such desired perturbations can align directionally with the true gradient, instead of maintaining a fixed length.
  arXiv  Detail & Related papers  (2025-10-22T19:06:39Z)
• Variance-Reducing Couplings for Random Features [57.73648780299374]
  Random features (RFs) are a popular technique to scale up kernel methods in machine learning. We find couplings to improve RFs defined on both Euclidean and discrete input spaces. We reach surprising conclusions about the benefits and limitations of variance reduction as a paradigm.
  arXiv  Detail & Related papers  (2024-05-26T12:25:09Z)
• Randomized Coordinate Subgradient Method for Nonsmooth Composite Optimization [11.017632675093628]
  Coordinate-type subgradient methods for addressing nonsmooth problems are relatively underexplored due to the set of properties of the Lipschitz-type assumption.
  arXiv  Detail & Related papers  (2022-06-30T02:17:11Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Fused-Lasso Regularized Cholesky Factors of Large Nonstationary Covariance Matrices of Longitudinal Data [0.0]
  smoothness of the subdiagonals of the Cholesky factor of large covariance matrices is closely related to the degrees of nonstationarity of autoregressive models for time series and longitudinal data. We propose an algorithm for sparse estimation of the Cholesky factor which decouple row-wise.
  arXiv  Detail & Related papers  (2020-07-22T02:38:16Z)
• Debiased Sinkhorn barycenters [110.79706180350507]
  Entropy regularization in optimal transport (OT) has been the driver of many recent interests for Wasserstein metrics and barycenters in machine learning. We show how this bias is tightly linked to the reference measure that defines the entropy regularizer. We propose debiased Wasserstein barycenters that preserve the best of both worlds: fast Sinkhorn-like iterations without entropy smoothing.
  arXiv  Detail & Related papers  (2020-06-03T23:06:02Z)
• Explicit Regularization of Stochastic Gradient Methods through Duality [9.131027490864938]
  We propose randomized Dykstra-style algorithms based on randomized dual coordinate ascent. For accelerated coordinate descent, we obtain a new algorithm that has better convergence properties than existing gradient methods in the interpolating regime.
  arXiv  Detail & Related papers  (2020-03-30T20:44:56Z)
• Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform [64.90148466525754]
  We study the performance of iterative sketching for least-squares problems. We show that the convergence rate for Haar and randomized Hadamard matrices are identical, andally improve upon random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
  arXiv  Detail & Related papers  (2020-02-03T16:17:50Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.