The Convolution Operation

A convolution in deep learning is an operation that takes an input tensor (e.g., an image) and a small learnable tensor called a kernel or filter, and produces an output tensor by sliding the kernel across the input and computing a dot product at each position. Formally, for a 2D single-channel input $I$ and kernel $K$ of size $k_h \times k_w$, the output at position $(i, j)$ is

This is precisely cross-correlation, not mathematical convolution. True convolution, as defined in signal processing, flips the kernel before sliding:

Because the kernel weights are learned rather than hand-designed, flipping makes no practical difference — a learned flipped kernel is just as good as a learned unflipped one, and the network cannot tell the difference during training. Nearly every deep learning framework implements cross-correlation and calls it "convolution"; this article follows that convention but flags the distinction because it matters when porting classical signal-processing kernels (e.g., a hand-designed edge detector) into a network. Three hyperparameters govern the geometry of the sliding window:

• Kernel size $k$ — the spatial extent of the filter (e.g., 3×3, 5×5). Larger kernels see more context per step but cost more computation and parameters.
• Stride $s$ — how many positions the kernel moves between computations. Stride 1 visits every position; stride 2 skips every other one, halving each spatial dimension.
• Padding $p$ — how many border pixels (typically zeros) are added around the input before sliding, used to control whether the output shrinks, stays the same size ("same" padding), or shrinks freely ("valid" padding).

A real convolutional layer typically has multiple input channels (e.g., R, G, B) and multiple output channels (each its own learned filter bank), which we develop below. The key structural fact that distinguishes convolution from a dense layer is weight sharing: the same $k \times k$ set of weights is reused at every spatial location, rather than learning an independent weight for every (input pixel, output pixel) pair.

Step 1 — Choose geometry. Fix input size $H \times W$, kernel size $k_h \times k_w$, stride $s$, and padding $p$ (assume symmetric padding on all sides for simplicity).

Step 2 — Pad the input. Create a padded input of size $(H + 2p) \times (W + 2p)$ by surrounding the original with $p$ rows/columns of zeros (zero-padding is standard; reflection and replication padding are used for specialized cases).

Step 3 — Slide and dot-product. Position the kernel at the top-left corner of the padded input. At each valid position, compute the elementwise product of the kernel and the overlapping input patch, sum the results into a single scalar, and write it to the output. Move the kernel by `stride` positions horizontally; when the row is exhausted, reset horizontally and move down by `stride` vertically.

Step 4 — Repeat across channels. For multi-channel input (depth $C_{in}$), the kernel itself has depth $C_{in}$; the dot product sums over height, width, and channel simultaneously, producing a single 2D output map per filter. Using $C_{out}$ independently learned filters produces $C_{out}$ output channels, stacked into a 3D output tensor.

Step 5 — Add bias and apply nonlinearity. Each output channel typically has one shared bias added to every spatial position, followed by an activation function (ReLU, etc.), exactly as in a standard feedforward layer. ``` function CONV2D(Input, Kernel, stride, padding):

# Input: H x W x C_in tensor

# Kernel: k_h x k_w x C_in x C_out tensor (C_out filters, each C_in-deep)

# stride: integer step size

# padding: integer border width (zero-padded) PaddedInput = ZERO_PAD(Input, padding) # (H+2p) x (W+2p) x C_in H_pad, W_pad, C_in = shape(PaddedInput) k_h, k_w, _, C_out = shape(Kernel) H_out = floor((H_pad - k_h) / stride) + 1 W_out = floor((W_pad - k_w) / stride) + 1 Output = new tensor of shape H_out x W_out x C_out, filled with 0 for f in 1 .. C_out: # each output filter for i in 0 .. H_out - 1: # output row for j in 0 .. W_out - 1: # output column row_start = i stride col_start = j stride acc = 0 for m in 0 .. k_h - 1: for n in 0 .. k_w - 1: for c in 0 .. C_in - 1: acc += PaddedInput[row_start + m, col_start + n, c]

• Kernel[m, n, c, f]

Output[i, j, f] = acc + Bias[f] return Output ``` The four nested loops over `(m, n, c)` compute exactly the dot product from the definition of $S(i,j)$ above; the two outer loops over `(i, j)` implement the sliding window; the loop over `f` implements multiple output channels. In practice this quadruple loop is never executed naively — it is reformulated as a single large matrix multiplication (the "im2col" trick: unroll every patch into a row of a matrix, then multiply by the flattened kernel matrix) to exploit highly optimized BLAS/GPU kernels, but the semantics are identical to the pseudocode above.

Time complexity. For a single output channel, the algorithm visits $H_{out} \times W_{out}$ output positions, and at each position performs $k_h \times k_w \times C_{in}$ multiply-adds. With $C_{out}$ output filters, total work is

This is honest as-is: it is the exact operation count of the naive sliding-window algorithm, matching the four nested loops in the pseudocode with no hidden shortcuts. Compare this to a fully connected layer mapping the same input ($H\cdot W \cdot C_{in}$ values) to the same output size ($H_{out}\cdot W_{out}\cdot C_{out}$ values): a dense layer costs $O(H\cdot W\cdot C_{in}\cdot H_{out}\cdot W_{out}\cdot C_{out})$ — every input connects to every output. Convolution replaces the two full spatial factors $H\cdot W$ with just $k_h \cdot k_w$, which is normally a tiny constant (3×3, 5×5, 7×7) compared to typical image dimensions (224×224). This is the entire efficiency argument in one line: locality shrinks the receptive field per output unit from "the whole image" to "a small window," and weight sharing means that shrinkage doesn't cost accuracy for the many vision tasks where patterns are local and translation-invariant.

Space complexity. The kernel itself stores $k_h \cdot k_w \cdot C_{in} \cdot C_{out}$ parameters, independent of input spatial size $H, W$ — this is the crucial parameter-count win over dense layers, whose weight count scales with $H\cdot W$. The output tensor requires $O(H_{out}\cdot W_{out}\cdot C_{out})$ space, and the padded input requires $O((H+2p)(W+2p)C_{in})$ space; both are unavoidable since the algorithm must materialize its output and (if padding is used) a padded copy of the input (or equivalent boundary-checking logic, which trades a little time for saving this space).

Output-size formula (correctness of the shape bookkeeping). With input size $H$, padding $p$ on each side, kernel size $k$, and stride $s$:

Justification: after padding, the input has $H + 2p$ positions along that axis. The kernel's top edge can range over any starting index $i$ such that the kernel (spanning $k$ cells) still fits: $i + k - 1 \le H + 2p - 1$, i.e. $i \le H + 2p - k$. Valid starting indices under stride $s$ are $0, s, 2s, \dots$, and the count of such indices in $[0, H+2p-k]$ is $\lfloor (H+2p-k)/s \rfloor + 1$. The same formula applies independently to the width axis.

Correctness of the sliding-window semantics. The claim to verify is that the pseudocode's `Output[i,j,f]` equals the mathematical definition $S_f(i,j) = \sum_{m,n,c} I_{pad}(i s + m,\, j s + n,\, c)\, K(m,n,c,f) + b_f$. This holds by direct correspondence: the loop sets `row_start = istride`, `col_start = jstride`, then accumulates exactly the terms $I_{pad}(row\_start+m,\ col\_start+n,\ c)\cdot K(m,n,c,f)$ for all valid $(m,n,c)$ — which is precisely the sum in the definition. The loop bounds `H_out, W_out` are derived directly from the formula above, guaranteeing every kernel placement stays within the padded input (no out-of-bounds access) and no valid placement is skipped (every $i$ from $0$ to $H_{out}-1$ corresponds to a distinct valid `row_start`). Hence the algorithm computes exactly the defined operation — an exhaustive, not approximate, computation.

Translation equivariance (why weight sharing is mathematically sound). If the input is shifted by $(\Delta i, \Delta j)$ (ignoring boundary effects), the output shifts by the same amount: $S(i + \Delta i, j + \Delta j)$ computed on shifted input equals $S(i,j)$ on the original, because the kernel weights $K(m,n,c,f)$ do not depend on position $(i,j)$ — they are the same numbers reused at every location. This is precisely what makes a filter trained to detect, say, a vertical edge near the top of an image equally useful for detecting a vertical edge near the bottom, without needing separate parameters for each location.

Tradeoffs, stated honestly. Convolution's efficiency comes at the cost of an inductive bias: it assumes local, translation-invariant structure is useful, which is excellent for natural images but can be a mismatch for data with no meaningful spatial locality (e.g., arbitrarily permuted tabular features). Large kernels or many layers are still needed to grow the receptive field to see global structure, which is why deep stacks of small convolutions (rather than one huge kernel) became the standard design.

Take a single-channel $5 \times 5$ input, padding $p = 0$, stride $s = 2$, and a $3\times3$ kernel — a genuinely asymmetric example (no symmetric trick hides an arithmetic slip). Input $I$:

Output size: $H_{out} = \lfloor (5 + 0 - 3)/2 \rfloor + 1 = \lfloor 1 \rfloor + 1 = 2$. So the output is $2\times2$. Valid starting rows/cols under stride 2 are $\{0, 2\}$ (since $H + 2p - k = 2$, indices $0$ and $2$ fit; index $4$ would need the kernel to reach row 6, out of bounds).

Position (0,0) — patch = rows 0–2, cols 0–2:

Position (0,1) — patch = rows 0–2, cols 2–4:

Position (1,0) — patch = rows 2–4, cols 0–2:

Position (1,1) — patch = rows 2–4, cols 2–4:

Final output:

This traces exactly one full forward pass: notice stride 2 means the patches at row 0–2 and row 2–4 do not overlap in the row dimension but do overlap in column selection with each other's neighbors, a subtlety stride-1 examples never expose. If instead you used padding $p=1$, the formula gives $H_{out} = \lfloor(5+2-3)/2\rfloor+1 = 2 + 1= 3$ (recomputing with the zero border), producing a $3\times 3$ output — a good self-check exercise.

The convolution operation as used in neural networks descends from a lineage joining signal processing, neuroscience-inspired vision models, and gradient-based learning. Its neural-network incarnation is most closely associated with Yann LeCun, who combined convolutional weight sharing with backpropagation to build practical, trainable vision systems.

Convolution is the computational backbone of image classification, object detection, semantic segmentation, and medical image analysis systems, from mobile phone camera pipelines to radiology screening tools. It underlies speech and audio models that treat spectrograms as images, and 1D convolutions are widely used for time-series and genomic sequence analysis. Modern hardware — GPUs, TPUs, and dedicated convolution accelerators — is co-designed around the im2col/matrix-multiply reformulation of exactly the sliding-window operation described here, because convolution's regular, data-parallel structure maps efficiently onto massively parallel compute. Frameworks like PyTorch, TensorFlow, and JAX expose highly tuned convolution primitives (via libraries such as cuDNN) that implement precisely the mathematics developed in this article, layered underneath the higher-level abstractions of Convolutional Layers and Parameter Sharing and followed downstream by Pooling Operations for spatial downsampling.

Ask the tutor: How does stacking multiple convolutional layers grow the network's effective receptive field, and how is that related to the design choices behind ResNet and other deep architectures?