分析哈达玛变换替代傅里叶变换的误差结构，发现其可预测且与滤波器对齐相关。
Structure of the Circular-Dyadic Convolution Error
- 通过哈达玛变换替代傅里叶变换引入代数误差，但存在固定无误差位置。
- 误差算子几乎满秩，仅在对数维零空间内为零，整体误差能量约翻倍。
- 误差由滤波器与变换的对齐性决定，随机平均下有闭式表达式。
dyadic 和 circular 卷积均可通过哈达玛变换或 FFT 计算的离散傅里叶变换（DFT）在 $O(N\log N)$ 时间内完成。哈达玛变换因其仅涉及实数符号翻转更优，但用其替代 DFT 会引入代数误差。本文给出三项互补结果：第一，识别出精确误差抵消——两个输入和两个输出位置始终无误差，且无法通过重排输出消除；第二，误差算子几乎满秩，其零空间维度仅为对数级；第三，期望误差由单一对齐标量决定，通过对随机滤波器取平均得到闭式表达。一般情况下，替换误差使输出能量在渐近意义上翻倍，除非滤波器位于普遍零误差子空间，此时无误差。这些结果表明，替换误差具有结构性、可预测性且受对齐性支配。
原文摘要 · Abstract (English)
Dyadic and circular convolution can both be computed in $O(N\log N)$ time using the Hadamard transform and the FFT-computed discrete Fourier transform (DFT), respectively. The Hadamard transform is preferable for its real-valued sign flips, yet its substitution for the DFT introduces algebraic error. We present three complementary results that characterize this error. First, we identify exact error cancellation: two input and two output positions are universally error-free, and no reordering of the output can eliminate this error. Second, the error operator is nearly full rank, while its null space has only logarithmic dimension. Third, the expected error is governed by a single alignment scalar, with a closed-form expression obtained by averaging over random filters. In general, the substitution error asymptotically doubles the output energy, except for filters in the universal zero-error subspace, which incur no error. Collectively, these results show that the substitution error is structured, predictable, and governed by alignment.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。