Convolution is a foundational operation in deep learning—especially in computer vision—where it enables hierarchical feature extraction through localized, parameter-shared transformations. Unlike general matrix multiplication, convolution exploits spatial locality and translation invariance, making it both computationally efficient and semantically meaningful for grid-structured data like images.

The Mathematical Foundation

In mathematics, convolution is an integral (or sum, in discrete settings) that expresses how the shape of one function modifies another. For continuous real-valued functions f and g, their convolution is defined as:

( f * g ) ( t ) = ∫ −∞ ∞ f ( τ ) g ( t − τ ) d τ This formulation captures the idea of "sliding" g across f, flipping g horizontally (due to t − τ), computing pointwise products, and integrating over overlap. In practice, digital systems use the discrete version:

( f * g ) [ n ] = ∑ m = − ∞ ∞ f [ m ] g [ n − m ] For finite sequences—such as pixel arrays—the summation bounds become explicit, and convolution reduces to a sliding dot product between input patches and a learnable kernel.

Interpretation Through Signal Response

A concrete intuition arises from linear time-invariant (LTI) systems. Suppose f[n] is an input signal (e.g., sensor readings), and g[n] models how the system responds to an impulse at time zero. Then the output h[n] = (f * g)[n] represents the cumulative effect of all past inputs, each weighted by its corresponding delayed response:

h [ n ] = ∑ k = 0 n f [ k ] g [ n − k ] This mirrors how CNNs interpret filters: each kernel encodes a pattern detector; its activation at position (i,j) reflects how well that local region matches the learned template.

Key Operational Parameters in CNNs

Modern convolution layers extend the basic operation with configurable parameters:

• Stride (s): Controls step size during kernel traversal. Larger strides reduce output resolution and computational load.
• Padding (p): Adds zero-valued border pixels. Common modes include:
  • Valid: No padding → output size = ⌊(H − K + 1)/s⌋ × ⌊(W − K + 1)/s⌋
  • Same: Padding chosen so output spatial dimensions match input (requires p = ⌊(K − 1)/2⌋ for odd K)
• Input/Output Channels (Cin, Cout): Each output channel results from applying Cin independent kernels (one per input channel) and summing across depth.
• Kernel Size (K × K): Defines receptive field extent. Smaller kernels encourage deeper stacking for equivalent global context.

Memory Layout and Tensor Computation

Efficient implementation depends on memory layout conventions:

• NCHW: Batch, Channel, Height, Width — preferred in PyTorch for cache-friendly channel-wise access.
• NHWC: Batch, Height, Width, Channel — common in TensorFlow and accelerators due to spatial locality.

A naive NHWC-based 2D convolution (ignoring batch dimension) can be expressed as:

for (int oh = 0; oh < OH; ++oh) {
  for (int ow = 0; ow < OW; ++ow) {
    for (int oc = 0; oc < OC; ++oc) {
      float sum = 0.0f;
      for (int kh = 0; kh < KH; ++kh) {
        for (int kw = 0; kw < KW; ++kw) {
          for (int ic = 0; ic < IC; ++ic) {
            sum += input[(oh * s + kh) * W * IC + (ow * s + kw) * IC + ic] *
                   kernel[kh * KW * IC + kw * IC + ic];
          }
        }
      }
      output[oh * OW * OC + ow * OC + oc] = sum + bias[oc];
    }
  }
}

This six-level loop nest reveals opportunities for optimization: loop reordering (to improve cache reuse), vectorization (SIMD instructions), tiling, and fusion with activation functions.

Computational Complexity

Let H, W be input spatial dimensions, Cin, Cout input/output channels, K kernel side length, and s stride. The number of multiply-add operations per layer is approximately:

O ( H W K 2 C in C out s 2 ) Space complexity includes trainable weights (K² × Cin × Cout) and intermediate feature maps (H × W × Cout). Techniques like depthwise separable convolutions or Winograd transforms aim to reduce this cost without sacrificing representational power.

Practical Implementation Example

Below is a minimal NumPy-based convolution function supporting padding and stride:

import numpy as np

def conv2d(input_tensor, kernel, stride=1, padding='same'):
    N, H_in, W_in, C_in = input_tensor.shape
    K_h, K_w, _, C_out = kernel.shape
    
    # Compute padding
    if padding == 'same':
        p_h = (K_h - 1) // 2
        p_w = (K_w - 1) // 2
        pad_width = ((0, 0), (p_h, p_h), (p_w, p_w), (0, 0))
    else:
        pad_width = ((0, 0), (0, 0), (0, 0), (0, 0))
    
    padded = np.pad(input_tensor, pad_width, mode='constant')
    H_out = (padded.shape[1] - K_h) // stride + 1
    W_out = (padded.shape[2] - K_w) // stride + 1
    
    output = np.zeros((N, H_out, W_out, C_out))
    
    for n in range(N):
        for h in range(H_out):
            for w in range(W_out):
                for c_out in range(C_out):
                    region = padded[n,
                                   h*stride:h*stride+K_h,
                                   w*stride:w*stride+K_w,
                                   :]
                    output[n, h, w, c_out] = np.sum(region * kernel[..., c_out])
    
    return output

Note: This implementation prioritizes clarity over performance—production frameworks use highly optimized kernels (e.g., cuDNN, oneDNN) leveraging hardware-specific acceleration and memory hierarchies.