Convolution and the Fourier transform

Posted by David Zaslavsky on September 28, 2010 2:57 AM

— Comments

One of the neat properties of the Fourier transform is that if you want to convolve two functions, an easy way to do it is to multiply their Fourier transforms together and then take the inverse Fourier transform of the result. It’s often said as “convolution in normal space corresponds to multiplication in Fourier space.” I think I’ve always accepted this on faith, but today I had occasion to actually come up with a proof.

To start with, let’s make some definitions. The convolution of two functions $f(x)$ and $g(x)$ is the result of shifting and scaling one function by each point of the other. It’s usually used in applications where one of the functions is a Gaussian distribution, or some other function that has a peak at some point, and in that case you can think of it like this: suppose $g(x)$ is the function with the peak. For each point $\bigl(y,f(y)\bigr)$, make a copy of $g(x)$, and shift it over so that the peak is at $y$. Then multiply it by the value of $f(y)$. The sum of all those scaled and shifted peaks is the convolution.

Convolution of a Gaussian with a sine wave

The image shows a visual representation of the convolution of a Gaussian curve $\exp(-x^2)$ with a sine wave $2\sin(x)$ — heck, who are we kidding, it’s just there to look pretty. But if you’d like to interpret it, the dashed curve shows the original sine wave, and a selection of the scaled and shifted Gaussians are shown in various colors. The end result of this happens to be proportional to the original sine wave, and it’s represented by the gray shading.

Mathematically, the convolution of two functions $f$ and $g$ is written and defined like this:

$$[f*g](x) = \int_{-\infty}^{\infty} f(x - y)g(y)\udc y$$

or equivalently,

$$[f*g](x) = \int_{-\infty}^{\infty} g(x - y)f(y)\udc y$$

The two definitions are precisely equivalent, even though they may not look like it at first glance. You can prove it by making the change of variables $z = x - y$ in either definition.

Moving on, the Fourier transform breaks up a function $f(x)$ into its frequency components, like an equalizer. It’s written and defined as

$$\tilde{f}(k) = \frac{1}{\sqrt{2\pi}}\int_{-\infty}^{\infty}f(x) e^{-ikx}\udc x$$

The value $\tilde{f}(k)$ is the “amount” of frequency $k$ that exists within the function.

Now, suppose we use $h(x)$ to denote the convolution of $f(x)$ and $g(x)$; that is, $h(x) = [f*g](x)$. The statement that forms the subject of this post, that convolution in normal space is equivalent to multiplication in Fourier space, can be written like this:

$$\tilde{h}(k) = \sqrt{2\pi}\tilde{f}(k) \tilde{g}(k)$$

This is saying that if we convolve and then take the Fourier transform, it’s the same as taking the Fourier transforms and then multiplying, except for a constant coefficient. To prove it, it’s easiest to evaluate both sides of this equation independently and show that they come out to the same value. (From this point forward I’ll omit the limits on the integrals, but remember that they are $\pm\infty$)

$$\tilde{h}(k) = \frac{1}{\sqrt{2\pi}}\int h(x)e^{ikx}\udc x = \frac{1}{\sqrt{2\pi}}\iint f(x - y)g(y)e^{ikx}\udc x\udc y$$

and

$$\tilde{f}(k) \tilde{g}(k) = \frac{1}{\sqrt{2\pi}}\int f(x)e^{ikx}\udc x\times\frac{1}{\sqrt{2\pi}}\int g(y)e^{iky}\udc y = \frac{1}{2\pi}\int f(x)g(y)e^{ik(x+y)}\udc x\udc y$$

The key to showing the equality is making the change of variables $u = x + y$ in the second integral:

$$\tilde{f}(k) \tilde{g}(k) = \frac{1}{2\pi}\int f(u - y)g(y)e^{iku}\udc u\udc y$$

Now if you relabel $u$ as $x$, which you can do since it’s just a dummy variable, this becomes exactly the same (apart from that factor of $\sqrt{2\pi}$) as $\tilde{h}(k)$ from two equations back.