This paper explores the error characteristics of dyadic and circular convolution, highlighting the efficiency advantage of the Hadamard transform. Both can be computed in $O(N\log N)$ time, but the Hadamard transform is preferable due to its real-valued sign flips. However, the algebraic error introduced by substituting the DFT is significant.
The authors present three complementary results to characterize this error:
- Exact Error Cancellation: At two input and output positions, the error is universally absent, and no reordering of the output can eliminate this error.
- Rank of the Error Operator: The error operator is nearly full rank, while its null space has only logarithmic dimension.
- Expected Error Control: The expected error is governed by a single alignment scalar, with a closed-form expression obtained by averaging over random filters.
Overall, the substitution error asymptotically doubles the output energy, except for filters in the universal zero-error subspace, which incur no error. Collectively, these results indicate that the substitution error is structured, predictable, and governed by alignment.
Blogger's Review: This paper provides a rigorous mathematical analysis of the error characteristics arising from the substitution of Hadamard transform for DFT, emphasizing the importance of choosing the right convolution method, especially in high-performance applications.