Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The FFT Strikes Back: An Efficient Alternative to Self-Attention

arxiv.org

Post reply on HN
Print view View original

61–70 of 175 posts

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#61

Post by thijson »

bee_rider wrote: post #39
yagizdegirmenci wrote: post #10

Google introduced this idea in 2022 with "FNet: Mixing Tokens with Fourier Transforms" [0]. Later they found out that, performance of their TPU(s) for matrix multiplication was faster than FFT in the most scenarios. [0]: https://arxiv.org/abs/2105.03824

That seems like an odd comparison, specialty hardware is often better, right? Hey, do DSPs have special hardware to help with FFTs? (I’m actually asking, this isn’t a rhetorical question, I haven’t used one of the things but it seems like it could vaguely be helpful).

I remember hearing about logic to help with deinterleaving the results of the butterfly network after the FFT is done.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#63

Post by leecarraher »

this seems to follow the similar FNO work by nvidia, and switching to frequency domain is usually in any computer scientist's toolbox at this point, however, I'm curious if this translates to real gains for real architectures. FFT makes use of imaginary numbers to encode the harmonics of the signal, these are generally not amenable to gpu architectures. Would fast walsh hadamard suffice? Sometimes the 'signal mixing' is more important than the harmonics of a compositions of sines. Or do we go further down the rabbit hole of trained transformation and try out wavelets? I am an avid FFT fan, (love fast johnson lindenstrauss transform using the embedded uncertainty principle for RIP), but sometimes real hardware and good theory dont always align (eg there are sub ternary matrix multiplies, but they are rarely used in DL)

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#65

Post by SJC_Hacker »

TeMPOraL wrote: post #50
TheDudeMan wrote: post #36

Machines going to be thinking in the frequency domain. We cooked.

Our bodies have parts that do processing in frequency domain. Who knows, maybe it'll turn out we are thinking in the frequency domain, too.

Yes, the cochlea for one basically performs an FT on the incoming input signal, at least with respect to magnitude. The phase portion is still in the time domain

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#66

Post by hansvm »

leecarraher wrote: post #63

this seems to follow the similar FNO work by nvidia, and switching to frequency domain is usually in any computer scientist's toolbox at this point, however, I'm curious if this translates to real gains for real architectures. FFT makes use of imaginary numbers to encode the harmonics of the signal, these are generally not amenable to gpu architectures. Would fast walsh hadamard suffice? Sometimes the 'signal mixing'…

Complex numbers work just fine on a GPU. You just represent the data as a real-part matrix and an imaginary-part matrix and do the (ac-bd)+(ad+bc)i stuff in matrix land instead of on complex scalars.

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#67

Post by Y_Y »

leecarraher wrote: post #63

this seems to follow the similar FNO work by nvidia, and switching to frequency domain is usually in any computer scientist's toolbox at this point, however, I'm curious if this translates to real gains for real architectures. FFT makes use of imaginary numbers to encode the harmonics of the signal, these are generally not amenable to gpu architectures. Would fast walsh hadamard suffice? Sometimes the 'signal mixing'…

What's wrong with complex numbers on GPUs? You don't have to do anything special. It's obviously faster if you can make simplifying assumptions like "the input signal is purely real" but otherwise at worst you're dealing with pairs of reals (or floats) and don't have to think about philosophical implications.

https://docs.nvidia.com/cuda/cufft/

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#68

Post by Y_Y »

markisus wrote: post #47

The Fourier transform is taken along the “token” dimension. However, in many applications, this dimension is not meaningful. That’s why transformers are a great option for consuming data which is permutation invariant. I would like to see additional experiments using the lesser known Fourier transform over finite groups [1], which is permutation invariant but shares many properties with the standard Fourier transform…

What's the finite group in this case?

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#69

Post by ambicapter »

xeonmc wrote: post #7

Basically leverages convolution theorem[0]: expensive convolutions in direct space becomes simple multiplications in reciprocal space, and vice versa. Whereever you have a convolution operation on your data, transform them to the conjugate domain to turn it into multiplication. In other words, work in the domain that is natural to your data. [0] https://en.wikipedia.org/wiki/Convolution_theorem

> In other words, work in the domain that is natural to your data.

Why would multiplication be more "natural" to a domain than convolution, as opposed to just simpler to calculate?

Re: The FFT Strikes Back: An Efficient Alternative to Self-Attention

#70

Post by ipunchghosts »

ipunchghosts wrote: post #40

This guy's has had a lot bangers lately.

Overall, i like this guys papers but they strike me as someone who is very smart but hasnt looked through the literature carefully. Many of the techniques he is proposing were already done about 5-6 years ago. However, I imagine that because the field is flooded with new humans, they are not aware of this research or think it will lead to a fruitful end (which many other researchers have already thought of this and it didn't lead anywhere hence why it was abandoned). Overall, it seems we are starting to recycle ideas because there isnt enough lit review and or mentoring from senior deep learning / ML folks who can quickly look at a paper and tell the author where the work has been already investigated.
Post reply on HN