循环二进卷积误差的结构

arXiv:2607.15293v1 公告类型：新 摘要：使用 Hadamard 变换和 FFT 计算的离散傅里叶变换 (DFT) 分别可以在 $O(N\log N)$ 时间内计算二进卷积和循环卷积。 Hadamard 变换因其实值符号翻转而更受欢迎，但它对 DFT 的替代会引入代数误差。我们提出了三个互补的结果来表征该错误。首先，我们确定精确的误差消除：两个输入和两个输出位置通常是无误差的，并且输出的重新排序不能消除该误差。其次，误差算子几乎是满秩的，而其零空间只有对数维数。第三，预期误差由单个对齐标量控制，并通过对随机滤波器进行平均而获得封闭形式的表达式。一般来说，替代误差渐近地使输出能量加倍，但通用零误差子空间中的滤波器除外，它不会产生误差。总的来说，这些结果表明替代错误是结构化的、可预测的，并且由比对控制。