Structure of the Circular-Dyadic Convolution Error
For practitioners using Hadamard transforms for convolution, this provides a theoretical understanding of the substitution error, enabling error-aware algorithm design.
The paper characterizes the algebraic error when substituting the Hadamard transform for the FFT-computed DFT in circular-dyadic convolution, showing that the error is structured, predictable, and governed by alignment, with asymptotic doubling of output energy except for filters in a zero-error subspace.
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.