The Convolution Operation

Table of Contents

1. Learning Objectives
2. Notation
3. Core Intuition
4. 1D Discrete Convolution
5. 2D Convolution for Images
6. Convolution as Matrix Multiplication
7. Translation Equivariance
8. Stride and Padding
9. Multi-Channel Convolutions
10. Receptive Field Analysis
11. Backpropagation Through Convolution
12. Common Pitfalls
13. Summary
14. Exercises

Learning Objectives

1. Define discrete convolution and cross-correlation; explain the distinction.
2. Express 2D convolution as a matrix-vector product using doubly-block Toeplitz matrices.
3. Prove translation equivariance of the convolution operator.
4. Derive output dimensions for given kernel size, stride, and padding.
5. Compute the receptive field of deep convolutional architectures.
6. Derive the gradient of the loss with respect to convolution weights (backprop through conv).

Notation

• $x[n]$ — 1D input signal
• $w[k]$ — kernel (filter) of size $K$
• $(x * w)[n]$ — convolution output
• $\mathbf{X} \in \mathbb{R}^{H \times W}$ — 2D input (single channel)
• $\mathbf{W} \in \mathbb{R}^{K_H \times K_W}$ — 2D kernel
• $s$ — stride, $p$ — padding
• $C_{\text{in}}, C_{\text{out}}$ — input/output channels

Core Intuition

Convolution is a linear operation that slides a small "template" (kernel) over the input, computing a weighted sum at each position. It encodes two inductive biases: locality (each output depends on a small input region) and weight sharing (the same kernel is applied everywhere). These biases make CNNs extremely parameter-efficient for spatial data.

1D Discrete Convolution

Definition (Cross-Correlation). In deep learning, "convolution" is technically cross-correlation:

True convolution flips the kernel: $(x \star w)[n] = \sum_k w[k] \cdot x[n - k]$. Since kernels are learned, the flip is immaterial — both learn the same filters.

Output size for input length $N$, kernel size $K$, no padding:

2D Convolution for Images

For input $\mathbf{X} \in \mathbb{R}^{H \times W}$ and kernel $\mathbf{W} \in \mathbb{R}^{K_H \times K_W}$:

Output dimensions:

Convolution as Matrix Multiplication

The convolution in (1) is a linear operation and can be written as $\mathbf{y} = \mathbf{T}\mathbf{x}$ where $\mathbf{T}$ is a Toeplitz matrix:

Each row is a shifted copy of the kernel weights. For 2D: the matrix is doubly-block Toeplitz. This viewpoint makes it clear that convolution is a special case of matrix multiplication with structured weight sharing.

Parameter count: A fully-connected layer mapping $HW \to H'W'$ needs $HWH'W'$ parameters. A convolutional layer needs only $K_H \cdot K_W$ (per channel pair) — a massive reduction.

Translation Equivariance

Definition. An operator $T$ is equivariant to translation $\tau$ if: $T[\tau_\delta(x)] = \tau_\delta[T(x)]$.

Theorem. Convolution is translation equivariant.

Proof. Let $\tau_\delta(x)[n] = x[n - \delta]$. Then:

Shifting the input shifts the output by the same amount. $\blacksquare$

Implication: A feature detected at one spatial location will be detected identically at any other location, without needing to learn separate detectors.

Stride and Padding

Stride $s$: Sample the output every $s$ positions:

Output size: $N_{\text{out}} = \lfloor(N - K)/s\rfloor + 1$.

Padding $p$: Append $p$ zeros to each side of the input. With padding:

"Same" padding: Choose $p$ such that $N_{\text{out}} = \lceil N/s\rceil$. For $s=1$: $p = (K-1)/2$.

Multi-Channel Convolutions

Input: $\mathbf{X} \in \mathbb{R}^{C_{\text{in}} \times H \times W}$. Kernel: $\mathbf{W} \in \mathbb{R}^{C_{\text{out}} \times C_{\text{in}} \times K_H \times K_W}$.

Each output channel uses a different $C_{\text{in}} \times K_H \times K_W$ kernel. Total parameters: $C_{\text{out}} \cdot C_{\text{in}} \cdot K_H \cdot K_W + C_{\text{out}}$.

Receptive Field Analysis

The receptive field of a neuron at layer $l$ is the input region that can influence its value.

For a stack of $L$ convolutional layers with kernel size $K$ and stride 1:

With stride $s$ at each layer:

Larger receptive fields capture more global context. Deeper networks or dilated convolutions increase RF without increasing parameters.

Backpropagation Through Convolution

Given $\partial\mathcal{L}/\partial\mathbf{Y}$ (gradient w.r.t. output), we need:

Gradient w.r.t. weights:

This is itself a convolution of the input with the output gradient.

Gradient w.r.t. input:

This is a full convolution (with padding) of the output gradient with the flipped kernel — the "transposed convolution."

Common Pitfalls

Pitfall 1. Confusing convolution with cross-correlation. In practice, all deep learning frameworks implement cross-correlation but call it "convolution."

Pitfall 2. Forgetting that pooling breaks strict equivariance. Max-pooling with stride 2 introduces approximate (not exact) translation invariance.

Pitfall 3. Not accounting for receptive field limitations. If the RF is smaller than the relevant structure in the data, the network cannot capture it.

Summary

• Convolution slides a learned kernel over input, computing local weighted sums.
• Encodes locality and weight sharing — reducing parameters by orders of magnitude.
• Translation equivariant: detecting a feature anywhere requires only one kernel.
• Expressible as Toeplitz matrix multiplication.
• Backprop through conv = convolution with flipped kernel.
• Receptive field grows linearly with depth (or faster with stride/dilation).

Exercises

Exercise 1. Compute the output of a 1D convolution with input $[1, 2, 3, 4, 5]$ and kernel $[1, -1]$.

Exercise 2. Derive the output dimensions for a 2D convolution with $H=32, W=32, K=5, s=2, p=2$.

Exercise 3. Construct the Toeplitz matrix for a 1D kernel $[w_0, w_1, w_2]$ applied to a length-5 input.

Exercise 4. Prove that the composition of two convolutions (without nonlinearity) is equivalent to a single convolution with a larger kernel.

Exercise 5. Compute the receptive field of a VGG-style network with 5 layers of $3 \times 3$ kernels and stride 1.