1
$\begingroup$

I am delving into the matrix representation of dilated convolutions, especially after understanding standard 1D convolutions as Toeplitz matrix-vector multiplications.

My specific focus is on Dilated Convolution. Based on my initial understanding, a dilated convolution involves introducing "holes" or zeros between elements in the convolution process.

Therefore, would a matrix representation of a dilated convolution simply be akin to the standard convolution matrix but with zeros inserted between the non-zero elements in each row?

Any insights or mathematical references regarding this would be highly valuable to me.

$\endgroup$
1
  • $\begingroup$ I think they use sparse methods for multiplication, so instead of having actual zeros, they just change which elements they multiply together. They claim it is same compute cost, and the only way for that is not to do zero-multiplications. I think it works a little like striding. $\endgroup$ Commented May 22 at 20:26

1 Answer 1

2
$\begingroup$

Well, I don't know what insights you are looking for exactly, your understanding sounds very solid and you are correct that there will be zeros between the kernel elements in the matrix. Maybe its interesting for you how to construct such a matrix: We start from what we have and what we want to achieve:

We have some 1D data $\mathbf{a}$ and a kernel $\mathbf{k}$:

$$ \mathbf{a} = [a_0, ..., a_i, ...a_T ], \mathbf{k} = [k_0, k_1] $$

We want the following result for dilation factor 1 (no dilation):

$$ \mathbf{a} * \mathbf{k} = \begin{bmatrix} a_0 k_0 + a_1 k_1 \\ a_1 k_0 + a_2 k_1 \\ a_2 k_0 + a_3 k_1 \\ a_3 k_0 + a_4 k_1 \\ a_4 k_0 + a_5 k_1 \\ ... \end{bmatrix} $$

for dilation factor 2, we would reduce the sampling rate of the model by skipping elements. The end result should therefore look like this (with a stride of 1):

$$ \mathbf{a} * \mathbf{k} = \begin{bmatrix} a_0 k_0 + a_2 k_1 \\ a_1 k_0 + a_3 k_1 \\ a_2 k_0 + a_4 k_1 \\ a_3 k_0 + a_5 k_1 \\ a_4 k_0 + a_6 k_1 \\ ... \end{bmatrix} $$

It's straight forward what the matrix has to look like when you start from the desired result. By first writing $\mathbf{a}$ as a column vector and then designing the matrix row by row, the computation written out would then be:

$$ \mathbf{a} * \mathbf{k} = \begin{bmatrix} k_0 & 0 & k_1 & & \dots & & 0\\ & k_0 & 0 & k_1 & & & \\ \vdots & & k_0 & 0 & k_1 & & \vdots \\ & & & k_0 & 0 & k_1 & \\ 0 & & \dots & & k_0 & 0 & k_1 & \\ & & & & & & ... \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ a_4 \\ ...\end{bmatrix} = \begin{bmatrix} a_0 k_0 + a_2 k_1 \\ a_1 k_0 + a_3 k_1 \\ a_2 k_0 + a_4 k_1 \\ a_3 k_0 + a_5 k_1 \\ a_4 k_0 + a_6 k_1 \\ ... \end{bmatrix} $$

Clearly you are right, that there are zeros in between the kernel elements $k_i$, i.e. we introduce a zero diagonal into the matrix. The number of such diagonals corresponds exactly to the dilation rate. To make the stride of the convolution other than 1, lets call it $s$, simply shift the $i^{th}$ row by $(s-1) \cdot i$ zeros to the right.

$\endgroup$

You must log in to answer this question.

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