Convolution theorem

The convolution theorem states that the convolution is transformed into a point-wise multiplication by the Fourier transform.

Let f and g be two functions. Let F be the operator performing the Fourier transform such that e.g. F f is the Fourier transform of f. f * g be the convolution of f and g. Then

F (f * g) = F f · F g,

where · denotes the point-wise multiplication. The convolution theorem appears also in the following forms:

f * g = F^-1 (F f · F g),

F^-1 (F f * F g) = f · g

where F^-1 is the reverse Fourier transform.

The second form is especially useful for implementing a numerical convolution on a computer: The convolution has quadratic computational complexity. With the help of the convolution theorem and the fast Fourier transform, the complexity of the convolution can be reduced to O(n log (n)).