Convolutions Using Fourier Transform

#Fourier Transform #Convolution

Convolution

$$ (f*h)(x) = \int \mathrm d f(y) h(x-y), $$

is equivalent to

$$ \mathcal F^{-1}\left[ \mathcal F[ f(x) ] \circ \mathcal F[h(x)] \right], $$

with $\mathcal F$ being the Fourier transform, i.e.,

$$ \mathcal F[f(x)] = \int \mathrm d x f(x) e^{-2\pi i x s}. $$

Proof

One could prove it using the Fourier integral theorem,

$$ f(x) = \iint dy d\xi f(y)e^{2\pi i (x-y)\xi}. $$

Derivation

Given

$$ \begin{align} \mathcal F_s \left(f(y)\right) &= \int dy f(y) e^{-2\pi i y s}, \\ \mathcal F_s \left(h(y)\right) &= \int dz h(z) e^{-2\pi i z s}, \end{align} $$

we have

$$ \mathcal F_s(f(y)) \mathcal F_s(h(z)) = \int dz dy f(y)h(z) e^{-2\pi i (y+z) s}. $$

Inverse transform of the above shows

$$ \mathcal F_x^{-1}\left( \mathcal F_s(f(y)) \mathcal F_s(h(z)) \right) = \int ds \int dz dy f(y)h(z) e^{-2\pi i (y+z) s + 2\pi i x s}. $$

Using Fourier integral theorem, we can simplify the formula by defining a new variable ${\color{red}\bar x} = {\color{red}y + z}$

$$ \begin{align} \mathcal F_x^{-1}\left( \mathcal F_s(f(y)) \mathcal F_s(h(z)) \right) &= \int dy \int dz ds f(y) h(z) e^{2\pi i ( x - ({\color{red}y+z}) ) s} \\ &= \int dy \int d \bar x ds f(y) h(\bar x - y) e^{2\pi i ( x - {\color{red}\bar x} ) s} \\ &= \int dy f(y) h(\bar x - y) \\ &= (f * h) (\bar x) \end{align} $$

Published: by ;

L Ma (2021). 'Convolutions Using Fourier Transform', Datumorphism, 12 April. Available at: https://datumorphism.leima.is/cards/math/convolution-and-fourier-transform/.

Current Ref:

  • cards/math/convolution-and-fourier-transform.md