The Convolution Operation

Before the deep learning revolution, computer vision relied heavily on hand-crafted feature extractors—SIFT, SURF, HOG, and countless others designed by experts who spent years understanding what makes visual patterns recognizable. The breakthrough insight of Convolutional Neural Networks was replacing this manual feature engineering with learned features derived through a remarkably simple mathematical operation: convolution.

Convolution is not a machine learning invention. It has been central to signal processing, physics, and applied mathematics for over two centuries. What makes CNNs revolutionary is the realization that this classical operation, when composed in layers with learnable parameters, can hierarchically extract features of increasing abstraction—from edges and textures to object parts and entire semantic concepts.

In this page, we develop a rigorous understanding of discrete convolution from first principles. By the end, you will understand not just how to compute convolutions, but why this operation is so remarkably well-suited for spatial data processing.

To appreciate discrete convolution, we must first understand its continuous predecessor. The convolution operation was formalized in the 18th and 19th centuries through the work of mathematicians studying linear systems and differential equations.

The Continuous Convolution Integral:

For two continuous functions f(t) and g(t), their convolution (f * g)(t) is defined as:

$$(f * g)(t) = \int_{-\infty}^{\infty} f(\tau) \cdot g(t - \tau) , d\tau$$

This integral computes a weighted average of f, where the weights are given by g, centered and evaluated at each point t. The operation is commutative: (f * g) = (g * f), which can be seen by substituting u = t - τ.

Physical Interpretation:

In signal processing, convolution describes the output of a linear time-invariant (LTI) system. If f(t) represents an input signal and g(t) represents the system's impulse response (how the system responds to an instantaneous input), then (f * g)(t) gives the system's output.

Consider a simple example: an audio signal passing through a reverberant room. The room's impulse response g(t) describes how a short click would echo and decay. The convolution of any audio f(t) with this impulse response produces the 'reverb' effect—the mathematical model of physical acoustics.

The Transition to Discrete:

In digital computing, we work with sampled signals—discrete sequences of values rather than continuous functions. Images are 2D grids of pixel intensities, not continuous intensity fields. Audio is stored as sequences of amplitude samples, not continuous waveforms.

This necessitates the discrete convolution, which replaces the integral with a summation and works over discrete indices rather than continuous domains. The transition from continuous to discrete is not merely technical—it introduces important computational considerations while preserving the essential mathematical properties that make convolution useful.

1D Discrete Convolution:

For two discrete sequences f[n] and g[n], their convolution (f * g)[n] is defined as:

$$(f * g)[n] = \sum_{k=-\infty}^{\infty} f[k] \cdot g[n - k]$$

In practice, our sequences are finite (say, f has length N and g has length M), so the summation is bounded:

$$(f * g)[n] = \sum_{k=0}^{M-1} f[n - k] \cdot g[k]$$

where we assume f[i] = 0 for i < 0 or i ≥ N (zero-padding beyond boundaries).

Kernel/Filter Terminology:

In CNN contexts, one sequence is typically called the input (or signal), and the other is called the kernel (or filter). The kernel is usually much smaller than the input:

• Input f: length N (e.g., 1000 samples, or a 224×224 image)
• Kernel g: length K (e.g., 3 samples, or a 3×3 filter)

The output of the convolution has length that depends on boundary handling (more on this when we discuss padding).

2D Discrete Convolution:

For images (2D arrays), convolution extends naturally. For a 2D input I[m, n] (image with height H, width W) and a 2D kernel K[i, j] (with height Kh, width Kw):

$$(I * K)[m, n] = \sum_{i=0}^{K_h-1} \sum_{j=0}^{K_w-1} I[m - i, n - j] \cdot K[i, j]$$

Or equivalently, with the kernel flipped:

$$(I * K)[m, n] = \sum_{i=0}^{K_h-1} \sum_{j=0}^{K_w-1} I[m + i - K_h + 1, n + j - K_w + 1] \cdot K[K_h - 1 - i, K_w - 1 - j]$$

The second formulation makes explicit that we flip the kernel both horizontally and vertically before sliding it across the image.

The most intuitive way to understand convolution is through the 'flip and slide' (or 'flip and drag') interpretation. This procedural view makes the computation clear:

Step-by-Step Process:

1. Flip the kernel (reverse its order in 1D; rotate 180° in 2D)
2. Slide the flipped kernel across the input, position by position
3. At each position, compute the dot product (element-wise multiplication and sum)
4. The result at each position forms one element of the output

Visual Example (1D):

Consider input f = [1, 2, 3, 4, 5] and kernel g = [a, b, c].

• Flip kernel: g' = [c, b, a]
• At position 0: place g' starting at the leftmost, compute overlap
• At position 1: slide g' one step right, compute overlap
• Continue until g' has slid completely across f

This sliding window interpretation directly translates to the summation in the formal definition.

The Extended Output:

Notice that convolving an input of length N with a kernel of length K produces an output of length N + K - 1 in the 'full' mode. The extra positions correspond to partial overlaps at the boundaries.

Why 'Flip' Matters (Mathematically):

The flip ensures associativity of convolution:

$$f * (g * h) = (f * g) * h$$

This property is crucial in signal processing and CNNs, where we cascade multiple convolutional operations. Without the flip, this associativity breaks, and the order of operations would matter in ways that complicate both theory and implementation.

Another consequence of the flip is commutativity:

$$f * g = g * f$$

Either sequence can be considered the 'input' or the 'kernel'—the result is identical. This symmetry is elegant but can cause confusion when reading literature, as authors may place the kernel first or second depending on convention.

Convolution possesses several remarkable mathematical properties that explain its prevalence in signal processing and, by extension, deep learning. Understanding these properties provides insight into why convolution is the natural operation for spatial data.

1. Commutativity: $$f * g = g * f$$

The order of operands doesn't matter. In CNNs, we conventionally write the input first and kernel second (I * K), but mathematically, the result is symmetric.

2. Associativity: $$f * (g * h) = (f * g) * h$$

Multiple convolutions can be grouped in any order. This property is essential for analyzing stacked convolutional layers. Two consecutive convolutions with kernels K₁ and K₂ can theoretically be replaced by a single convolution with kernel K₁ * K₂.

3. Distributivity over Addition: $$f * (g + h) = (f * g) + (f * h)$$

Convolution distributes over sum. This property underlies certain decomposition techniques and analysis methods.

4. Linearity: $$f * (\alpha g) = \alpha (f * g)$$

Scalar multiplication factors out. Combined with distributivity, this makes convolution a linear operation.

5. The Convolution Theorem:

Perhaps the most powerful property of convolution relates it to the Fourier transform:

$$\mathcal{F}{f * g} = \mathcal{F}{f} \cdot \mathcal{F}{g}$$

Convolution in the spatial (or time) domain equals pointwise multiplication in the frequency domain.

This theorem has profound implications:

• It explains why convolution acts as a frequency filter. Kernel elements determine which frequency components are amplified or attenuated.
• It provides a fast computation method. Instead of O(N·K) direct convolution, compute via FFT in O(N log N) time.
• It offers analytical insight. Analyzing a kernel's frequency response reveals what patterns it detects.

For example, the averaging kernel [1/3, 1/3, 1/3] acts as a low-pass filter, attenuating high-frequency components (sharp edges) and preserving low-frequency components (gradual variations). The edge-detection kernel [1, -2, 1] acts as a high-pass filter, doing the opposite.

Beyond the mathematical properties, convolution has a deeply intuitive interpretation that explains its success in visual pattern recognition: template matching.

The Core Idea:

When we slide a kernel across an image, the dot product at each position measures similarity between the kernel pattern and the local image patch. A high output indicates the patch strongly resembles the kernel; a low (or negative) output indicates mismatch or anti-correlation.

Example: Edge Detection

Consider the classic Sobel edge-detection kernel:

$$K_x = \begin{bmatrix} -1 & 0 & +1 \ -2 & 0 & +2 \ -1 & 0 & +1 \end{bmatrix}$$

This kernel computes a weighted difference between right and left pixels. Where the image has a vertical edge (bright on right, dark on left), the kernel output is large positive. Where the image has the opposite edge, output is large negative. Where the image is uniform, output is near zero.

The kernel is a template for vertical edge patterns. Convolution 'matches' this template across every image location, producing an edge response map.

From Hand-Crafted to Learned Templates:

Classical computer vision carefully designed kernels for specific tasks:

• Sobel/Prewitt kernels for edges
• Gaussian kernels for blurring
• Laplacian kernels for blob detection
• Gabor filters for texture analysis

The insight of CNNs is that instead of hand-designing these templates, we learn them from data. Each kernel's weights become trainable parameters optimized via backpropagation. The network discovers what templates are useful for the task at hand—be it classification, segmentation, or generation.

Hierarchical Feature Learning:

In a deep CNN:

• Early layers learn simple templates (edges, color contrasts, simple textures)
• Middle layers combine these into more complex patterns (corners, junctions, object parts)
• Later layers compose these into high-level concepts (eyes, wheels, written characters)

This hierarchy emerges automatically when we stack convolutional layers—each layer's templates are built from the previous layer's feature responses.

When the kernel slides to positions near the input boundaries, parts of the kernel extend beyond the input's extent. How we handle these boundary cases affects both the output size and the values computed at edges.

Modes of Convolution:

For an input of size N and kernel of size K:

1. Full Mode: Compute outputs at all positions where any overlap exists.

   • Output size: N + K - 1
   • Includes positions where the kernel only partially overlaps the input
   • Requires defining 'virtual' values outside the input (typically zeros)

2. Same Mode: Produce output of the same size as the input.

   • Output size: N
   • Kernel is centered on each input position
   • Requires (K - 1)/2 padding on each side for odd K

3. Valid Mode: Only compute where the kernel fully overlaps the input.

   • Output size: N - K + 1
   • No padding needed
   • All output values computed from 'real' input data only

Padding Options:

When padding is required (full or same mode), we must choose what values to use for the 'virtual' positions outside the input:

• Zero Padding: Pad with zeros. Simple and efficient. Most common in CNNs.
• Replicate/Edge Padding: Extend edge values. Reduces edge artifacts. Common in image processing.
• Reflect/Mirror Padding: Reflect the signal at boundaries. Smooth extrapolation.
• Circular/Wrap Padding: Treat signal as periodic. Used for signals with inherent periodicity.

In Deep Learning:

CNNs predominantly use zero padding with 'same' mode. This choice:

• Preserves spatial resolution across layers (important for architectures like ResNet)
• Treats boundaries consistently and simply
• Introduces minor edge artifacts, but these are trained around

Understanding the computational cost of convolution is essential for designing efficient neural networks and choosing appropriate kernel sizes.

Direct Convolution Complexity:

1D Convolution:

• Input length: N
• Kernel length: K
• Operations: O(N × K) multiplications and additions

2D Convolution:

• Input dimensions: H × W
• Kernel dimensions: Kₕ × Kw
• Operations: O(H × W × Kₕ × Kw)

Multichannel Convolution (as used in CNNs):

• Input: H × W × Cᵢₙ (height × width × input channels)
• Kernels: Kₕ × Kw × Cᵢₙ × Cₒᵤₜ (one 3D kernel per output channel)
• Operations: O(H × W × Kₕ × Kw × Cᵢₙ × Cₒᵤₜ)

For a typical CNN layer with H=W=224, K=3, Cᵢₙ=Cₒᵤₜ=64:

• Operations ≈ 224 × 224 × 3 × 3 × 64 × 64 ≈ 1.85 billion operations

This is just one layer! Deep CNNs have dozens of such layers.

Memory Considerations:

Beyond compute, memory bandwidth often limits convolution performance:

• Input reuse: Each input element is used in multiple output computations. Caching strategies are critical.
• Kernel reuse: The same kernel applies across all spatial positions. Kernels are typically small enough to fit in cache.
• im2col memory expansion: This optimization trades memory for compute efficiency. The expanded matrix can be 9× larger than the input for 3×3 kernels.

Hardware Trends:

Modern accelerators (GPUs, TPUs) are designed with convolution in mind:

• Tensor Cores (NVIDIA Volta and later) provide hardware-accelerated matrix operations
• TPU's MXU (Matrix Multiply Unit) is optimized for the im2col formulation
• Custom ASICs achieve even higher efficiency by exploiting convolution structure

We've developed a comprehensive understanding of discrete convolution—the operation that makes Convolutional Neural Networks possible. Let's consolidate the key insights:

What's Next:

In the next page, we examine cross-correlation—the operation that deep learning frameworks actually implement when they say 'convolution'. We'll clarify the distinction between true mathematical convolution (with the kernel flip) and cross-correlation (without), and explain why this difference typically doesn't matter for neural networks.