Answers · The mathematics underneath

Why does sliding a filter along a signal become simple multiplication after a Fourier transform?

In shortBecause a filter scales every steady rhythm without changing its rate, so the whole sliding sum collapses into one multiplication for each rhythm.

Because a steady rhythm comes out of a sliding sum as the same rhythm, changed only in size and starting point, the entire filter collapses into one multiplier per rate. The sliding is expensive only because it repeats the same addition at every offset; once the signal is described rate by rate, there is no offset left to repeat.

x[n] = e^{i\omega n}, \qquad (h * x)[n] = \sum_m h[m]\, e^{i\omega(n-m)} = e^{i\omega n} \underbrace{\sum_m h[m]\, e^{-i\omega m}}_{H(\omega)}

Why a rhythm survives the slide

The bracket is a sum over the weights alone. The position $n$ has cancelled out of it completely, which is the whole of the argument: whatever offset the weights sit at, they see the same rhythm displaced by the same fraction of a cycle, so they pick up the same phases every time and those phases can be gathered into one factor. $H(\omega)$ is therefore a single complex number per rate: its modulus is how much the filter multiplies that rhythm by, its argument is how far it delays it. The slide has become one multiplication, and that multiplication is between numbers labelled by rate, never between samples labelled by time.

FIG 1

rate		gain

Read the column downwards. The slowest rate comes through at full size, which is what being an average means. A rhythm at $2\pi/3$ , two thirds of the way to the fastest rate the record can carry, is annihilated: the three contributions arrive a third of a cycle apart, the three vectors close into a triangle, and the sum is zero. Nothing downstream can recover that rate, because nothing of it reaches the output. Past the zero the gain is negative, so a faster rhythm emerges upside down rather than merely shrunken. The leftover factor $e^{-i\omega}$ is the delay, and it is exactly one reading, which is why the average reports the middle of its window rather than its left edge.

What the multiplication saves

Take the short record two, eight, two, two, two, fourteen, two with the three weights above. The first output is $(2 + 8 + 2)/3 = 4$ , the second is $(8 + 2 + 2)/3 = 4$ , and five positions in all give fifteen multiply-adds. Scale that up: a thousand weights slid along a million readings is $1000 \times 10^6 = 10^9$ multiplications. The fast transform of a million readings takes about twenty passes over the data, since $2^{20} = 1{,}048{,}576$ , so roughly $20 \times 10^6$ operations per transform, around $4 \times 10^7$ for the two transforms plus $10^6$ for the rate by rate products. Three orders of magnitude, and the gap widens as the weights lengthen.

The guess that fails

The natural reading of "becomes multiplication" is that you multiply the signal by the filter sample by sample, and that reading is wrong in a way that inverts the meaning. Multiplying two rhythms together adds their rates: a rhythm at $\omega$ times a rhythm at $\theta$ is a rhythm at $\omega + \theta$ . So a pointwise product takes each rate and shifts it somewhere else, smearing the spectrum, which is the one thing a filter never does. The theorem is not about multiplying the signal by the weights. It is about multiplying the signal's arrow at rate $k$ by the filter's arrow at that same rate $k$ , and the two factors carry the same index, so no rate is ever added to another. Crudely: a slide at every position is the same as a scale at every rate.

That also explains why the result is worth having in both directions. Left to right it is a way of computing a sliding sum quickly. Right to left it is a way of designing one: choose the size and delay you want at each rate, write those arrows down, transform back, and the weights appear. The negative gain in the table, for instance, is simply a design choice made visible.

Where it stops

Two assumptions are load bearing. The weights must be identical at every position. Let the filter change as it goes, an adaptive coefficient or a gate that opens and shuts, and the rhythms no longer come back unchanged, no single multiplier per rate exists, and the multiplication fails outright. The other is length. A finite transform treats the end of the record as adjacent to the beginning, so a sliding sum that runs past the end wraps round and corrupts the earliest outputs with the latest readings. Padding both signals with zeros, long enough to hold the full overlap, is the repair, and it costs nothing but memory.

Worth keeping

A filter can change the size and starting point of a steady rhythm but never its rate, so no energy ever moves between rates.
The rhythm at rate k is an eigenfunction of every sliding sum, with eigenvalue equal to the filter's own transform at that same rate, which is why the slide turns into one multiplication.
Multiplying two signals sample by sample adds their rates together and smears the spectrum; the multiplication in the convolution theorem is indexed by rate, not by time.

Where this goes next

This question is one step of The Fourier Transform, a course that works through its subject from the beginning. The page that teaches this part of it is Sliding Becomes Multiplying, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course