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

71–80 of 175 posts

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

#71

Post by MajimasEyepatch »

ambicapter wrote: post #69
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?

As an example, if you're trying to "smooth out" some signal, what you're really trying to do is remove the high frequency components. So using a Fourier transform to convert it to the frequency domain lets you directly work with the frequency data, rather than indirectly in the time/space/whatever domain. The fact that the operation is simpler in the frequency domain is a good hint that you've picked the "natural" space in which to look at the problem. Of course, there's no formal definition of "naturalness," and at the end of the day, you get the same result either way.

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

#72

Post by tonetegeatinst »

I sort of grasp big O notation...but this is sort of over my head like most stuff that has to do with computer or electrical engineering.

As someone who is absolutely terrible at math, I envy the people who grasp or at least can learn this type of stuff and get an engineering degree and license.

All I really know about FFT is that is changes a signal, its somehow used in processing signals of some kind, and it apparently from what I heard was the key to detecting nuclear detonations back in the day.

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

#73

Post by dilawar »

tonetegeatinst wrote: post #72

I sort of grasp big O notation...but this is sort of over my head like most stuff that has to do with computer or electrical engineering. As someone who is absolutely terrible at math, I envy the people who grasp or at least can learn this type of stuff and get an engineering degree and license. All I really know about FFT is that is changes a signal, its somehow used in processing signals of some kind, and it appare…

https://m.youtube.com/watch?v=spUNpyF58BY

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

#74

Post by markisus »

Y_Y wrote: post #68
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?

I’m thinking the integers mod 2^n where n is something computers are good at (8, 32, 64). You have hardware support the group operation.

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

#75

Post by yorwba »

markisus wrote: post #74
Y_Y wrote: post #68

Earlier quoted context omitted.

What's the finite group in this case?

I’m thinking the integers mod 2^n where n is something computers are good at (8, 32, 64). You have hardware support the group operation.

That is the traditional Fourier transform, except it can be a cyclic group of any size, doesn't need to be a power of 2. (Though FFTs with 2^n input size are particularly easy to implement.)

And it's not permutation invariant.

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

#76

Post by addaon »

thijson wrote: post #61
bee_rider wrote: post #39

Earlier quoted context omitted.

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.

Yeah, bit-reversed addressing mode as seen on the dsPIC is an example of this.

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

#77

Post by MajimasEyepatch »

tonetegeatinst wrote: post #72

I sort of grasp big O notation...but this is sort of over my head like most stuff that has to do with computer or electrical engineering. As someone who is absolutely terrible at math, I envy the people who grasp or at least can learn this type of stuff and get an engineering degree and license. All I really know about FFT is that is changes a signal, its somehow used in processing signals of some kind, and it appare…

Having a decent intuitive notion of Fourier transforms is an incredibly useful tool in your toolbox, even if you can't derive a Fourier transform by hand or write a fast Fourier transform (FFT) algorithm.

The basic idea is this: (almost) any (useful) signal can be represented as a sum of sine waves with different frequencies and phases. For example, an electrical signal or a sound wave is a one-dimensional signal where the x-axis is time. This might look like a really complex squiggly line that's hard to work with. Using a Fourier transform, you can separate the individual frequencies of that time-based signal. Then, you can modify the specific frequencies however you want. For example, if you have a lot of random, spiky noise in the signal, that will show up as high frequencies. To clean it up, just do a Fourier transform, throw out any data with a frequency above a certain threshold, and then run an inverse Fourier transform on the remaining data to get back a smoother version of the original signal. This is called a low-pass filter, and it's more or less equivalent to taking a moving average of the original signal.

Where it gets really fun is that you can extend this, in a pretty straightforward way, to higher dimensions. A two-dimensional signal, where both the x- and y-axes are space, is just an image. JPEG compression is based on this concept: it removes the high-frequency signal in the image in order to store the data in a more compact form, at the expense of losing some fine detail (or creating those ring-like artifacts, if you throw out too much data). Add a third dimension for time, and now you have video. And so on.

The nice thing about all this is that it's very visual, so you can get a good intuition for it without having to know all the math inside and out. Here's a good page with lots of visualizations and interactive examples: https://www.jezzamon.com/fourier/index.html

And this 3Blue1Brown video does a good job of explaining it: https://youtu.be/spUNpyF58BY?si=dz0z-s8NftW3Htun

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

#78

Post by bigmattystyles »

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

Is reciprocal space always just 1/space as in frequency=1/t?

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

#79

Post by amelius »

ambicapter wrote: post #69
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?

I think they just meant simpler to calculate.

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

#80

Post by amelius »

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

Reminds me how CNNs were also not implemented using FFTs.
Post reply on HN