Skip to content

What is the Convolution?

Addition, multiplication, and convolution are three different ways to combine the same two inputs.
Convolution is a rule for combining two objects by measuring how much they overlap after one of them has been shifted. The notion of convolution of two functions plays a fundamental role in Fourier analysis; it appears naturally in the context of Fourier series but also serves more generally in the analysis of functions in other settings.
CONVOLUTION OF PERIODIC FUNCTIONS
Given two 2π2\pi-periodic integrable functions ff and gg on R\mathbb{R}, we define their convolution f∗gf*g on [−π,π][-\pi,\pi] by
(f∗g)(x)=12π∫−ππf(y)g(x−y) dy.\begin{equation*}(f*g)(x)=\frac{1}{2\pi}\int_{-\pi}^{\pi} f(y)g(x-y)\,\mathrm{d}y.\end{equation*}
In the context of Fourier series, convolution appears because the partial sums of the Fourier series of ff can be written as a convolution. Indeed,
SN(f)(x)=∑n=−NNf^(n)einx=∑n=−NN(12π∫−ππf(y)e−iny dy)einx=12π∫−ππf(y)(∑n=−NNein(x−y)) dy=(f∗DN)(x),\begin{align*}S_N(f)(x)&= \sum_{n=-N}^{N}\widehat{f}(n)e^{inx} \\&=\sum_{n=-N}^{N} \left( \frac{1}{2\pi}\int_{-\pi}^{\pi} f(y)e^{-iny}\,\mathrm{d}y \right)e^{inx} \\&= \frac{1}{2\pi}\int_{-\pi}^{\pi} f(y) \left( \sum_{n=-N}^{N}e^{in(x-y)} \right) \,\mathrm{d}y \\&=(f*D_N)(x),\end{align*}
where
DN(t)=∑n=−NNeint\begin{equation*}D_N(t)=\sum_{n=-N}^{N}e^{int}\end{equation*}
is the Dirichlet kernel.
Blur with the average kernel
A digital image can be viewed as a discrete function on a grid. In image convolution, a small matrix called a kernel is shifted across the image, and each output pixel is computed by multiplying nearby input pixels by the corresponding kernel weights and summing the results:
(I∗K)i,j=∑u,vIi−u,j−vKu,v.\begin{equation*}(I*K)_{i,j} = \sum_{u,v} I_{i-u,j-v}K_{u,v}.\end{equation*}
For color images, the same formula is applied to each color channel. The next two videos show this discrete convolution rule as an image-processing operation.
A Gaussian blur
Convolution also interacts well with Fourier analysis: transforming a convolution turns it into multiplication. This is one reason convolution is central in Fourier series and in many algorithms for filtering or solving differential equations.
ALGEBRAIC PROPERTIES OF CONVOLUTION
Let ff, gg, and hh be 2π2\pi-periodic integrable functions. Then
f∗(g+h)=(f∗g)+(f∗h),(cf)∗g=c(f∗g)=f∗(cg)for every c∈C,f∗g=g∗f,(f∗g)∗h=f∗(g∗h).\begin{align*}f*(g+h) &= (f*g)+(f*h), \\(cf)*g &= c(f*g)=f*(cg) \qquad \text{for every } c\in\mathbb{C}, \\f*g &= g*f, \\(f*g)*h &= f*(g*h).\end{align*}
Linearity follows from linearity of the integral in the definition of convolution. For commutativity, use the change of variables t=x−yt=x-y and periodicity:
(f∗g)(x)=12π∫−ππf(y)g(x−y) dy=12π∫−ππg(t)f(x−t) dt=(g∗f)(x).\begin{align*}(f*g)(x)&= \frac{1}{2\pi}\int_{-\pi}^{\pi} f(y)g(x-y)\,\mathrm{d}y \\&= \frac{1}{2\pi}\int_{-\pi}^{\pi} g(t)f(x-t)\,\mathrm{d}t \\&= (g*f)(x).\end{align*}
For associativity, Fubini's theorem and periodicity give
((f∗g)∗h)(x)=1(2π)2∫−ππ∫−ππf(z)g(y−z)h(x−y) dz dy=1(2π)2∫−ππf(z)(∫−ππg(u)h(x−z−u) du) dz=12π∫−ππf(z)(g∗h)(x−z) dz=(f∗(g∗h))(x).\begin{align*}((f*g)*h)(x)&=\frac{1}{(2\pi)^2}\int_{-\pi}^{\pi}\int_{-\pi}^{\pi}f(z)g(y-z)h(x-y)\,\mathrm{d}z\,\mathrm{d}y \\&=\frac{1}{(2\pi)^2}\int_{-\pi}^{\pi}f(z)\left(\int_{-\pi}^{\pi}g(u)h(x-z-u)\,\mathrm{d}u\right)\,\mathrm{d}z \\&=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(z)(g*h)(x-z)\,\mathrm{d}z \\&=(f*(g*h))(x).\end{align*}
REGULARITY OF CONVOLUTION
Let ff and gg be 2π2\pi-periodic Riemann integrable functions. Then f∗gf*g is continuous.
Since ff is Riemann integrable on a compact interval, it is bounded; choose B>0B>0 such that ∣f(y)∣≤B|f(y)|\le B. If x1x_1 and x2x_2 are real, then
∣(f∗g)(x1)−(f∗g)(x2)∣=∣12π∫−ππf(y)(g(x1−y)−g(x2−y)) dy∣≤B2π∫−ππ∣g(x1−y)−g(x2−y)∣ dy.\begin{align*}|(f*g)(x_1)-(f*g)(x_2)|&=\left|\frac{1}{2\pi}\int_{-\pi}^{\pi}f(y)\bigl(g(x_1-y)-g(x_2-y)\bigr)\,\mathrm{d}y\right| \\&\le\frac{B}{2\pi}\int_{-\pi}^{\pi}|g(x_1-y)-g(x_2-y)|\,\mathrm{d}y.\end{align*}
The final integral tends to 00 as x1→x2x_1\to x_2, because translations are continuous in L1L^1 for Riemann integrable periodic functions. Indeed, approximate gg in L1L^1 by a continuous periodic function qq, and use
∥τag−g∥1≤2∥g−q∥1+∥τaq−q∥1,\begin{equation*}\|\tau_a g-g\|_1\le2\|g-q\|_1+\|\tau_a q-q\|_1,\end{equation*}
where the last term tends to 00 by uniform continuity of qq. Therefore f∗gf*g is continuous.
FOURIER TRANSFORM OF CONVOLUTION
Let ff and gg be 2π2\pi-periodic integrable functions. Then for every n∈Zn\in\mathbb{Z},
f∗g^(n)=f^(n)g^(n).\begin{equation*}\widehat{f*g}(n)=\widehat{f}(n)\widehat{g}(n).\end{equation*}
Using the definition of convolution and Fubini's theorem,
f∗g^(n)=12π∫−ππ(f∗g)(x)e−inx dx=12π∫−ππ12π(∫−ππf(y)g(x−y) dy)e−inx dx=12π∫−ππf(y)e−iny(12π∫−ππg(x−y)e−in(x−y) dx) dy=12π∫−ππf(y)e−inyg^(n) dy=f^(n)g^(n).\begin{align*}\widehat{f*g}(n)&=\frac{1}{2\pi}\int_{-\pi}^{\pi}(f*g)(x)e^{-inx}\,\mathrm{d}x \\&=\frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{1}{2\pi}\left(\int_{-\pi}^{\pi}f(y)g(x-y)\,\mathrm{d}y\right)e^{-inx}\,\mathrm{d}x \\&=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(y)e^{-iny}\left(\frac{1}{2\pi}\int_{-\pi}^{\pi}g(x-y)e^{-in(x-y)}\,\mathrm{d}x\right)\,\mathrm{d}y \\&=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(y)e^{-iny}\widehat{g}(n)\,\mathrm{d}y \\&=\widehat{f}(n)\widehat{g}(n).\end{align*}
In the inner integral, the change of variables t=x−yt=x-y is allowed because gg is 2π2\pi-periodic.

References

  • [SteinShakarchi2003]Stein, Elias M., and Rami Shakarchi. Fourier Analysis: An Introduction. First edition. Princeton University Press, 2003.
  • [Sanderson2022]Sanderson, Grant. ``But what is a convolution?'' 3Blue1Brown, 2022. Video.