In mathematics, the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the product of their Fourier transforms. More generally, convolution in one domain (e.g., time domain) equals point-wise multiplication in the other domain (e.g., frequency domain). Other versions of the convolution theorem are applicable to various Fourier-related transforms.
Functions of a continuous variable
Consider two functions <math>u(x)</math> and <math>v(x)</math> with Fourier transforms <math>U</math> and <math>V</math>:
<math display="block">\begin{align}
U(f) &\triangleq \mathcal{F}\{u\}(f) = \int_{-\infty}^{\infty}u(x) e^{-i 2 \pi f x} \, dx, \quad f \in \mathbb{R}\\[1ex]
V(f) &\triangleq \mathcal{F}\{v\}(f) = \int_{-\infty}^{\infty}v(x) e^{-i 2 \pi f x} \, dx, \quad f \in \mathbb{R}
\end{align}</math>
where <math>\mathcal{F}</math> denotes the Fourier transform operator. The transform may be normalized in other ways, in which case constant scaling factors (typically <math>2\pi</math> or <math>\sqrt{2\pi}</math>) will appear in the convolution theorem below. The convolution of <math>u</math> and <math>v</math> is defined by:
<math display="block">r(x) = \{u*v\}(x) \triangleq \int_{-\infty}^{\infty} u(\tau) v(x-\tau)\, d\tau = \int_{-\infty}^{\infty} u(x-\tau) v(\tau)\, d\tau.</math>
In this context the asterisk denotes convolution, instead of standard multiplication. The tensor product symbol <math>\otimes</math> is sometimes used instead.
The convolution theorem states that:
that any linear transform that turns convolution into a product is the DFT (up to a permutation of coefficients).
A time-domain derivation proceeds as follows:
<math display="block">
\begin{align}
\scriptstyle{\rm DFT}\displaystyle \{u_{_N} * v\}[k] &\triangleq \sum_{n=0}^{N-1} \left(\sum_{m=0}^{N-1} u_{_N}[m]\cdot v_{_N}[n-m]\right) e^{-i 2\pi kn/N}\\
&= \sum_{m=0}^{N-1} u_{_N}[m] \left(\sum_{n=0}^{N-1} v_{_N}[n-m]\cdot e^{-i 2\pi kn/N}\right)\\
&= \sum_{m=0}^{N-1} u_{_N}[m]\cdot e^{-i 2\pi km/N}
\underbrace{
\left(\sum_{n=0}^{N-1} v_{_N}[n-m]\cdot e^{-i 2\pi k(n-m)/N}\right)}_{\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\quad \scriptstyle \text{due to periodicity\\
&= \underbrace{
\left(\sum_{m=0}^{N-1} u_{_N}[m]\cdot e^{-i 2\pi km/N}\right)}_{\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]}
\left(\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\right).
\end{align}
</math>
A frequency-domain derivation follows from , which indicates that the DTFTs can be written as:
<math display="block">
\mathcal{F}\{u_{_N} * v\}(f) = \frac{1}{N} \sum_{k=-\infty}^{\infty} \left(\scriptstyle{\rm DFT}\displaystyle \{u_{_N} * v\}[k]\right)\cdot \delta\left(f-k/N\right). \quad \scriptstyle \mathsf{(Eq.5a)}
</math>
<math display="block">
\mathcal{F}\{u_{_N}\}(f) = \frac{1}{N} \sum_{k=-\infty}^{\infty} \left(\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\right)\cdot \delta\left(f-k/N\right).
</math>
The product with <math>V(f)</math> is thereby reduced to a discrete-frequency function:
<math display="block">\begin{align}
\mathcal{F}\{u_{_N} * v\}(f) &= G_{_N}(f) V(f) \\
&= \frac{1}{N} \sum_{k=-\infty}^{\infty} \left(\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\right)\cdot V(f)\cdot \delta\left(f-k/N\right)\\
&= \frac{1}{N} \sum_{k=-\infty}^{\infty} \left(\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\right)\cdot V(k/N)\cdot \delta\left(f-k/N\right)\\
&= \frac{1}{N} \sum_{k=-\infty}^{\infty} \left(\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\right)\cdot \left(\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\right) \cdot \delta\left(f-k/N\right), \quad \scriptstyle \mathsf{(Eq.5b)}
\end{align}
</math>
where the equivalence of <math>V(k/N)</math> and <math>\left(\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\right)</math> follows from . Therefore, the equivalence of (5a) and (5b) requires:
<math display="block">\scriptstyle{\rm DFT}
\displaystyle {\{u_{_N} * v\}[k]}
= \left(\scriptstyle{\rm DFT}
\displaystyle\{u_{_N}\}[k]\right)\cdot \left(\scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\right).</math>
<br>We can also verify the inverse DTFT of (5b):
<math display="block">\begin{align}
(u_{_N} * v)[n] & = \int_{0}^{1} \left(\frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\cdot \scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\cdot \delta\left(f-k/N\right)\right)\cdot e^{i 2 \pi f n} df \\
& = \frac{1}{N} \sum_{k=-\infty}^{\infty} \scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\cdot \scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\cdot \underbrace{\left(\int_{0}^{1} \delta\left(f-k/N\right)\cdot e^{i 2 \pi f n} df\right)}_{\text{0, for} \ k\ \notin\ [0,\ N)} \\
& = \frac{1}{N} \sum_{k=0}^{N-1} \bigg(\scriptstyle{\rm DFT}\displaystyle\{u_{_N}\}[k]\cdot \scriptstyle{\rm DFT}\displaystyle\{v_{_N}\}[k]\bigg)\cdot e^{i 2 \pi \frac{n}{N} k}\\
&=\ \scriptstyle{\rm DFT}^{-1} \displaystyle \bigg( \scriptstyle{\rm DFT}\displaystyle \{u_{_N}\}\cdot \scriptstyle{\rm DFT}\displaystyle \{v_{_N}\} \bigg).
\end{align}</math>
Convolution theorem for inverse Fourier transform
There is also a convolution theorem for the inverse Fourier transform:
Here, "<math>\cdot</math>" represents the Hadamard product, and "<math>*</math>" represents a convolution between the two matrices.
<math display="block">\begin{align}
&\mathcal{F}\{u*v\} = \mathcal{F}\{u\} \cdot \mathcal{F}\{v\}\\
&\mathcal{F}\{u \cdot v\}= \mathcal{F}\{u\}*\mathcal{F}\{v\}
\end{align}</math>
so that
<math display="block">\begin{align}
&u*v= \mathcal{F}^{-1}\left\{\mathcal{F}\{u\}\cdot\mathcal{F}\{v\}\right\}\\
&u \cdot v= \mathcal{F}^{-1}\left\{\mathcal{F}\{u\}*\mathcal{F}\{v\}\right\}
\end{align}</math>
Convolution theorem for tempered distributions
The convolution theorem extends to tempered distributions.
Here, <math>v</math> is an arbitrary tempered distribution:
<math display="block">\begin{align}
&\mathcal{F}\{u*v\} = \mathcal{F}\{u\} \cdot \mathcal{F}\{v\}\\
&\mathcal{F}\{u \cdot v\}= \mathcal{F}\{u\}*\mathcal{F}\{v\}.
\end{align}</math>
But <math>\alpha = F\{u\}</math> must be "rapidly decreasing" towards <math>-\infty</math> and <math>+\infty</math> in order to guarantee the existence of both, convolution and multiplication product. Equivalently, if <math>u = F^{-1}\{\alpha\}</math> is a smooth "slowly growing" ordinary function, it guarantees the existence of both, multiplication and convolution product.
In particular, every compactly supported tempered distribution, such as the Dirac delta, is "rapidly decreasing". Equivalently, bandlimited functions, such as the function that is constantly <math>1</math> are smooth "slowly growing" ordinary functions. If, for example, <math>v\equiv\operatorname{\text{Ш</math> is the Dirac comb both equations yield the Poisson summation formula and if, furthermore, <math>u\equiv\delta</math> is the Dirac delta then <math>\alpha \equiv 1</math> is constantly one and these equations yield the Dirac comb identity.
See also
- Moment-generating function of a random variable
Notes
References
Further reading
Additional resources
For a visual representation of the use of the convolution theorem in signal processing, see:
- Johns Hopkins University's Java-aided simulation: http://www.jhu.edu/signals/convolve/index.html
de:Faltung (Mathematik)#Faltungstheorem 2
fr:Produit de convolution