Convolution as matrix multiplication

Important

Discrete convolution can be viewed as multiplication by a matrix, but the matrix has several entries constrained to be equal to other entries.

For example, for univariate ($1D$) discrete convolution, each row of the matrix is constrained to be equal to the row above shifted by one element.

---

The Matrix Representation of 1D ‘Valid’ Discrete Convolution

Let’s consider a simple 1D signal and a kernel:

• Input Signal $\mathbf{i}$: $[i_1,i_2,i_3,i_4,i_5]$
• Kernel $\mathbf{k}$: $[k_1,k_2,k_3]$

A ‘valid’ convolution (implying no padding or kernel flipping) calculates the output $\mathbf{s}$ only at positions where the kernel fully overlaps the signal:

• $s_1=(i_1\cdot k_1)+(i_2\cdot k_2)+(i_3\cdot k_3)$
• $s_2=(i_2\cdot k_1)+(i_3\cdot k_2)+(i_4\cdot k_3)$
• $s_3=(i_3\cdot k_1)+(i_4\cdot k_2)+(i_5\cdot k_3)$

This operation can be expressed as a single matrix multiplication ($\mathbf{s}=\mathbf{M}\cdot \mathbf{i}$) by constructing a corresponding Toeplitz matrix $\mathbf{M}$, as follows:

$$\left(\begin{array}{c}{s}_1\\ s_2\\ s_3\end{array}\right)=\left(\begin{array}{ccccc}{k}_1& k_2& k_3& 0& 0\\ 0& k_1& k_2& k_3& 0\\ 0& 0& k_1& k_2& k_3\end{array}\right)\cdot \left(\begin{array}{c}{i}_1\\ i_2\\ i_3\\ i_4\\ i_5\end{array}\right)$$

This proves how the sliding operation of convolution can be regarded as a single matrix multiplication.

Toeplitz matrix

Looking at the matrix $\mathbf{M}$ :

$$\mathbf{M}=\left(\begin{array}{ccccc}{k}_1& k_2& k_3& 0& 0\\ 0& k_1& k_2& k_3& 0\\ 0& 0& k_1& k_2& k_3\end{array}\right)$$

it can be observed the following pattern:

• the second row is exactly the first row shifted one position to the right.
• the third row is the second shifted one position to the right.

This special structure, with constant diagonals, is precisely a Toeplitz matrix.

2D case

In $2D$ case, convolution corresponds to a doubly block circulant matrix.
The underlying principle remains the same, but the matrix structure becomes more elaborate in order to manage the 2D nature of the image.

In addition to these equality constraints between elements, convolution usually corresponds to a sparse matrix (a matrix whose elements are mostly zero).
This is because the kernel is generally much smaller than the input image.

Looking again at the above Toeplitz matrix $\mathbf{M}$, notice how many zeros are present: this is due to the kernel ($3$ elements) being smaller than the input ($5$ elements).
In a real case, with an image of millions of pixels and a kernel of size $5\times 5$, the matrix $\mathbf{M}$ would be enormous but almost entirely filled with zeros.

Note

Any neural network algorithm that works with matrix multiplication and does not depend on specific properties of the matrix structure should work with convolution, without requiring any further changes to the neural network.

Typical convolutional neural networks do make use of further specializations in order to deal with large inputs efficiently, but these are not strictly necessary from a theoretical perspective.