% Convolution theorem


# Convolution theorem

The **convolution theorem** states that a convolution in the direct domain
is equal to a product in the frequency domain. This is especially useful
for computation, 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 constants from its definition:

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

To prove this, we expand the right-hand side of the theorem and
rearrange the integrals:

$$\begin{aligned}
    \hat{\mathcal{F}}^{-1}\{\tilde{f}(k) \: \tilde{g}(k)\}
    &= B \int_{-\infty}^\infty \tilde{f}(k) \Big( A \int_{-\infty}^\infty g(x') \exp(i s k x') \dd{x'} \Big) \exp(-i s k x) \dd{k}
    \\
    &= A \int_{-\infty}^\infty g(x') \Big( B \int_{-\infty}^\infty \tilde{f}(k) \exp(- i s k (x - x')) \dd{k} \Big) \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 thing again, this time starting from a product in
the $x$-domain:

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


## Laplace transform

For functions $f(t)$ and $g(t)$ which are only defined for $t \ge 0$,
the convolution theorem can also be stated using the Laplace transform:

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

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

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

We prove this by expanding the left-hand side. Note that the lower
integration limit is 0 instead of $-\infty$, because we set both $f(t)$
and $g(t)$ to zero for $t < 0$:

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

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

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