2-D convolution as a matrix-matrix multiplication

neural-network deep-learning conv-neural-network matrix-multiplication convolution
no_name picture no_name · May 28, 2013 · Viewed 36.8k times · Source

I know that, in the 1D case, the convolution between two vectors, a and b, can be computed as conv(a, b), but also as the product between the T_a and b, where T_a is the corresponding Toeplitz matrix for a.

Is it possible to extend this idea to 2D?

Given a = [5 1 3; 1 1 2; 2 1 3] and b=[4 3; 1 2], is it possible to convert a in a Toeplitz matrix and compute the matrix-matrix product between T_a and b as in the 1-D case?

Answer

Salvador Dali picture Salvador Dali · May 18, 2017

Yes, it is possible and you should also use a doubly block circulant matrix (which is a special case of Toeplitz matrix). I will give you an example with a small size of kernel and the input, but it is possible to construct Toeplitz matrix for any kernel. So you have a 2d input x and 2d kernel k and you want to calculate the convolution x * k. Also let's assume that k is already flipped. Let's also assume that x is of size n×n and k is m×m.

So you unroll k into a sparse matrix of size (n-m+1)^2 × n^2, and unroll x into a long vector n^2 × 1. You compute a multiplication of this sparse matrix with a vector and convert the resulting vector (which will have a size (n-m+1)^2 × 1) into a n-m+1 square matrix.

I am pretty sure this is hard to understand just from reading. So here is an example for 2×2 kernel and 3×3 input.

enter image description here * enter image description here

Here is a constructed matrix with a vector:

enter image description here

which is equal to enter image description here.

And this is the same result you would have got by doing a sliding window of k over x.

Related questions

Why binary_crossentropy and categorical_crossentropy give different performances for the same problem?

I'm trying to train a CNN to categorize text by topic. When I use binary cross-entropy I get ~80% accuracy, with categorical cross-entropy I get ~50% accuracy. I don't understand why this is. It's a multiclass problem, doesn't that mean that I …

Read More
How to calculate the number of parameters for convolutional neural network?

I'm using Lasagne to create a CNN for the MNIST dataset. I'm following closely to this example: Convolutional Neural Networks and Feature Extraction with Python. The CNN architecture I have at the moment, which doesn't include any dropout layers, is: …

Read More
ValueError: Input 0 is incompatible with layer conv1d_1: expected ndim=3, found ndim=4

I am building a prediction model for the sequence data using conv1d layer provided by Keras. This is how I did model= Sequential() model.add(Conv1D(60,32, strides=1, activation='relu',padding='causal',input_shape=(None,64,1))) model.add(Conv1D(80,10, …

Read More