🤖 machine learning

Structure of the Circular-Dyadic Convolution Error

This paper characterizes the structured and predictable algebraic error introduced when substituting the Hadamard transform for the DFT in circular convolution, revealing that the error is governed by alignment, nearly full-rank with a logarithmic null space, and asymptotically doubles output energy except in specific universal zero-error subspaces.

Original authors: Ben Fauber, Alireza Moradzadeh

Published 2026-07-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Ben Fauber, Alireza Moradzadeh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to send a secret message across a crowded room. To do this efficiently, you need a special code that scrambles your words so they can be sent quickly and unscrambled by the receiver. In the world of computer science, specifically in how machines learn to recognize patterns, there are two famous "code-makers" used for this job. One is the Fourier Transform, a mathematical wizard that works by spinning numbers in a circle (like a clock) to mix them up. The other is the Hadamard Transform, a simpler, faster wizard that only uses plus and minus signs, flipping bits like switches on and off.

For years, engineers have been tempted to swap the complex, spinning Fourier wizard for the simpler, flipping Hadamard wizard. Why? Because the Hadamard version is easier for computers to handle and doesn't need to deal with complicated imaginary numbers. It's like trying to replace a high-end, color-printing 3D printer with a fast, black-and-white dot-matrix printer because the dot-matrix one is cheaper and faster. The big question is: Does the picture still look right? If you use the wrong printer, does the image just get a little blurry, or does it turn into a completely different picture? This paper dives deep into that exact question, treating the "error" not as a random glitch, but as a structured, predictable pattern that follows its own strict rules.

The Great Swap: When "Fast" Isn't "Right"

In the world of deep learning (the technology behind AI that recognizes cats in photos or translates languages), computers often need to perform a task called convolution. Think of this as sliding a filter (like a stencil) over an image to highlight specific features. To do this super fast, computers usually use the Fourier method, which relies on a circular logic: if you go past the end of the list, you wrap around to the beginning, like a clock hand hitting 12 and jumping back to 1.

However, some researchers proposed using the Hadamard method instead. This method uses a different kind of logic called "XOR" (exclusive OR), which is more like a game of "switching bits" rather than wrapping around a circle. The hope was that you could just swap the Fourier method for the Hadamard method without changing anything else in the code. This paper, by Ben Fauber and Alireza Moradzadeh from NVIDIA, investigates what happens when you make that swap.

The Discovery: It's Not Just Random Noise

The authors found that swapping these two methods doesn't just create a little bit of static noise. Instead, it creates a very specific, structured error. Here is what they discovered, broken down into three main findings:

1. The Two "Safe Zones"
The most surprising finding is that the error isn't everywhere. There are exactly two spots in the output where the two methods agree perfectly, no matter what data you put in. If you look at the very last position and the middle position of the result, the "circular" math and the "bit-flipping" math give you the exact same answer.

The Catch: You cannot fix the rest of the mess by simply shuffling the order of the results. The authors proved that no matter how you rearrange the output, you can never make the two methods match for every single input. The mismatch is baked into the math itself.

2. The "Almost Full" Error Machine
The paper looks at the "error operator," which is a fancy way of describing the machine that turns the correct answer into the wrong one. They found that this machine is "nearly full rank." In plain English, this means the error affects almost every single piece of data you throw at it.

The Tiny Exception: The only data that doesn't get messed up is a very tiny, specific group of inputs. The size of this "safe group" is incredibly small compared to the total amount of data. For a signal length of 1,024, the safe group is only 11 dimensions wide (about 1% of the total). As the data gets bigger, this safe zone shrinks even further, becoming almost invisible. This means that for almost all real-world filters, the swap creates a significant error.

3. The Energy Explosion
Perhaps the most dramatic finding is about the "energy" of the error. When you use a random filter (a typical, untrained filter), the error doesn't just add a little noise; it actually doubles the energy of the output.

Imagine you are trying to measure the volume of a song. If you use the wrong math, the volume doesn't just get a little louder; it suddenly becomes twice as loud as it should be, but the "sound" is completely distorted. The paper shows that as the data gets larger, the error energy approaches exactly twice the energy of the intended output. This happens because the two methods become so different that they stop canceling each other out and instead pile up their mistakes.

The "Alignment" Secret

The paper also introduces a concept called an "alignment scalar." Think of this as a score that tells you how well your filter fits the Hadamard method.

If your filter is one of those rare, special ones that lives in the tiny "safe zone," the score is perfect, and there is zero error.
If your filter is a standard, random one, the score is low, and the error is huge.
The authors derived a formula that predicts exactly how much error you will get based on this alignment score. They found that for generic, random filters, the error is unavoidable and substantial.

Why This Matters

The paper effectively puts a stop to the idea that the Hadamard transform can be a simple "drop-in" replacement for the Fourier transform in neural networks. While the Hadamard method is faster and simpler, the authors prove that it computes a fundamentally different operation.

It's not a bug; it's a feature of the math: The error isn't random; it's structured.
It's not fixable by shuffling: You can't just reorder the data to make it work.
It's usually bad news: Unless you specifically design your filter to live in that tiny "zero-error" zone (which is very hard to do by accident), the swap will likely double the energy of your output and distort your results.

In short, if you are building a system that relies on circular convolution (like many current AI models), swapping in the Hadamard transform without understanding these strict rules is like swapping a precision Swiss watch for a digital stopwatch because the stopwatch is cheaper. It might tell time, but it won't tell the right time, and the difference isn't just a few seconds—it's a completely different way of measuring time. The paper provides the blueprint for exactly how wrong that measurement will be, showing that the error is predictable, massive, and governed by how well your data aligns with the new math.

Technical Summary: Structure of the Circular–Dyadic Convolution Error

Problem Statement
The paper addresses the algebraic mismatch that arises when substituting the Hadamard transform for the Discrete Fourier Transform (DFT) in convolution operations. While both transforms enable $O(N \log N)$ computation, they diagonalize fundamentally different group convolutions: the DFT diagonalizes circular convolution over the cyclic group $\mathbb{Z}_N$ (using modular indexing), whereas the Hadamard transform diagonalizes dyadic convolution over the binary group $(\mathbb{Z}_2)^m$ (using XOR indexing). Although recent deep learning architectures have proposed Hadamard layers as "drop-in" replacements for DFT-based convolutions, the specific signal conditions under which this substitution introduces error, the structural properties of the resulting error operator, and the magnitude of that error have not been formally characterized. The authors note that while finite-group Fourier theory establishes these groups are non-isomorphic for $m \ge 2$ , the rank structure and expected error behavior of the difference operator remain unexplored.

Methodology
The authors analyze the error signal $e = y_C - y_D$ , where $y_C$ is the circular convolution and $y_D$ is the dyadic convolution of a filter $u$ and input $v$ . They define the error as a linear transformation $e = (C_u - H_u)v$ , where $C_u$ and $H_u$ are the circulant and dyadic convolution matrices, respectively. The analysis proceeds through three complementary lenses:

Exact Cancellation: Identifying specific input/output indices where the modular and XOR indexing coincide for all signals.
Operator Structure: Analyzing the rank and null space of the error matrix $(C_u - H_u)$ by studying the orbit structure of the "mismatch permutations" $\rho_n$ generated by the group action.
Statistical Expectation: Deriving a closed-form expression for the expected squared error magnitude by averaging over random filters and inputs, governed by an "alignment scalar" $Q(u)$ that measures the index agreement between the two convolution types.

Key Contributions and Results

Universal Zero-Error Conditions:
The paper proves that for any $N=2^m$ ( $m \ge 2$ ), there are exactly two output positions ( $n = N-1$ and $n = N/2 - 1$ ) and two input positions ( $k = 0$ and $k = N/2$ ) where the error vanishes universally for all signals. Crucially, the authors demonstrate that no reordering (permutation) of the output can extend this agreement to all inputs; the two convolutions are algebraically distinct and cannot be reconciled by simple index shifting.
Null-Space and Rank Structure:
The error operator $(C_u - H_u)$ is shown to be nearly full rank. Specifically, for generic filters, the rank is $N - m - 1$ , leaving a null space (the "universal zero-error subspace") of dimension $m + 1$ . This null space is logarithmic in size relative to $N$ (dimension $\approx \log_2 N + 1$ ). The basis vectors of this subspace are the standard basis vector $b_0$ and vectors $f_p$ defined by the least significant bit (LSB) positions of the indices. Consequently, the zero-error subspace occupies a vanishingly small fraction of the total space as $N$ increases (e.g., 1.1% at $N=1024$ ).
Expected Error Magnitude and Alignment:
The expected squared error for random, independent, zero-mean signals is governed by a single alignment scalar $Q(u) = \sum_{n,k} u[(n-k) \mod N] u[n \oplus k]$ .
- For generic filters, the expected error energy asymptotically doubles the output energy of the intended circular convolution as $N \to \infty$ .
- The ratio of expected error energy to output energy approaches 2, driven by the decorrelation between the two convolution types.
- Filters lying in the universal zero-error subspace achieve maximum alignment ( $Q(u) = N\|u\|^2_2$ ) and incur zero error.
- For generic i.i.d. filters, the normalized alignment decays to zero as $N$ increases, placing them far from the zero-error regime.

Significance and Claims
The paper claims that the substitution error is not random noise but is structured, predictable, and governed by alignment. The results formalize that replacing DFT-based circular convolution with Hadamard-based dyadic convolution fundamentally changes the operation being computed.

Predictability: The error is determined by the "matching set" of indices where modular and XOR arithmetic coincide.
Inevitability for Generic Signals: For the vast majority of inputs and generic filters, the substitution introduces substantial error (asymptotically doubling output energy), rather than a negligible perturbation.
Design Implication: The alignment scalar $Q(u)/\|u\|^2_2$ serves as a diagnostic metric. While the paper does not propose new training methods, it highlights that whether learned filters in neural networks naturally align with the zero-error subspace is an open empirical question, given that the subspace is extremely small relative to the total parameter space.

The work concludes that while Hadamard transforms offer hardware efficiency, their interchangeability with DFTs in convolutional settings is limited to a negligible subspace of filters and inputs, and the resulting error must be understood as a structural consequence of non-isomorphic group convolutions.

The Great Swap: When "Fast" Isn't "Right"

The Discovery: It's Not Just Random Noise

The "Alignment" Secret

Why This Matters

Technical Summary: Structure of the Circular–Dyadic Convolution Error

More like this