12
$\begingroup$

How can the convolution operation used by CNNs be implemented as a matrix-vector multiplication? We often think of the convolution operation in CNNs as a kernel that slides across the input. However, rather than sliding this kernel (e.g. using loops), we can perform the convolution operation "in one step" using a matrix-vector multiplication, where the matrix is a circulant matrix containing shifted versions of the kernel (as rows or columns) and the vector is the input.

How exactly can this operation be performed? I am looking for a detailed step-by-step answer that shows how the convolution operation (as usually presented) can be performed using a matrix-vector multiplication.

Is this the usual way the convolution operations are implemented in CNNs?

$\endgroup$
0

1 Answer 1

10
$\begingroup$

To show how the convolution (in the context of CNNs) can be viewed as matrix-vector multiplication, let's suppose that we want to apply a $3 \times 3$ kernel to a $4 \times 4$ input, with no padding and with unit stride.

Here's an illustration of this convolutional layer (where, in blue, we have the input, in dark blue, the kernel, and, in green, the feature map or output of the convolution).

enter image description here

Now, let the kernel be defined as follows

$$ \mathbf{W} = \begin{bmatrix} w_{0, 0} & w_{0, 1} & w_{0, 2} \\ w_{1, 0} & w_{1, 1} & w_{1, 2} \\ w_{2, 0} & w_{2, 1} & w_{2, 2} \end{bmatrix} \in \mathbb{R}^{3 \times 3} $$

Similarly, let the input be defined as

$$ \mathbf{I} = \begin{bmatrix} i_{0, 0} & i_{0, 1} & i_{0, 2} & i_{0, 3} \\ i_{1, 0} & i_{1, 1} & i_{1, 2} & i_{1, 3} \\ i_{2, 0} & i_{2, 1} & i_{2, 2} & i_{2, 3} \\ i_{3, 0} & i_{3, 1} & i_{3, 2} & i_{3, 3} \\ \end{bmatrix} \in \mathbb{R}^{4 \times 4} $$

Then the convolution above (without padding and with stride 1) can be computed as a matrix-vector multiplication as follows. First, we redefine the kernel $\mathbf{W}$ as a sparse matrix $\mathbf{W}' \in \mathbb{R}^{4 \times 16}$ (which is a circulant matrix because of its circular nature) as follows.

$$ {\scriptscriptstyle \mathbf{W}' = \begin{bmatrix} w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 & w_{2, 0} & w_{2, 1} & w_{2, 2} & 0 & 0 & 0 & 0 & 0 \\ 0 & w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 & w_{2, 0} & w_{2, 1} & w_{2, 2} & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 & w_{2, 0} & w_{2, 1} & w_{2, 2} & 0 \\ 0 & 0 & 0 & 0 & 0 & w_{0, 0} & w_{0, 1} & w_{0, 2} & 0 & w_{1, 0} & w_{1, 1} & w_{1, 2} & 0 & w_{2, 0} & w_{2, 1} & w_{2, 2} \end{bmatrix} } $$ Similarly, we reshape the input $\mathbf{I}$ as a 16-dimensional vector $\mathbf{I}' \in \mathbb{R}^{16}$.

$$ {\scriptstyle \mathbf{I}' = \begin{bmatrix} i_{0, 0} & i_{0, 1} & i_{0, 2} & i_{0, 3} & i_{1, 0} & i_{1, 1} & i_{1, 2} & i_{1, 3} & i_{2, 0} & i_{2, 1} & i_{2, 2} & i_{2, 3} & i_{3, 0} & i_{3, 1} & i_{3, 2} & i_{3, 3} \end{bmatrix}^T } $$

Then the convolution of $\mathbf{W}$ and $\mathbf{I}$, that is

$$\mathbf{W} \circledast \mathbf{I} = \mathbf{O} \in \mathbb{R}^{2 \times 2},$$ where $\circledast$ is the convolution operator, is equivalently defined as $$\mathbf{W}' \cdot \mathbf{I}' = \mathbf{O}' \in \mathbb{R}^{4},$$ where $\cdot$ is the matrix-vector multiplication operator. The produced vector $\mathbf{O}'$ can then be reshaped as a $2 \times 2$ feature map.

You can easily verify that this representation is correct by multiplying e.g. the 16-dimensional input vector $\mathbf{I}'$ with the first row of $\mathbf{W}'$ to obtain the top-left entry of the feature map.

$$w_{0, 0} i_{0, 0} + w_{0, 1} i_{0, 1} + w_{0, 2} i_{0, 2} + 0 i_{0, 3} + w_{1, 0} i_{1, 0} + w_{1, 1} i_{1, 1} + w_{1, 2}i_{1, 2} + 0 i_{1, 3} + w_{2, 0} i_{2, 0} + w_{2, 1}i_{2, 1} + w_{2, 2} i_{2, 2} + 0 i_{2, 3} + 0 i_{3, 0} + 0 i_{3, 1} + 0 i_{3, 2} + 0 i_{3, 3} = \\ w_{0, 0} i_{0, 0} + w_{0, 1} i_{0, 1} + w_{0, 2} i_{0, 2} + w_{1, 0} i_{1, 0} + w_{1, 1} i_{1, 1} + w_{1, 2}i_{1, 2} + w_{2, 0} i_{2, 0} + w_{2, 1}i_{2, 1} + w_{2, 2} i_{2, 2} = \\ \mathbf{O}'_{0} \in \mathbb{R} ,$$ which is equivalent to an element-wise multiplication of $\mathbf{W}$ with the top-left $3 \times 3$ sub-matrix of the input followed by a summation over all elements (i.e. convolution), that is

$$ \sum \left( \begin{bmatrix} w_{0, 0} & w_{0, 1} & w_{0, 2} \\ w_{1, 0} & w_{1, 1} & w_{1, 2} \\ w_{2, 0} & w_{2, 1} & w_{2, 2} \end{bmatrix} \odot \begin{bmatrix} i_{0, 0} & i_{0, 1} & i_{0, 2} \\ i_{1, 0} & i_{1, 1} & i_{1, 2} \\ i_{2, 0} & i_{2, 1} & i_{2, 2} \end{bmatrix} \right) = \mathbf{O}_{0, 0} = \mathbf{O}'_{0} \in \mathbb{R}, $$ where $\odot$ is the element-wise multiplication and $\sum$ is the summation over all elements of the resulting matrix.

The advantage of this representation (and computation) is that back-propagation can be computed more easily by just transposing $\mathbf{W}'$, i.e. with $\mathbf{W}'^T$.

Take also a look at this Github repository that explains how the convolution can be implemented as matrix multiplication.

$\endgroup$
5
  • $\begingroup$ link to github repo is dead $\endgroup$
    – Adam
    Jul 23, 2022 at 7:06
  • $\begingroup$ Thank you very much! very good explanation. Now I have a question, is it possible to come up with a general expression for W'(i,j)? $\endgroup$ Jan 6, 2023 at 1:16
  • $\begingroup$ What is the justification for "W⊛I=O∈R2×2, where ⊛ is the convolution operator, is equivalently defined as W′⋅I′=O′∈R4"? $\endgroup$ Jan 6, 2023 at 4:13
  • 1
    $\begingroup$ @SnehalPatel The justification is that this is a known result in mathematics. See the link to the "circulant matrix" in my answer. $\endgroup$
    – nbro
    Jan 6, 2023 at 12:00
  • $\begingroup$ I understood the circulant matrix but in $W^\prime$ I did not understand the reason for shifting two to left instead of one. $\endgroup$
    – jomegaA
    Oct 16, 2023 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .