News for hackers. Stuff that matters.
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.

Re:Choose Your Weapon: Survival Strategies for Depressed AI ... by Ambix on Saturday April 15, 2023 @05:13AM (#35578945)
Could you point to some actual examples of using FFT for NNs in real projects / GitHub codebases? Would like to dig more into the thing.