I have been reading through Chapter 9 of www.deeplearningbbook.org, where convolutional networks are being described.

The following image represents the output of a 2D convolution, without kernel flipping.

enter image description here

The book goes on to describe this matrix as a Toeplitz matrix where,

for univariate discrete convolution, each row of the matrix is constrained to be equal to the row above shifted by one element.

I fully understand this statement since w, x, y and z are constants in their respective columns with shifting elements.

However, there is no mention of diagonal-constants which are a key feature of such matrices. As per Wikipedia (link above) and several other sources:

a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant.

Going back to the image above, does this mean that, for instance, aw == cx == gy? How can this be ensured when all elements are different?


The matrices in that picture are not toeplitz matrices. Rather, convolution can be treated as matrix multiplication by a toeplitz matrix.

For example, to convolve $x = [1, 3, 1, 0]^T$ by the filter [5, 1, 1], you first construct the toeplitz matrix:

$$M = \begin{bmatrix} 5 & 1 & 1 & 0 & 0 & 0\\ 0 & 5 & 1 & 1 & 0 & 0\\ 0 & 0 & 5 & 1 & 1 & 0\\ 0 & 0 & 0 & 5 & 1 & 1\\ \end{bmatrix}$$

Then $Mx$ computes the convolution (technically correlation!) of $x$ by the filter. Clearly $M$ is toeplitz.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.