Re:Choose Your Weapon: Survival Strategies for Depressed AI ...
by ndriscoll on Friday April 14, 2023 @01:40PM
(#35572319)
Because convolution is an O(N^2) operation, but a Fourier transform (and its inverse) can be done in O(NlogN) and turns convolution into O(N) multiplication. So if you do FFT, multiply, Inverse FFT, you get convolution in O(NlogN).
Re:Choose Your Weapon: Survival Strategies for Depressed AI ...
by staunton on Friday April 14, 2023 @05:56PM
(#35575326)
I see, the wording confused me. You don't really "put Fourier transforms around the convolutional layers" because you have to completely replace the convolutions.
This seems to be done in some cases. I guess it isn't done more widely because the "standard" convolution kernels are very small and the performance would actually be worse?
Re:Choose Your Weapon: Survival Strategies for Depressed AI ...
by jondea on Friday April 14, 2023 @06:02PM
(#35575383)
Computing convolutions using FFTs is efficient for large kernels (or filters). Most convolutions in popular ML models have small kernels, a regime where it is typically more efficient to reformulate the convolution as a matrix multiplication.
I think your complexity argument is correct for N=pixels=kernel size. But typically, pixels>>kernel size.
Disclosure: I work at Arm optimising open source ML frameworks. Opinions are my own.
What do you mean? Processing a CNN layer takes an amount of time that does not depend on the input data, only the input/output sizes. Fourier transform is just a change of basis. Why should anything speed up?