用两块结构化哈达玛旋转近似高维均匀随机旋转,揭示其优劣边界。
Approximating Uniform Random Rotations by Two-Block Structured Hadamard Rotations in High Dimensions

- 采用两块哈达玛结构旋转,提升生成效率
- 单坐标逼近误差随维度下降至 d^{-1/5} 阶
- 整体分布仍有不可忽略偏差,不适用于所有场景
均匀随机旋转在快速 Johnson-Lindenstrauss 嵌入、核近似、通信高效学习及近期人工智能压缩流程中具有重要应用,但在高维下生成与应用成本高昂。常用替代方案是基于沃尔什-哈达玛变换和随机符号对角矩阵的重复结构化随机旋转。本文研究两次应用该结构化旋转的逼近效果。结果表明:对于任意固定坐标,其输出在所有输入下收敛于均匀旋转对应坐标的分布,且柯尔莫哥洛夫距离上界为 d^{-1/5}。然而,全向量分布的沃斯泰因距离存在明确下界,说明在最坏情况下,两块变换无法全局模拟均匀随机旋转。针对极值输入,我们还证明了匹配的渐近上界,表明该下界阶数紧致。结果揭示了一维边缘行为随维度改善,而高维整体几何仍存非消失偏差,部分解释了结构化哈达玛旋转在某些算法中的成功,也明确了其不能作为真实均匀随机旋转的直接替代品。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。