arXiv：cs.LG· Tomer Zilca, Gal Mendelson·· 13 小时前
高维下两阶段结构化 Hadamard 旋转逼近均匀随机旋转的理论分析
Approximating Uniform Random Rotations by Two-Stage Structured Hadamard Rotations in High Dimensions
AI 导读
研究证明两阶段结构化 Hadamard 旋转在 Kolmogorov 与 Wasserstein-1 距离下对单位输入的逐坐标逼近误差上界为 √(log d/d)，随维度升高而收敛；但对输入 u=e₁，全向量分布的 Wasserstein-1 距离存在不随维度消失的显著偏差，且该下界紧致。结果表明一维边缘分布逼近随维度改善，而全向量律仍存在不可忽略的差距，与具体算法性能保证的联系尚待研究。
正文
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.
| Subjects: | Machine Learning (cs.LG); Performance (cs.PF) |
| Cite as: | arXiv:2604.23418 [cs.LG] |
| (or arXiv:2604.23418v2 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2604.23418 arXiv-issued DOI via DataCite |
Submission history
From: Gal Mendelson [view email]
[v1]
Sat, 25 Apr 2026 19:22:42 UTC (351 KB)
[v2]
Thu, 8 Oct 2026 18:42:44 UTC (141 KB)
来源：arXiv：cs.LG · arxiv.org