---
title: "Convolution theorem"
sort_title: "Convolution theorem"
date: 2021-02-22
categories:
- Mathematics
layout: "concept"
---

The **convolution theorem** states that a convolution in the real domain
is equal to a product in the frequency domain.
This fact is especially useful for computation,
as it allows replacing an $$\mathcal{O}(n^2)$$ convolution
with an $$\mathcal{O}(n \log(n))$$ transform and product.



## Fourier transform

The convolution theorem is usually expressed as follows,
where $$\hat{\mathcal{F}}$$ is the [Fourier transform](/know/concept/fourier-transform/),
and $$A$$ and $$B$$ are the constants from its definition:

$$\begin{aligned}
    \boxed{
        \begin{aligned}
            A \cdot (f * g)(x)
            &= \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\}
            \\
            B \cdot (\tilde{f} * \tilde{g})(k)
            &= \hat{\mathcal{F}}\Big\{ f(x) \: g(x) \Big\}
        \end{aligned}
    }
\end{aligned}$$


{% include proof/start.html id="proof-fourier" -%}
We expand the right-hand side of the theorem and rearrange the integrals:

$$\begin{aligned}
    \hat{\mathcal{F}}{}^{-1}\Big\{ \tilde{f}(k) \: \tilde{g}(k) \Big\}
    &= B \int_{-\infty}^\infty \tilde{f}(k) \bigg( A \int_{-\infty}^\infty g(x') \: e^{i s k x'} \dd{x'} \bigg) e^{-i s k x} \dd{k}
    \\
    &= A \int_{-\infty}^\infty g(x') \bigg( B \int_{-\infty}^\infty \tilde{f}(k) \: e^{-i s k (x - x')} \dd{k} \bigg) \dd{x'}
    \\
    &= A \int_{-\infty}^\infty g(x') \: f(x - x') \dd{x'}
    \\
    &= A \cdot (f * g)(x)
\end{aligned}$$

Then we do the same again,
this time starting from a product in the $$x$$-domain:

$$\begin{aligned}
    \hat{\mathcal{F}}\Big\{ f(x) \: g(x) \Big\}
    &= A \int_{-\infty}^\infty f(x) \bigg( B \int_{-\infty}^\infty \tilde{g}(k') \: e^{-i s x k'} \dd{k'} \bigg) e^{i s k x} \dd{x}
    \\
    &= B \int_{-\infty}^\infty \tilde{g}(k') \bigg( A \int_{-\infty}^\infty f(x) \: e^{i s x (k - k')} \dd{x} \bigg) \dd{k'}
    \\
    &= B \int_{-\infty}^\infty \tilde{g}(k') \: \tilde{f}(k - k') \dd{k'}
    \\
    &= B \cdot (\tilde{f} * \tilde{g})(k)
\end{aligned}$$
{% include proof/end.html id="proof-fourier" %}



## Laplace transform

For functions $$f(t)$$ and $$g(t)$$ that are only defined for $$t \ge 0$$,
the convolution theorem can also be stated using
the [Laplace transform](/know/concept/laplace-transform/):

$$\begin{aligned}
    \boxed{
        (f * g)(t)
        = \hat{\mathcal{L}}{}^{-1}\Big\{ \tilde{f}(s) \: \tilde{g}(s) \Big\}
    }
\end{aligned}$$

Because the inverse Laplace transform $$\hat{\mathcal{L}}{}^{-1}$$ is usually difficult,
the theorem is often stated using the forward transform instead:

$$\begin{aligned}
    \boxed{
        \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\}
        = \tilde{f}(s) \: \tilde{g}(s)
    }
\end{aligned}$$


{% include proof/start.html id="proof-laplace" -%}
We expand the left-hand side.
Note that the lower integration limit is 0 instead of $$-\infty$$,
because we choose to set both $$f(t)$$ and $$g(t)$$ to zero for $$t < 0$$:

$$\begin{aligned}
    \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\}
    &= \int_0^\infty \bigg( \int_0^\infty g(t') \: f(t - t') \dd{t'} \bigg) e^{-s t} \dd{t}
    \\
    &= \int_0^\infty \bigg( \int_0^\infty f(t - t') \: e^{-s t} \dd{t} \bigg) \: g(t') \dd{t'}
\end{aligned}$$

Then we define a new integration variable $$\tau = t - t'$$, yielding:

$$\begin{aligned}
    \hat{\mathcal{L}}\Big\{ (f * g)(t) \Big\}
    &= \int_0^\infty \bigg( \int_0^\infty f(\tau) \: e^{-s (\tau + t')} \dd{\tau} \bigg) \: g(t') \dd{t'}
    \\
    &= \int_0^\infty \bigg( \int_0^\infty f(\tau) \: e^{-s \tau} \dd{\tau} \bigg) \: g(t') \: e^{-s t'} \dd{t'}
    \\
    &= \int_0^\infty \tilde{f}(s) \: g(t') \: e^{-s t'} \dd{t'}
    \\
    &= \tilde{f}(s) \: \tilde{g}(s)
\end{aligned}$$
{% include proof/end.html id="proof-laplace" %}



## References
1.  O. Bang,
    *Applied mathematics for physicists: lecture notes*, 2019,
    unpublished.