使用随机阿达玛变换进行量化：现已证明有效的启发式方法

均匀随机旋转 (URR) 是现代量化方法中常见的预处理步骤，用于梯度压缩、推理加速、KV 缓存压缩、模型权重量化和矢量数据库中的近似最近邻搜索。在实践中，URR 通常被随机 Hadamard 变换 (RHT) 取代，它在允许快速实现的同时保留正交性。剩下的问题是最坏情况输入的性能。对于 URR，每个坐标都单独分布为平移 beta 分布，该分布在高维中收敛为高斯分布。一般来说，一个 RHT 不适合最坏的情况，因为单个坐标可能远离这些分布。我们证明，在任何 $d$ 大小的输入向量上组合两个 RHT 后，归一化旋转向量的每个固定坐标的边缘分布在 Kolmogorov 距离和 $1$-Wasserstein 距离中都在标准高斯的 $O(d^{-1/2})$ 范围内。然后，我们将这些界限插入现代压缩方案（即 DRIVE 和 QUIC-FL）的分析中，并表明两个 RHT 实现了渐近匹配 URR 的性能。然而，我们表明两个 RHT 可能不足以进行矢量量化（VQ），矢量量化通常需要固定大小的坐标块之间的弱相关性（而不是单个坐标的边缘分布收敛）。我们证明三个 RHT 的组合会导致坐标协方差衰减。这确保了针对 URR 优化的任何固定、有界、多维 VQ 码本在使用三个 RHT 时具有相同的预期误差，直至随维度消失的加性项。最后，由于实际输入很少是对抗性的，因此我们提出对输入矩进行线性时间 ${O}(d)$ 检查，以动态调整运行时使用的 RHT 数量，以提高性能。