Convolution as Matrix Multiplication
Step by step explanation of 2D convolution implemented as matrix multiplication using Toeplitz matrices. (Read full explanation in pdf format)
What is the purpose?
Instead of using for-loops to perform 2D convolution on images (or any other 2D matrices) we can convert the filter to a Toeplitz matrix and image to a vector and do the convolution just by one matrix multiplication (and of course some post-processing on the result of this multiplication to get the final result)
Why do we do that?
There are many efficient matrix multiplication algorithms, so using them we can have an efficient implementation of the convolution operation.
What is in this document?
Mathematical and algorithmic explanation of this process. I will put a naive Python implementation of this algorithm to make it more clear.
Summary of the methods
1. Define Input and Filter
Let I be the input signal and F be the filter or kernel.
2. Calculate the final output size
If the I is m1 x n1 and F is m2 x n2 the size of the output will be:
3. Zero-pad the filter matrix
Zero pad the filter to make it the same size as the output.
4. Create a Toeplitz matrix for each row of the zero-padded filter
5. Create a doubly blocked Toeplitz matrix
Now all these small Toeplitz matrices should be arranged in a big doubly blocked Toeplitz matrix. 
6. Convert the input matrix to a column vector
7. Multiply doubly blocked Toeplitz matrix with the vectorized input signal
This multiplication gives the convolution result.
8. Last step: reshape the result to a matrix form
Cool website