Convolution

Level AdvancedDifficulty ★★★★★Concept⌖ Open in the map

What is it?

$(f * g)(t) = \int f(\tau)\,g(t - \tau)\,\dd\tau$ : a sliding weighted average of one function by another. Blur, echo, smoothing, the output of any linear time-invariant system — and, discretized, the operation that gives convolutional neural networks their name.

Formulas

$(f * g)(t) = \int_{-\infty}^{\infty} f(\tau)\,g(t - \tau)\,\dd\tau, \qquad (x * h)[n] = \sum_k x[k]\,h[n - k]$; $p_{X+Y} = p_X * p_Y$
the density of a sum of independent variables $X$ , $Y$

Where it shows up in computing

Image processing and computer vision★★★★★fundamentalSignals, media and vision
Blur, sharpen and edge filters are convolutions with small kernels.
Digital filters★★★★★fundamentalSignals, media and vision
An FIR filter is a convolution of the signal with its impulse response.
Signal processing★★★★★fundamentalSignals, media and vision
The output of any LTI system is the input convolved with the impulse response (reverb = convolution with a room).

Where it shows up in AI

Convolutional networks (CNNs)★★★★★fundamentalAI and machine learning
A conv layer slides learned kernels over the input (strictly, a cross-correlation: the kernel is not flipped).

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

Exercises

1Computation

Convolve the sequence $[1, 2, 3]$ with the kernel $[1, 1]/2$ .

Solution

$[0.5,\ 1.5,\ 2.5,\ 1.5]$ : a moving average (with the edges padded by zeros).

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

What is it?

Formulas

Where it shows up in computing

Where it shows up in AI

Where is it used?

ℒ AI and machine learning

∿ Signals, media and vision

⊕ Cryptography and security

Exercises