Answers.Body: <p>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 <span class="math-container">$3 \times 3$</span> kernel to a <span class="math-container">$4 \times 4$</span> input, with no padding and with unit stride.</p>
  <p>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).</p>
  <p><a href="https://i.sstatic.net/zviX9.png" rel="noreferrer"><img src="https://i.sstatic.net/zviX9.png" alt="enter image description here" /></a></p>
  <p>Now, let the kernel be defined as follows</p>
  <p><span class="math-container">$$
  \mathbf{W} = 
  \begin{bmatrix}
  w_{0, 0} &amp; w_{0, 1} &amp; w_{0, 2} \\
  w_{1, 0} &amp; w_{1, 1} &amp; w_{1, 2} \\
  w_{2, 0} &amp; w_{2, 1} &amp; w_{2, 2}
  \end{bmatrix} 
  \in
  \mathbb{R}^{3 \times 3}
  $$</span></p>
  <p>Similarly, let the input be defined as</p>
  <p><span class="math-container">$$
  \mathbf{I} = 
  \begin{bmatrix}
  i_{0, 0} &amp; i_{0, 1} &amp; i_{0, 2} &amp; i_{0, 3} \\
  i_{1, 0} &amp; i_{1, 1} &amp; i_{1, 2} &amp; i_{1, 3} \\
  i_{2, 0} &amp; i_{2, 1} &amp; i_{2, 2} &amp; i_{2, 3} \\
  i_{3, 0} &amp; i_{3, 1} &amp; i_{3, 2} &amp; i_{3, 3} \\ 
  \end{bmatrix} 
  \in
  \mathbb{R}^{4 \times 4}
  $$</span></p>
  <p>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 <span class="math-container">$\mathbf{W}$</span> as a sparse matrix <span class="math-container">$\mathbf{W}' \in \mathbb{R}^{4 \times 16}$</span> (which is a <a href="https://ccrma.stanford.edu/%7Ejos/fp/Cyclic_Convolution_Matrix.html" rel="noreferrer"><em>circulant matrix</em></a> because of its circular nature) as follows.</p>
  <p><span class="math-container">$$
  {\scriptscriptstyle
  \mathbf{W}' = 
  \begin{bmatrix}
  w_{0, 0} &amp; w_{0, 1} &amp; w_{0, 2} &amp; 0 &amp; w_{1, 0} &amp; w_{1, 1} &amp; w_{1, 2} &amp; 0 &amp;  w_{2, 0} &amp; w_{2, 1} &amp; w_{2, 2} &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
  0 &amp; w_{0, 0} &amp; w_{0, 1} &amp; w_{0, 2} &amp; 0 &amp; w_{1, 0} &amp; w_{1, 1} &amp; w_{1, 2} &amp; 0 &amp; w_{2, 0} &amp; w_{2, 1} &amp; w_{2, 2} &amp; 0 &amp; 0 &amp; 0 &amp; 0  \\
  0 &amp; 0 &amp; 0 &amp; 0 &amp; w_{0, 0} &amp; w_{0, 1} &amp; w_{0, 2} &amp; 0 &amp; w_{1, 0} &amp; w_{1, 1} &amp; w_{1, 2} &amp; 0 &amp;  w_{2, 0} &amp; w_{2, 1} &amp; w_{2, 2} &amp; 0 \\
  0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; w_{0, 0} &amp; w_{0, 1} &amp; w_{0, 2} &amp; 0 &amp; w_{1, 0} &amp; w_{1, 1} &amp; w_{1, 2} &amp; 0 &amp;  w_{2, 0} &amp; w_{2, 1} &amp; w_{2, 2}
  \end{bmatrix} 
  }
  $$</span>
  Similarly, we reshape the input <span class="math-container">$\mathbf{I}$</span> as a 16-dimensional vector <span class="math-container">$\mathbf{I}' \in  \mathbb{R}^{16}$</span>.</p>
  <p><span class="math-container">$$
  {\scriptstyle
  \mathbf{I}' = 
  \begin{bmatrix}
  i_{0, 0} &amp; i_{0, 1} &amp; i_{0, 2} &amp; i_{0, 3} &amp; i_{1, 0} &amp; i_{1, 1} &amp; i_{1, 2} &amp; i_{1, 3} &amp; i_{2, 0} &amp; i_{2, 1} &amp; i_{2, 2} &amp; i_{2, 3} &amp; i_{3, 0} &amp; i_{3, 1} &amp; i_{3, 2} &amp; i_{3, 3} 
  \end{bmatrix}^T
  }
  $$</span></p>
  <p>Then the convolution of <span class="math-container">$\mathbf{W}$</span> and <span class="math-container">$\mathbf{I}$</span>, that is</p>
  <p><span class="math-container">$$\mathbf{W} \circledast \mathbf{I} = \mathbf{O} \in \mathbb{R}^{2 \times 2},$$</span>
  where <span class="math-container">$\circledast$</span> is the convolution operator, is equivalently defined as <span class="math-container">$$\mathbf{W}' \cdot \mathbf{I}' = \mathbf{O}' \in \mathbb{R}^{4},$$</span> where <span class="math-container">$\cdot$</span> is the matrix-vector multiplication operator. The produced vector <span class="math-container">$\mathbf{O}'$</span> can then be reshaped as a <span class="math-container">$2 \times 2$</span> feature map.</p>
  <p>You can easily verify that this representation is correct by multiplying e.g. the 16-dimensional input vector <span class="math-container">$\mathbf{I}'$</span> with the first row of <span class="math-container">$\mathbf{W}'$</span> to obtain the top-left entry of the feature map.</p>
  <p><span class="math-container">$$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} ,$$</span> which is equivalent to an element-wise multiplication of <span class="math-container">$\mathbf{W}$</span> with the top-left <span class="math-container">$3 \times 3$</span> sub-matrix of the input followed by a summation over all elements (i.e. convolution), that is</p>
  <p><span class="math-container">$$
  \sum \left(
  \begin{bmatrix}
  w_{0, 0} &amp; w_{0, 1} &amp; w_{0, 2} \\
  w_{1, 0} &amp; w_{1, 1} &amp; w_{1, 2} \\
  w_{2, 0} &amp; w_{2, 1} &amp; w_{2, 2}
  \end{bmatrix} 
  \odot
  \begin{bmatrix}
  i_{0, 0} &amp; i_{0, 1} &amp; i_{0, 2} \\
  i_{1, 0} &amp; i_{1, 1} &amp; i_{1, 2}  \\
  i_{2, 0} &amp; i_{2, 1} &amp; i_{2, 2}
  \end{bmatrix} 
  \right) = \mathbf{O}_{0, 0} = \mathbf{O}'_{0} \in \mathbb{R},
  $$</span>
  where <span class="math-container">$\odot$</span> is the element-wise multiplication and <span class="math-container">$\sum$</span> is the summation over all elements of the resulting matrix.</p>
  <p>The advantage of this representation (and computation) is that back-propagation can be computed more easily by just transposing <span class="math-container">$\mathbf{W}'$</span>, i.e. with <span class="math-container">$\mathbf{W}'^T$</span>.</p>
  <p>Take also a look at <a href="https://github.com/alisaaalehi/convolution_as_multiplication" rel="noreferrer">this Github repository</a> that explains how the convolution can be implemented as matrix multiplication.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-07-23T07:06:07.090Z
Answers.Text: link to github repo is dead
Answers.UserDisplayName: Adam
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-06T01:16:35.783Z
Answers.Text: 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)?
Answers.UserDisplayName: Francisco Serra
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-06T04:13:51.147Z
Answers.Text: What is the justification for "W⊛I=O∈R2×2, where ⊛ is the convolution operator, is equivalently defined as W′⋅I′=O′∈R4"?
Answers.UserDisplayName: Snehal Patel
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-01-06T12:00:53.873Z
Answers.Text: @SnehalPatel The justification is that this is a known result in mathematics. See the link to the "circulant matrix" in my answer.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-10-16T09:25:07.343Z
Answers.Text: I understood the circulant matrix but in $W^\prime$ I did not understand the reason for shifting two to left instead of one.
Answers.UserDisplayName: jomegaA
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-14T12:51:56.600Z
Answers.LastActivityDate: 2020-11-07T00:33:53.540Z
Answers.LastEditDate: 2020-11-07T00:33:53.540Z
Answers.UserDisplayName: nbro
Body: <p>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 <a href="https://en.wikipedia.org/wiki/Circulant_matrix" rel="noreferrer">circulant matrix</a> containing shifted versions of the kernel (as rows or columns) and the vector is the input. </p>
  
  <p>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.</p>
  
  <p>Is this the usual way the convolution operations are implemented in CNNs?</p>
  
Tags: <machine-learning><deep-learning><convolutional-neural-networks><implementation><convolution>
Title: How can the convolution operation be implemented as a matrix multiplication?
UserDisplayName: nbro
ThreadText: # How can the convolution operation be implemented as a matrix multiplication?
  
  (Asked by: username_0 on 2019-03-12)
  
  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](https://en.wikipedia.org/wiki/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?
  
  **Tags:** machine-learning, deep-learning, convolutional-neural-networks, implementation, convolution
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2020-06-14. Score: 12 | Accepted answer
  
  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](https://i.sstatic.net/zviX9.png)](https://i.sstatic.net/zviX9.png)
  
  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*](https://ccrma.stanford.edu/%7Ejos/fp/Cyclic_Convolution_Matrix.html) 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](https://github.com/alisaaalehi/convolution_as_multiplication) that explains how the convolution can be implemented as matrix multiplication.
  
  > **Comments:**
  > **username_1**: link to github repo is dead  
  > **username_2**: 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)?  
  > **username_3**: What is the justification for "W⊛I=O∈R2×2, where ⊛ is the convolution operator, is equivalently defined as W′⋅I′=O′∈R4"?  
  > **username_0**: @username_3 The justification is that this is a known result in mathematics. See the link to the "circulant matrix" in my answer.  
  > **username_4**: I understood the circulant matrix but in $W^\prime$ I did not understand the reason for shifting two to left instead of one.  
  
  ---
  
  