4 ms·

I'd guess that the "sliding window" metaphor means you could model matrix multiplication as a convolution. Does this give any intuition for matrix multiplicatio

by Twisol 5y ago

I'd guess that the "sliding window" metaphor means you could model matrix multiplication as a convolution. Does this give any intuition for matrix multiplication via the Fast Fourier Transform? https://en.m.wikipedia.org/wiki/Convolution_theorem https://en.m.wikipedia.org/wiki/Convolution_theorem > the convolution theorem states that under suitable conditions the Fourier transform of a convolution of two functions (or signals) is the pointwise product of their Fourier transforms.

amelius 5y ago
The fastest known matrix multiplication algorithm is the Coppersmith-Winograd algorithm with a complexity of O(n^2.3737). FFT is O(n log n). So probably not.
- Twisol 5y ago
  Apologies; apparently I was thinking of integer multiplication using FFT: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... But my question (which wasn't about asymptotic complexity) stands: can we think about matrix multiplication as a convolution? If so, we can do pointwise multiplication sandwiched between Fourier transforms -- I don't expect it to be fast, I just expect it to be possible.
- Rayhem 5y ago
  > Fastest known matrix multiplication algorithm... ...for general matrices. Fourier transforms do indeed diagonalize circulant matrices[1], making their multiplications O(2 n log n + n) -> O(n log n). [1]: https://en.wikipedia.org/wiki/Circulant_matrix https://en.wikipedia.org/wiki/Circulant_matrix
  - amelius 5y ago
    Yes, no doubt that there are faster algorithms for specific matrices. That matrix you are bringing into the discussion is only n-dimensional, so not surprising that you can multiply it faster than a matrix that is n×n dimensional.
cochne 5y ago
You can't model matrix multiplication as a convolution, but you can model convolution as matrix multiplication (with a toeplitz matrix) which is why the discrete fourier transform can be modeled as a matrix multiplication.
- Twisol 5y ago
  > You can't model matrix multiplication as a convolution Hmm. I'm not convinced yet... The "convolution" of two functions M and N -- let's notate it as M <> N, because ASCII -- will itself be a function, where for each index `i` we consider indices of M and N that sum to `i`. At each index `i`, we "sum" the "products" of M and N at indices summing to `i`; so if `i` is 2 (and we start indexing at 0, for sanity), we have `(M <> N)(2) = M(0)*N(2) + M(1)*N(1) + M(2)*N(0)`. https://betterexplained.com/articles/intuitive-convolution/ https://betterexplained.com/articles/intuitive-convolution/ Now consider a matrix multiplication M * N. We can think of M as an array of row vectors, and N an array of column vectors; in both cases, they're functions from (a subset of) the naturals to matrix elements. To instantiate convolution on our matrices, we can take multiplication as dot-product, and addition as a formal (uninterpreted) sum. (So, technically, we need to lift the elements of our input matrices to these sums as well, but there's a canonical way to do this.) Then M <> N is an array of formal sums of vectors; each formal sum gives an anti-diagonal band of elements in the matrix product, and the whole array runs along the main diagonal. There are almost certainly faults in the remaining details -- for example, it's not really clear that this is associative yet, due to the formal sum -- but this seems to cast matrix multiplication in the shape of a convolution.

by Twisol 5y ago

amelius 5y ago

The fastest known matrix multiplication algorithm is the Coppersmith-Winograd algorithm with a complexity of O(n^2.3737). FFT is O(n log n). So probably not.

Twisol 5y ago
Apologies; apparently I was thinking of integer multiplication using FFT: https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strasse... But my question (which wasn't about asymptotic complexity) stands: can we think about matrix multiplication as a convolution? If so, we can do pointwise multiplication sandwiched between Fourier transforms -- I don't expect it to be fast, I just expect it to be possible.
Rayhem 5y ago
> Fastest known matrix multiplication algorithm... ...for general matrices. Fourier transforms do indeed diagonalize circulant matrices[1], making their multiplications O(2 n log n + n) -> O(n log n). [1]: https://en.wikipedia.org/wiki/Circulant_matrix https://en.wikipedia.org/wiki/Circulant_matrix
- amelius 5y ago
  Yes, no doubt that there are faster algorithms for specific matrices. That matrix you are bringing into the discussion is only n-dimensional, so not surprising that you can multiply it faster than a matrix that is n×n dimensional.

cochne 5y ago

You can't model matrix multiplication as a convolution, but you can model convolution as matrix multiplication (with a toeplitz matrix) which is why the discrete fourier transform can be modeled as a matrix multiplication.

Twisol 5y ago
> You can't model matrix multiplication as a convolution Hmm. I'm not convinced yet... The "convolution" of two functions M and N -- let's notate it as M <> N, because ASCII -- will itself be a function, where for each index `i` we consider indices of M and N that sum to `i`. At each index `i`, we "sum" the "products" of M and N at indices summing to `i`; so if `i` is 2 (and we start indexing at 0, for sanity), we have `(M <> N)(2) = M(0)*N(2) + M(1)*N(1) + M(2)*N(0)`. https://betterexplained.com/articles/intuitive-convolution/ https://betterexplained.com/articles/intuitive-convolution/ Now consider a matrix multiplication M * N. We can think of M as an array of row vectors, and N an array of column vectors; in both cases, they're functions from (a subset of) the naturals to matrix elements. To instantiate convolution on our matrices, we can take multiplication as dot-product, and addition as a formal (uninterpreted) sum. (So, technically, we need to lift the elements of our input matrices to these sums as well, but there's a canonical way to do this.) Then M <> N is an array of formal sums of vectors; each formal sum gives an anti-diagonal band of elements in the matrix product, and the whole array runs along the main diagonal. There are almost certainly faults in the remaining details -- for example, it's not really clear that this is associative yet, due to the formal sum -- but this seems to cast matrix multiplication in the shape of a convolution.