Researchers Characterize Error in Hadamard Transform for Convolution

This research delves into the algebraic error that arises when the Hadamard transform is used as a substitute for the Discrete Fourier Transform (DFT) in computing circular convolution. While the Hadamard transform is often preferred for its real-valued sign flips and computational efficiency, this substitution introduces a quantifiable error. The paper presents three key findings that characterize this error. Firstly, it identifies specific input and output positions where the error universally cancels out, meaning these positions are always error-free. Secondly, the error operator is shown to be nearly full rank, indicating a broad impact, with its null space having only logarithmic dimension. Lastly, the expected error is found to be governed by a single alignment scalar, for which a closed-form expression is derived by averaging over random filters. The findings collectively reveal that this substitution error is structured, predictable, and can asymptotically double the output energy, except for specific filters that reside in the universal zero-error subspace.