假设我们需要将矩阵 $\mathbf{X} = \begin{bmatrix}
x_1 & x_2 & x_3 \\
x_4 & x_5 & x_6 \\
x_7 & x_8 & x_9
\end{bmatrix}$ 以 $\mathbf{H}=\begin{bmatrix}
h_1 & h_2 \\
h_3 & h_4
\end{bmatrix}$ 为卷积核做卷积操作，普通操作是用卷积核在矩阵上进行滚动相乘相加，但是这样不利于 GPU 等硬件加速运算，一般而言，矩阵的卷积会先转换为稀疏矩阵的乘法，再通过 BLAS 等已经极度优化过的线性代数计算库来计算，效率可以得到提升。
下面说明一下转换的方法：对于原来的矩阵，我们展开成一个列向量
$$
\mathbf{X} = \begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
x_6 \\
x_7 \\
x_8 \\
x_9
\end{bmatrix}
$$
（说明：以下卷积操作没有对卷积核进行旋转操作，但道理类似）
之后我们对卷积核进行循环展开，展开成为这样的矩阵：
$$
\mathbf{H} = \begin{bmatrix} h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 & 0 \\
0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 \\
0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 \\
0 & 0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 \\
\end{bmatrix}
$$
最后计算两个矩阵的乘积 $\mathbf{HX}$ 就得到了：
$$
\begin{bmatrix} h_1x_1+h_2x_2+h_3x_4+h_4x_5 \\
h_1x_2+h_2x_3+h_3x_5+h_4x_6 \\
h_1x_4+h_2x_5+h_3x_7+h_4x_8 \\
h_1x_5+h_2x_6+h_3x_8+h_4x_9 \\ \end{bmatrix}
$$
最后对这个列向量进行 reshape 操作就得到：
$$
\begin{bmatrix} h_1x_1+h_2x_2+h_3x_4+h_4x_5 &
h_1x_2+h_2x_3+h_3x_5+h_4x_6 \\
h_1x_4+h_2x_5+h_3x_7+h_4x_8 &
h_1x_5+h_2x_6+h_3x_8+h_4x_9 \\ \end{bmatrix}
$$
正是卷积的结果。
那么通用的做法是什么呢？假设输入矩阵 $\mathbf{X}$ 维数为 $m_1 \times n_1 $，卷积核 $\mathbf{H}$ 维数为 $m_2 \times n_2 $，输出尺寸则为 $ (m_1+m_2-1) \times (n_1+n_2-1) $
首先将卷积核向右上补零为输出结果的尺寸（举例为 $ 4 \times 4 $）：
$$
\mathbf{H}=\begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ h_1 & h_2 & 0 & 0 \\ h_3 & h_4 & 0 & 0 \end{bmatrix}
$$
从下到上将每一行展开成列数为 $n_1$ 的 Toeplitz 矩阵：
$$
\mathbf{F_0} = \begin{bmatrix} h_3 & 0 & 0 \\
h_4 & h_3 & 0 \\
0 & h_4 & h_3 \\
0 & 0 & h_4
\end{bmatrix}
$$
$$
\mathbf{F_1} = \begin{bmatrix} h_1 & 0 & 0 \\
h_2 & h_1 & 0 \\
0 & h_2 & h_1 \\
0 & 0 & h_2
\end{bmatrix}
$$
$$
\mathbf{F_3} = \mathbf{F_2} = \begin{bmatrix} 0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0 \\
0 & 0 & 0
\end{bmatrix}
$$
再将这些矩阵组合成 Doubly Blocked Toeplitz 矩阵，此时列数为 $m_1$：
$$
\mathbf{D} = \begin{bmatrix} \mathbf{F_0} & \mathbf{0} & \mathbf{0} \\
\mathbf{F_1} & \mathbf{F_0} & \mathbf{0} \\
\mathbf{F_2} & \mathbf{F_1} & \mathbf{F_0} \\
\mathbf{F_3} & \mathbf{F_2} & \mathbf{F_1} \\
\end{bmatrix}
$$
然后我们同样展开 $\mathbf{X}$ 为列向量，不过要从下到上展开：
$$
\mathbf{X}= \begin{bmatrix} x_7 \\ x_8 \\ x_9 \\ x_4 \\ x_5 \\ x_6 \\ x_1 \\ x_2 \\ x_3\end{bmatrix}
$$
然后计算 $\mathbf{D}\mathbf{X}$ 即可，计算完毕的结果同样进行 reshape，然后上下翻转就得到了我们想要的结果。
反卷积
在 pytorch 中，反卷积也叫 TransposedConvolution，这是为什么呢，我们看到文章前半段提到的矩阵乘法：
$$
\mathbf{X}= \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ x_8 \\ x_9\end{bmatrix}
$$
$$
\mathbf{H} = \begin{bmatrix} h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 & 0 \\
0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 & 0 & 0 \\
0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 & 0 \\
0 & 0 & 0 & 0 & h_1 & h_2 & 0 & h_3 & h_4 \\
\end{bmatrix}
$$
$\mathbf{X}$ 是一个 $9\times1$ 的矩阵，而 $\mathbf{H}$ 是一个 $4\times9$ 的矩阵，因此 $ \mathbf{HX}$ 就是一个 $4\times1$ 的矩阵，reshape 之后得到的是 $2\times2$ 的矩阵。
假设我们现在有一张 $2\times2$ 的特征图，要怎么反卷积得到一张上采样之后的图呢？看到这里你已经明白了，方法意外地简单，只需要把这个特征图也展开成列向量，然后用上面的卷积矩阵的转置进行左乘，就得到我们想要的结果！
展开成列向量的特征图尺寸是 $4\times1$，$\mathbf{H}^{\sf T}$ 的尺寸是 $9\times4$，左乘之后得到 $9\times1$ 的矩阵，进行 reshape 得到了 $3\times3$ 的原始图！
当然，在实际中，卷积与反卷积的权重不一定需要一样，尺寸也可以不一样。
参考资料：
https://stackoverflow.com/questions/16798888/2-d-convolution-as-a-matrix-matrix-multiplication