The convolution theorem
states that the Fourier transform
of a convolution
is the point-wise product of Fourier transforms.
Let f and g be two functions with convolution f * g.
(Note that the asterisk denotes convolution in this context, and not multiplication.)
Let F denote the Fourier transform operator, so F f and F g are the Fourier transforms of f and g, respectively.
- F (f * g) = (F f) · (''F g'\'),
where · denotes point-wise multiplication. It also works "the other way round":
- F (f · g) = (F f) * (F g).
By applying the inverse Fourier transfrom F-1
, we can write
- f * g = F-1 (F f · F g),
a formulation which is especially useful for implementing a numerical convolution on a computer
The standard convolution algorithm 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
). This can be exploited to construct fast multiplication algorithms.