Transposed Convolution
Definition
Let the matrix representation of a convolution with kernel $K$ be $C_{K}$. The following matrix transformation, defined by the transpose matrix of this, is called the transposed convolution.
$$ \mathbf{y} = C_{K}^{\mathsf{T}} \mathbf{x} $$
Explanation
Convolution is generally used along with pooling layers to reduce the dimensionality of input data and compress information. In contrast, transposed convolution is used to increase the dimensionality of compressed data, performing upsampling. Fundamentally, computing results by sliding the kernel across the input image is similar to convolution. The convolution outputs the dot product of a section of the image with the kernel, whereas transposed convolution differs by performing a scalar multiplication with each pixel of the image and the kernel. Additionally, in convolution, the input data area overlaps with the kernel, but in transposed convolution, the kernel overlaps with the output data area computed. The method of computation is well illustrated in the below GIFs.
For the same kernel, the matrix representations of convolution and transposed convolution are transposed concerning each other. Suppose we have a kernel as given in $3 \times 3$.
$$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$
The matrix transformation of convolution and transposed convolution for an image with this kernel $4 \times 4$ is as follows.
$$ \text{convolution: } \begin{bmatrix} 1 & 2 & 3 & 0 & 4 & 5 & 6 & 0 & 7 & 8 & 9 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 2 & 3 & 0 & 4 & 5 & 6 & 0 & 7 & 8 & 9 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 2 & 3 & 0 & 4 & 5 & 6 & 0 & 7 & 8 & 9 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 2 & 3 & 0 & 4 & 5 & 6 & 0 & 7 & 8 & 9 \end{bmatrix} $$
The corresponding transposed convolution is the transformation $B = A^{\mathsf{T}} : \mathbb{R}^{2 \times 2} \to \mathbb{R}^{4 \times 4}$ that sends the $\mathbb{R}^{2 \times 2}$ matrix to the $\mathbb{R}^{4 \times 4}$ matrix, shown below.
$$ \text{transposed convolution: } \begin{bmatrix} 1 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 \\ 3 & 2 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 4 & 0 & 1 & 0 \\ 5 & 4 & 2 & 1 \\ 6 & 5 & 3 & 2 \\ 0 & 6 & 0 & 3 \\ 7 & 0 & 4 & 0 \\ 8 & 7 & 5 & 4 \\ 9 & 8 & 6 & 5 \\ 0 & 9 & 0 & 6 \\ 0 & 0 & 7 & 0 \\ 0 & 0 & 8 & 7 \\ 0 & 0 & 9 & 8 \\ 0 & 0 & 0 & 9 \end{bmatrix} $$
Note that the two transformations are not inverses of each other. Actually, multiplying the two matrices does not yield the identity matrix.
$$ AB = \begin{bmatrix} 285 & 186 & 154 & 94 \\ 186 & 285 & 106 & 154 \\ 154 & 106 & 285 & 186 \\ 94 & 154 & 186 & 285 \end{bmatrix} $$ $$ BA = \begin{bmatrix} 1 & 2 & 3 & 0 & 4 & 5 & 6 & 0 & 7 & 8 & 9 & 0 & 0 & 0 & 0 & 0 \\ 2 & 5 & 8 & 3 & 8 & 14 & 17 & 6 & 14 & 23 & 26 & 9 & 0 & 0 & 0 & 0 \\ 3 & 8 & 13 & 6 & 12 & 23 & 28 & 12 & 21 & 38 & 43 & 18 & 0 & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & 0 & 8 & 23 & 38 & 21 & 32 & 68 & 83 & 42 & 56 & 113 & 128 & 63 \\ 0 & 0 & 0 & 0 & 9 & 26 & 43 & 24 & 36 & 77 & 94 & 48 & 63 & 128 & 145 & 72 \\ 0 & 0 & 0 & 0 & 0 & 9 & 18 & 27 & 0 & 36 & 45 & 54 & 0 & 63 & 72 & 81 \end{bmatrix} $$