python - Toeplitz matrix with an image

Question

I'm struggling to understand something. So far I understood this : x is 3x3 matrix and W is a 2x2 matrix

a) extend W to be a 4X9 matrix and flatten x to be 9x1

b) multiply the Toeplitz matrix and the vector

the part that I don't understand is how can do the same thing with an 400 * 400 image grayscaled before and 3x3 filter.

x = 400 * 400

w = 3 * 3

h = 9 * 160 000

x_flatten = 160 000

output = x_flatten * h ??

I can't figure it out how can I play with the shape to achieve the same principles to be able to retrieve my image after

thank you

Answer 1

Toeplitz matrix is used to get the result of the convolution between two matices. Suppose X is of shape (n,n) and W is of shape (m,m). Then your Toeplitz matrix h will be of shape ((n-m+1)^2 , n^2) and your flatten matrix X_flatten will become (n^2, 1). Then the resulting multiplication will produce vector of the length (n-m+1)^2, which is exact number of elements of inner convolution. You just need to reshape it back to square.