Convolution theorem
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.
Then
- 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 log
n). This can be exploited to construct fast multiplication algorithms.