3 ms·

I've been thinking a lot about how to apply FFTs to neural networks, so this is timely; thank you. If you're looking for deeper explanations, I recommend "Prac

I've been thinking a lot about how to apply FFTs to neural networks, so this is timely; thank you. If you're looking for deeper explanations, I recommend "Practical Signal Processing": https://www.amazon.com/Practical-Signal-Processing-Mark-Owen/dp/1107411823 https://www.amazon.com/Practical-Signal-Processing-Mark-Owen... Many of the chapters are here: https://battle.shawwn.com/sdb/books/PSP/ https://battle.shawwn.com/sdb/books/PSP/ but buy the book if you can afford to. In particular, Chapter 4's "untwisting" intuition is the best I've found: https://imgur.com/a/r7KvO60 https://imgur.com/a/r7KvO60 Another way of phrasing it: You know that effect when a wheel is spinning so fast, it looks like it's going backwards? If it looks like it's standing still, there's a Fourier coefficient at that rotational frequency. ... Or at least, I think there is. It's hard to be precise with analogies.

tracyhenry 5y ago
Google's FNet seems to apply FT to NNs? https://arxiv.org/abs/2105.03824 https://arxiv.org/abs/2105.03824
- sillysaurusx 5y ago
  That paper was one of the most misleading papers I've ever seen in NNs. https://twitter.com/theshawwn/status/1393315603973386240 https://twitter.com/theshawwn/status/1393315603973386240 Like many others, I was hyped when it came out. Then it turns out that BERT with half the param count still kicks their butts in accuracy. They also only model the .real component and ignore the .imaginary component entirely, which you can't do and expect good results. But, FFTs are so cool and under-explored that I'm sure they'll be making the rounds in NNs soon. There are lots of advantages to frequency space representations.
  - kortex 5y ago
    I don't understand why the first operations of a CNN are FFT-based decomposition into spatial wavelets. This is basically all the first layers are doing anyways. In fact the filters usually learn both an edge and a centroid at a given orientation. You can get both at the same time with complex wavelets.
obastani 5y ago
There has been some interesting recent work [1] applying Fourier transforms (more precisely, an adaptation of the Fourier transform to the sphere) to CNNs, to automatically encode equivariance to rotational symmetries. [1] https://arxiv.org/abs/1711.06721 https://arxiv.org/abs/1711.06721
mhh__ 5y ago
Proakis's book is quite good if you want to really nail down the fundamentals of the mathematics, but it's completely detached from applications and intuition despite what the cover (I suspect this is because the author has a different book on communication theory) says, so I'm not a huge fan of it.
37ef_ced3 5y ago
For neural nets, https://NN-512.com https://NN-512.com generates stand-alone C code vectorized Fourier convolutions that are 2x2 spatially strided (with a big 16x16 tile) This is great for large filter, 2x2 strided neural net convolutions (e.g., 7x7 stride 2x2) There's none of the waste you find elsewhere, in implementations that downsubsample the output of a dense (unstrided) Fourier convolution. I haven't seen this technique used anywhere else!

tracyhenry 5y ago

Google's FNet seems to apply FT to NNs? https://arxiv.org/abs/2105.03824 https://arxiv.org/abs/2105.03824

sillysaurusx 5y ago
That paper was one of the most misleading papers I've ever seen in NNs. https://twitter.com/theshawwn/status/1393315603973386240 https://twitter.com/theshawwn/status/1393315603973386240 Like many others, I was hyped when it came out. Then it turns out that BERT with half the param count still kicks their butts in accuracy. They also only model the .real component and ignore the .imaginary component entirely, which you can't do and expect good results. But, FFTs are so cool and under-explored that I'm sure they'll be making the rounds in NNs soon. There are lots of advantages to frequency space representations.
- kortex 5y ago
  I don't understand why the first operations of a CNN are FFT-based decomposition into spatial wavelets. This is basically all the first layers are doing anyways. In fact the filters usually learn both an edge and a centroid at a given orientation. You can get both at the same time with complex wavelets.

obastani 5y ago

There has been some interesting recent work [1] applying Fourier transforms (more precisely, an adaptation of the Fourier transform to the sphere) to CNNs, to automatically encode equivariance to rotational symmetries. [1] https://arxiv.org/abs/1711.06721 https://arxiv.org/abs/1711.06721

mhh__ 5y ago

Proakis's book is quite good if you want to really nail down the fundamentals of the mathematics, but it's completely detached from applications and intuition despite what the cover (I suspect this is because the author has a different book on communication theory) says, so I'm not a huge fan of it.

37ef_ced3 5y ago

For neural nets, https://NN-512.com https://NN-512.com generates stand-alone C code vectorized Fourier convolutions that are 2x2 spatially strided (with a big 16x16 tile) This is great for large filter, 2x2 strided neural net convolutions (e.g., 7x7 stride 2x2) There's none of the waste you find elsewhere, in implementations that downsubsample the output of a dense (unstrided) Fourier convolution. I haven't seen this technique used anywhere else!