What is a Convolution Anyway? (Part 1)

Every passing second, we are bombarded with photons. On a sunny day, more of them strike us each second than there are grains of sand on this planet. A tiny portion passes through the pupil (a little more when it dilates), and together these photons bring something encoded within them: raw information, an observation of the real world.

They hit the retina. The rods and cones that sit at its back respond in an unexpected way: in the dark they release a steady stream of neurotransmitter, like the surface of still water, and light makes them release less, like a disturbance. That ripple is the signal. It passes through layers of interneurons (horizontal, bipolar and amacrine cells), many of them wired sideways to their neighbours. Many of these cells respond to a small patch of the retina, pushed one way by the light at its centre and the other way by the light around it, so some parts of the signal are amplified and others attenuated. It is, quite literally, image sharpening and contrast adjustment: edges are exaggerated, flat regions are muted.

What survives is handed to the ganglion cells, whose long fibres bundle together into the optic nerve and carry the encoded information into the brain. And here is the remarkable part: each eye has well over a hundred million rods and cones, but only about a million ganglion cells. Before the signal has even left the eye, it has been squeezed roughly a hundredfold. The brain never sees the photons. It sees a summary.

Perception, for the most part, is the art of throwing data away. It keeps what is relevant (edges, shapes, objects) and discards the rest: sensor noise, the lighting, exactly where something happens to sit. What remains is a compact description of the scene, organised so that similar things sit close together: two glimpses of a cat end up near each other, even if they share almost no photons.

In machine learning, we call that compact description a representation, and the space it lives in a latent space. Some of its directions may turn out to mean something we can name, like “how furry” or “how round”. Many don’t, and whether we can read them at all is still an open question. What matters is that the latent space is useful: what we care about is easy to read off from it, and what we don’t care about is gone.

Machines that model biological visual perception

A convolutional neural network (CNN) is a machine built to do exactly this. To a computer, a photo is a grid of numbers: a modest 1000 × 1000 colour photo holds three million of them. Mathematically, a CNN is just a function: it takes a data matrix like that grid of pixels and returns a point in a latent space. A photo goes in; a short list of numbers comes out, from which “cat” is easy to read.

What makes a CNN special is that it is built almost entirely from one operation, repeated many times over: the convolution. So here is the question this series is really about. If you had to design that operation yourself, starting from nothing but a little linear algebra, what would you build?

By the end of this article, you will have built it from scratch, worked out exactly how big its output is, and seen that it is secretly one big matrix multiplication. Let’s start with the smallest piece we need: a way to ask “does this part of the data look like the pattern I care about?”

A dot product that slides

The simplest tool linear algebra gives us for comparing two things is the dot product. Take two vectors $x, w \in \mathbb{R}^d$, with $d = 5$:

$$z = x^\top w = \begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ w_3 \\ w_4 \\ w_5 \end{bmatrix} = \sum_{i=1}^{5} x_i w_i$$

The output is a single scalar $z$, and it tells us how aligned $x$ and $w$ are: for vectors of a given length, the more they point the same way, the larger $z$ is. That is already a pattern detector. If $w$ is the pattern, $z$ says how much $x$ looks like it.

But a pattern is usually much smaller than the data it hides in. Suppose our pattern is another vector $w' \in \mathbb{R}^k$ with $k = 3$. How do you take the dot product $x^\top w'$? You can’t, because the dimensions of the two vectors don’t match!

$$x^\top w' = \begin{bmatrix} x_1 & x_2 & x_3 & x_4 & x_5 \end{bmatrix} \begin{bmatrix} w'_1 \\ w'_2 \\ w'_3 \end{bmatrix} \implies \text{Undefined}$$

But suppose we could. How would we go about it?

One way would be to slide the $k$-sized vector $w'$ along $x$, one position at a time, taking the dot product with whichever $k$ entries of $x$ it currently sits over. (In the slides below, the bold entries are the ones being multiplied.)

Slide 1:

$$\begin{array}{cccccccc} x = & [ & \mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} & x_4 & x_5 & ] \\ w' = & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & & \end{array}$$ $$\rightarrow z_1 = x_1 w'_1 + x_2 w'_2 + x_3 w'_3$$

Slide 2:

$$\begin{array}{cccccccc} x = & [ & x_1 & \mathbf{x_2} & \mathbf{x_3} & \mathbf{x_4} & x_5 & ] \\ w' = & & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & \end{array}$$ $$\rightarrow z_2 = x_2 w'_1 + x_3 w'_2 + x_4 w'_3$$

Slide 3:

$$\begin{array}{cccccccc} x = & [ & x_1 & x_2 & \mathbf{x_3} & \mathbf{x_4} & \mathbf{x_5} & ] \\ w' = & & & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] \end{array}$$ $$\rightarrow z_3 = x_3 w'_1 + x_4 w'_2 + x_5 w'_3$$

Because we took several dot products, the output is no longer a single scalar $z$, but a vector $a$ holding all of those alignment scores:

$$a = \begin{bmatrix} z_1 & z_2 & z_3 \end{bmatrix}$$

This operation is called a cross-correlation, a tool from digital signal processing, and we’ll write it as $x \ast w'$. Machine learning calls the very same operation a convolution. That name has a story, and we’ll see it near the end.

A pattern detector

In deep learning, $x$ is called the input signal. It could represent almost anything: a row of pixels in an image, a slice of an audio Mel-spectrogram, or raw time-series data. What these have in common is local structure: neighbouring values are related to one another, and form meaningful features when grouped together. A few large numbers in the middle of a run of small ones in a stock price, say, mean the price spiked briefly before falling back.

Because $x$ has this local structure, our sliding vector $w'$, called a filter or kernel in both digital signal processing (DSP) and ML, acts as a pattern detector. By sliding $w'$ over $x$ and taking the dot product at every step, we scan the input for stretches that line up with $w'$: the larger the dot product, the better the match.

x22922

w′−12−1

z−7

z₁ = (−1)(2) + (2)(2) + (−1)(9) = −7

Notice that the filter didn’t need to know where the spike was. It used the same three numbers at every position, and the score lit up wherever the pattern happened to be. Move the spike, and the high score moves with it. That is the first thing perception needs: recognising the same thing wherever it appears. (The property has a name, translation equivariance, and we will meet it again.)

Here, we chose $w' = [-1, 2, -1]$ by hand, because we already knew what a spike looks like. Look at its shape: a centre minus its surround, the same computation the retina performs, built from three numbers. In a CNN, nobody chooses. The numbers in every filter are parameters, and training adjusts them, a little at a time, until the patterns they detect are the ones that help with the task. A CNN is never told what an edge or an ear looks like. It discovers which patterns are worth detecting, and whatever no filter responds to is, in effect, thrown away.

The trouble with edges

Every element of $x$ carries information, so ideally the filter should cover each one equally often. Look back at the three slides. Think of the middle entry of the kernel, $\mathbf{w'_2}$, as its centre: wherever it lands, the whole kernel overlaps $x$ and a full dot product is computed. The centre only ever lands on $x_2$, $x_3$ and $x_4$. Here is how often each entry gets touched:

	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
Times touched	1	2	3	2	1

The edge elements never land under the centre, and each meets the kernel only once. $x_3$ is touched in every slide. Our operation is biased toward the middle of the signal: if $x$ is a row of pixels, the data at the borders gets far less say than the data in the middle. (Hold on to that table. It will matter more than it looks.)

The fix is to artificially extend $x$, so that the centre $\mathbf{w'_2}$ can reach the edge entries too. We do this with zero padding ($p$): adding $p$ zeros (blank data points) at each end of $x$. The filter now starts scanning before it hits the actual data, and finishes after it leaves. With $p = 1$, we add one zero on the left and one on the right.

Slide 1 (entering the signal):

$$\begin{array}{cccccccccc} x_{\text{padded}} = & [ & \mathbf{0} & \mathbf{x_1} & \mathbf{x_2} & x_3 & x_4 & x_5 & 0 & ] \\ w' = & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & & & & \end{array}$$ $$\rightarrow z_1 = (0 \cdot w'_1) + (x_1 \cdot w'_2) + (x_2 \cdot w'_3)$$

The padded $0$ multiplies $w'_1$ and adds nothing to the sum. What changes is that $x_1$ now sits under the centre $\mathbf{w'_2}$.

Slide 2 (moving inward):

$$\begin{array}{cccccccccc} x_{\text{padded}} = & [ & 0 & \mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} & x_4 & x_5 & 0 & ] \\ w' = & & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & & & \end{array}$$ $$\rightarrow z_2 = (x_1 \cdot w'_1) + (x_2 \cdot w'_2) + (x_3 \cdot w'_3)$$

(… skipping Slides 3 and 4 …)

Slide 5 (exiting the signal):

$$\begin{array}{cccccccccc} x_{\text{padded}} = & [ & 0 & x_1 & x_2 & x_3 & \mathbf{x_4} & \mathbf{x_5} & \mathbf{0} & ] \\ w' = & & & & & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] \end{array}$$ $$\rightarrow z_5 = (x_4 \cdot w'_1) + (x_5 \cdot w'_2) + (0 \cdot w'_3)$$

$x_1$ and $x_5$ are no longer an afterthought: they sit right in the middle of the pattern detector in Slides 1 and 5. And the output $a$ now has 5 elements instead of 3, exactly as long as the input. Padding has preserved its size (its spatial dimension).

How big is the output?

Before going further, it helps to know exactly how many numbers come out. Suppose we are asked to work out the length of $a$ in advance, given only two pieces of information:

• $d$: the length of $x$
• $k$: the length of $w'$

We can think of the vector $x$ (length 5) as a runway for $w'$ (length 3) to slide on. Since we take one dot product at every position, the number of elements in $a$ equals the number of positions $w'$ can occupy. To see why this depends on the sizes of $x$ and $w'$, suppose they were the same size (say both of length 3): $w'$ would remain locked in place, resulting in a single scalar as the only output.

$$\begin{array}{cccccccc} x = & [ & \mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3}& ] \\ w' = & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & & \end{array}$$ $$\rightarrow z = x_1 w'_1 + x_2 w'_2 + x_3 w'_3$$

To count the empty slots $w'$ can slide into before hitting the wall, we simply subtract: $d - k$. In our original example, $5 - 3 = 2$, so $w'$ has 2 empty slots to move into.

$$\begin{array}{cccccccc} x = & [ & \mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} & {\overbrace{x_4 \quad x_5}^{\text{2 empty slots}}} & ] \\ w' = & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3}&&] & & \end{array}$$

But remember, before we slide into the first empty slot, we have already computed a dot product at the starting position!

$$\begin{array}{cccccccc} x = & [ & \mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} & x_4 & x_5 & ] \\ w' = & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & & \end{array}$$ $$\rightarrow z_1 = x_1 w'_1 + x_2 w'_2 + x_3 w'_3$$

Thus the total number of positions $w'$ can occupy in $x$ is $(5 - 3) + 1 = 3$, which is the size of $a$. So our general formula becomes

$$\text{Dimension of } a = (d - k) + 1$$ $$\text{Dimension of } a = (5 - 3) + 1 = 3$$

And looking back at our vector $a = \begin{bmatrix} z_1 & z_2 & z_3 \end{bmatrix}$, this matches our result! And so we may say that $a \in \mathbb{R}^{(d-k+1)}$.

The cliffhanger: stride

Up until now, we’ve assumed $w'$ slides over by 1 component at a time. We call this step size the stride ($s$). So far, $s = 1$.

But what if we want to speed up the process and skip over some positions? Let’s see what happens if we increase our stride to $s = 2$. To see it clearly, let’s slightly expand our runway: $d = 7$, $k = 3$, and $s = 2$.

Slide 1 (start):

$$\begin{array}{cccccccccc} x = & [ & \mathbf{x_1} & \mathbf{x_2} & \mathbf{x_3} & x_4 & x_5 & x_6 & x_7 & ] \\ w' = & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & & & & \end{array}$$ $$\rightarrow z_1 = x_1 w'_1 + x_2 w'_2 + x_3 w'_3$$

Slide 2 (take a step of 2):

$$\begin{array}{cccccccccc} x = & [ & x_1 & x_2 & \mathbf{x_3} & \mathbf{x_4} & \mathbf{x_5} & x_6 & x_7 & ] \\ w' = & & & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] & \end{array}$$ $$\rightarrow z_2 = x_3 w'_1 + x_4 w'_2 + x_5 w'_3$$

$w'$ seems to have skipped a position: it never started on $x_2$.

Slide 3 (take another step of 2):

$$\begin{array}{cccccccccc} x = & [ & x_1 & x_2 & x_3 & x_4 & \mathbf{x_5} & \mathbf{x_6} & \mathbf{x_7} & ] \\ w' = & & & & & [ & \mathbf{w'_1} & \mathbf{w'_2} & \mathbf{w'_3} & ] \end{array}$$ $$\rightarrow z_3 = x_5 w'_1 + x_6 w'_2 + x_7 w'_3$$

$w'$ skipped again, this time never starting on $x_4$.

With $d = 7$, $k = 3$ and $s = 2$, we ended up with exactly 3 dot products. Now let’s use our old formula to predict how many dot products $a$ would contain:

$$\rightarrow (d - k) + 1 \Rightarrow (7 - 3) + 1 = 5$$

Our formula doesn’t hold for strides greater than 1. The 5 we just got would only be right if $w'$ never skipped $x_2$ and $x_4$, which isn’t possible when $s = 2$.

Let’s go back to our runway. The total number of empty slots $w'$ has to slide into is still $d - k$: for our new example, $7 - 3 = 4$ slots. However, because our stride is $s = 2$, we are eating up those empty slots 2 at a time! To find out how many steps we can take into the runway, we divide the empty slots by our stride:

$$\text{Steps into empty slots} = \frac{d - k}{s} = \frac{7 - 3}{2} = 2 \text{ steps}$$

And just like before, we must add 1 for our very first calculation at the starting position, before we took any steps.

$$\text{Dimension of } a = \frac{d - k}{s} + 1$$ $$\text{Dimension of } a = \frac{7 - 3}{2} + 1 = 3$$

Which matches our 3 slides!

There is one small caveat, though. What if $d = 8$? Our runway of empty slots would be $8 - 3 = 5$, and with steps of 2 we get $5 / 2 = 2.5$ steps. Since $w'$ cannot take half a step and hang off the edge of $x$, we simply discard the decimal. This is called the floor function, written $\lfloor \cdot \rfloor$: it rounds down to the nearest whole number. So our formula for a 1D convolution with stride $s$ is:

$$a \in \mathbb{R}^{\lfloor \frac{d-k}{s} \rfloor + 1}$$

The master formula

How does padding change this? Very simply. Padding doesn’t change the logic of our strides or our dot products; it only makes the runway longer. Because we add $p$ zeros to the left and $p$ zeros to the right, the length of our runway is no longer $d$. It is now $d + 2p$.

To complete our master formula, all we have to do is replace our old runway ($d$) with the new, longer one ($d + 2p$):

$$\text{Dimension of } a = \lfloor \frac{\text{Runway} - k}{s} \rfloor + 1$$ $$\text{Dimension of } a = \lfloor \frac{(d + 2p) - k}{s} \rfloor + 1$$

Let’s plug in the numbers from our padded example ($d = 5$, $k = 3$, $p = 1$, $s = 1$) to make sure it works:

$$\text{Dimension of } a = \lfloor \frac{(5 + 2(1)) - 3}{1} \rfloor + 1$$ $$\text{Dimension of } a = \lfloor \frac{7 - 3}{1} \rfloor + 1$$ $$\text{Dimension of } a = 4 + 1 = 5$$

Five: exactly the five slides we took. And with everything at once, $d = 7$, $k = 3$, $p = 1$ and $s = 2$, we get $\lfloor (9 - 3)/2 \rfloor + 1 = 4$.

And just like that, we have the master formula for the output size of a 1D convolution $x \ast w'\text{:}$

$$a \in \mathbb{R}^{\lfloor \frac{(d+2p)-k}{s} \rfloor + 1}$$

Keep it in mind: in a moment, it will turn out to be counting something much more concrete.

Convolution is a matrix

Look at the three slides one more time. Each $z$ is a dot product of $w'$ with a slice of $x$. A stack of dot products with the same vector $x$ is exactly what a matrix–vector product computes: each row of the matrix, dotted with $x$. So we can write all three slides as one multiplication:

$$\begin{bmatrix} z_1 \\ z_2 \\ z_3 \end{bmatrix} = \begin{bmatrix} w'_1 & w'_2 & w'_3 & 0 & 0 \\ 0 & w'_1 & w'_2 & w'_3 & 0 \\ 0 & 0 & w'_1 & w'_2 & w'_3 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix}$$

or $z = Tx$. Every row holds the same filter, shifted one place to the right, with zeros everywhere else. Each diagonal of $T$ is constant (all $w'_1$, all $w'_2$, all $w'_3$, or all $0$), and a matrix like that is called a Toeplitz matrix.

Now look at what our hard-won arithmetic means here. The output size is the number of rows of $T$: the number of shifted copies of $w'$ that fit inside $x$. Padding lengthens $x$ by $2p$, so $T$ gains $2p$ columns, and room for more rows. A stride of $s$ keeps only every $s$-th row. (Strictly, a strided $T$ is no longer Toeplitz, but it is still a band of shifted copies of $w'$.) The master formula was counting rows all along.

Against a fully connected layer. The standard neural-network layer, a fully connected (dense) layer, also computes $z = Mx$. But its $M$ is dense: every output looks at every input, and every entry is its own parameter.

$$M = \begin{bmatrix} m_{11} & m_{12} & m_{13} & m_{14} & m_{15} \\ m_{21} & m_{22} & m_{23} & m_{24} & m_{25} \\ m_{31} & m_{32} & m_{33} & m_{34} & m_{35} \end{bmatrix}$$

From 5 inputs to 3 outputs, that is 15 numbers to learn. Our $T$ has the same shape, but only 3 distinct numbers. A convolution is a fully connected layer with two constraints:

• Locality: each output looks only at a small neighbourhood of the input. That is the band; everything outside it is zero.
• Weight sharing: every output uses the same weights. That is the repeated row.

Those two constraints are the whole trick, and they are exactly what perception needs: a pattern can be recognised from nearby values, and it means the same thing wherever it appears. They also save an enormous amount. A dense layer from a 1000 × 1000 image to an output of the same size would need $10^{12}$ weights; a 3 × 3 convolution has 9.

Why “convolution”? In signal processing, a convolution flips the filter before sliding it. Written out, the two operations differ only in the index on $w'$:

$$\text{cross-correlation: } z_i = \sum_{j=1}^{k} w'_j \, x_{i+j-1} \qquad \text{convolution: } z_i = \sum_{j=1}^{k} w'_{k+1-j} \, x_{i+j-1}$$

In the matrix, a convolution’s rows hold $w'$ backwards: $w'_3, w'_2, w'_1$. But in a CNN, the filter is learned. If a flipped filter is what the task needs, training simply finds it. Flipped or not, the layer can learn exactly the same things, so deep-learning libraries skip the flip and keep the familiar name. What machine learning calls a convolution is a cross-correlation, and nothing is lost by the mix-up.

Extending the idea to images

So far, $x$ has been a 1D signal. Our cat, though, is a grid. To handle images, we upgrade our vectors to matrices:

• The input ($x \rightarrow X$): instead of a runway of length $d$, the input is a 2D grid with a height ($H$) and width ($W$), so $X \in \mathbb{R}^{H \times W}$.
• The filter ($w' \rightarrow K$): the filter $K$ is now a 2D grid too. Filters are usually square, so we write its size as $F \times F$, and $K \in \mathbb{R}^{F \times F}$. (We use $F$ rather than $k$ for its size because $K$ now names the kernel itself.)

The sliding works exactly as before, just in two directions. The filter starts at the top-left corner and slides left to right across the width; when it hits the edge, it moves down by one stride and starts the next row from the left.

At each placement, we multiply the $F \times F$ filter element-wise with the $F \times F$ patch of the image it is resting on, and sum the results into a single scalar. It’s the same dot product as before: flatten both grids into vectors of length $F^2$ and you get exactly this sum. For a $3 \times 3$ patch and filter:

$$\text{Patch} = \begin{bmatrix} x_{11} & x_{12} & x_{13} \\ x_{21} & x_{22} & x_{23} \\ x_{31} & x_{32} & x_{33} \end{bmatrix}, \quad K = \begin{bmatrix} w_{11} & w_{12} & w_{13} \\ w_{21} & w_{22} & w_{23} \\ w_{31} & w_{32} & w_{33} \end{bmatrix}$$ $$z = (x_{11}w_{11}) + (x_{12}w_{12}) + \dots + (x_{33}w_{33}) = \sum_{i=1}^{F} \sum_{j=1}^{F} x_{ij} w_{ij}$$

Because sliding across the width is independent of sliding down the height, we don’t need a new size formula. We apply the 1D master formula twice, once per direction, with padding $P$ ($P$ zeros on each of the four sides) and stride $S$. These are the same $p$ and $s$ as before; capitals are the usual 2D notation.

$$H_{out} = \lfloor \frac{H - F + 2P}{S} \rfloor + 1 \qquad W_{out} = \lfloor \frac{W - F + 2P}{S} \rfloor + 1$$

The filter produces one scalar at every placement, so the output $A$, called a feature map, is a grid of its own: $A \in \mathbb{R}^{H_{out} \times W_{out}}$. Extending this to $n$ dimensions is just as easy: apply the same formula once per dimension.

The matrix view survives too. Flatten the image into one long vector, and a 2D convolution is again a single multiplication, by a matrix built from Toeplitz blocks arranged in a Toeplitz pattern, called a doubly block Toeplitz matrix. It is the same idea twice: shift along a row, then shift down the rows.

What does each output see?

Go back to the very first slide. $z_1$ was computed from $x_1$, $x_2$ and $x_3$, and nothing else. Change $x_5$ however you like, and $z_1$ won’t notice. In the matrix, this is the band: row 1 of $T$ is zero everywhere except over those three inputs. The patch of input that an output depends on is called its receptive field. After one convolution with a filter of size $k$, every output’s receptive field is exactly $k$ inputs wide. Neuroscientists use the same word for the retinal cells we met at the start, each responding to its own small patch of the retina.

That seems limiting. Our cat covers thousands of pixels, and a 3 × 3 filter sees nine of them. How can a network built from tiny windows ever recognise something big?

Here are some questions to sit with before Part 2:

1. Apply a second 3-wide convolution to $z$. One output of that second layer looks at three $z$‘s. How many $x$‘s does it depend on?
2. What happens to that number after ten layers? Does it grow by the same amount each time?
3. What if the first layer uses stride 2 instead?
4. Inside a receptive field, does every input count equally? Look back at the table in The trouble with edges: $x_3$ was touched three times, $x_1$ only once.

In Part 2, we’ll answer all four, and see how the receptive field is what lets a CNN go from edges to cats.