1

Discr. convolution can be represented as multiplication of input with matrix M.

Where M is presented a special case of Toeplitz matrices - circulant matrices.

The questions is: is 2d convolution can also be represented as matrix multiplication?

p.s. By dicr. convolution I mean dicr. convolution with indexing discrete samples in modulus fashion, i.e. the discrete signal is repeating ....X[n-1]x[0]x[1]...x[N-1]x[0]...

Konstantin Burlachenko
  • 5,233
  • 2
  • 41
  • 40
  • 1
    Possible duplicate of [2-D convolution as a matrix-matrix multiplication](https://stackoverflow.com/questions/16798888/2-d-convolution-as-a-matrix-matrix-multiplication) – Geoffrey Negiar Jul 18 '17 at 22:50
  • See [How can the convolution operation be implemented as a matrix-vector multiplication?](https://ai.stackexchange.com/q/11172/2444). – nbro Jun 14 '20 at 14:00

1 Answers1

1

Yes, it can, but it will generally be a rather big matrix. If your data set is on a grid of size NxM, then the convolution is a matrix operating on a vector of length N*M; the convolution matrix has N2M2 elements.

If your convolution kernel is small, then the matrix will typically a band matrix where the width of the band is at least N or M.

Han-Kwang Nienhuys
  • 3,084
  • 2
  • 12
  • 31
  • For 1D case is the signal has N slots, then convolution can be descried as NxN matrix, but really, it can defined via "Nx1" column, and all other are just curculant rotation of this "Nx1" column....I think that similar symmetry should be for 2d case. – Konstantin Burlachenko May 20 '16 at 22:42
  • @bruziuz I'm not sure that's the case since you have to wrap around back to the beginning before you've gone through all of the elements of the matrix. I should also mention that your question is trivially true for separable filters. – beaker May 20 '16 at 23:06