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 with convolution f * g.
Let F be the operator performing the Fourier transform such that e.g. F f is the Fourier transform of f.
Then
- F (f * g) = (F f) · (F g),
where · denotes the point-wise multiplication. It also works "the other way round":
- F (f · g) = (F f) * (F g).
By using 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.