Convolution as matrix multiplication (im2col)

Convolution lowering puts each receptive field in a matrix column so flattened filters can score all output positions together.

Summary

How do four overlapping patches become the four output values, and what must be stored? Use the input rows $[1, 2, 3]$ , $[4, 5, 6]$ , $[7, 8, 9]$ . The filter is $[[1, 0], [0, - 1]]$ , with stride one, no padding and no bias. Use deep-learning cross-correlation: do not flip the filter.

The mechanism

Flatten channel, kernel-row and kernel-column in that order; visit output positions row by row.

Output location	Patch column	Dot product with $[1, 0, 0, - 1]$
Top-left	$[1, 2, 4, 5]$	$1 - 5 = - 4$
Top-right	$[2, 3, 5, 6]$	$2 - 6 = - 4$
Bottom-left	$[4, 5, 7, 8]$	$4 - 8 = - 4$
Bottom-right	$[5, 6, 8, 9]$	$5 - 9 = - 4$

The four column scores reshape to a two-by-two output; no input reconstruction happens during that reshape. The patch matrix stores sixteen values from nine source values, ratio $16/9$ .

Learning objective

Each local patch becomes one column in the matrix product

Derivation

each patch becomes one column in output order. The center value 5 occurs in all four columns. Filter scores become four negative fours; forward only reshapes them. Explicit lowering stores the repeats. Original example checked against PyTorch Unfold and NVIDIA's convolution guide.

Check: Which input values produce the top-right output? Where do they appear in X_col?

Read it this way: Two adjacent 2x2 patches become these columns. Input rows are (1,2,3) and (4,5,6); shared pixels appear in both patches.
Why do the middle image pixels appear in both output columns?

For one image with $C_{in}$ channels, let $D = C_{in} k_{H} k_{W}$ and $P = H_{o u t} W_{o u t}$ . Unfold gives $U$ of shape $D \times P$ ; flattened filters $F$ have shape $C_{o u t} \times D$ . Compute $F U$ plus per-output-channel bias, then reshape to $C_{o u t} \times H_{o u t} \times W_{o u t}$ . For batch size $B$ , explicit columns store $B D P$ entries.

Dense work is $B C_{o u t} D P$ multiply-accumulates, or approximately twice that many FLOPs under the two-FLOP convention. The tiny example uses sixteen MACs even though its particular filter contains zeros. Materialized storage and whole-operator memory traffic are different quantities.

Change storage or channel structure

Avoid full materialization

New task: preserve these outputs without storing every patch simultaneously.

Picture and change: process one four-value column at a time and emit its score.

Check: patch scratch falls from sixteen to four scalar values here, while all four outputs remain minus four. Input, output and filter storage remain; repeated reads and indexing still cost work.

Use when: unfold storage or traffic is binding; benchmark an appropriate implicit/tiled kernel under the same operator.

Separate depthwise and pointwise work

New task: apply per-channel spatial filters, then mix channels.

Picture and change: take two input channels, four output positions and two-by-two depthwise filters. Depthwise work is $2 \cdot 4 \cdot 4 = 32$ MACs. Mixing those channels into three outputs with a pointwise filter adds $3 \cdot 2 \cdot 4 = 24$ MACs.

Check: total work is 56 MACs versus 96 for a dense two-by-two convolution with three output channels. These are different parameterizations, not generally interchangeable learned functions.

Use when: the architecture explicitly separates spatial filtering and channel mixing.

Reconstruct backward accumulation

Why is folding patches not an inverse reshape?

Reasoned answer

Overlapping columns contribute to the same input coordinate, so backward sums their contributions. Folding ones gives center coverage four in this example. Actual input gradients also include filter coefficients; with this filter and unit output gradients, the center derivative is zero.

Variants

For each axis, output length is $⌊(H + 2 p - d (k - 1) - 1) / s ⌋ + 1$ for valid parameters. Here $p$ is symmetric padding, $d$ dilation and $s$ stride; apply the formula independently to height and width. Groups restrict each filter to $C_{in} / g$ input channels, changing the MAC count accordingly. Depthwise is a grouped case; pointwise performs dense channel mixing at each location.

Implicit GEMM indexes virtual patch tiles instead of storing the complete unfold. Direct kernels, Winograd and FFT implementations use different layouts or transforms. FFT requires the correct padding/correlation convention; Winograd changes numerical behavior. Shape, hardware, precision and workspace determine useful choices, not a universal framework implementation rule.

Interview focus

Derive complete input, filter, column and output shapes, then state flatten order, bias and resource convention. Algebraic lowering is not evidence that the actual kernel allocated the patch matrix.

Common pitfalls

Flipping the example’s filter changes all outputs to positive four; convolution versus cross-correlation can matter. Explicit storage expansion depends on shape, stride, padding and dilation, not a constant nine-fold multiplier. Forward output reshape and backward overlap-add solve different tasks. Profile depthwise/pointwise work and their fusion boundary separately.

CNN architecture.
FlashAttention. Same idea: rearrange for hardware.