4 ms·

where would be the use cases for FFT ? I'm a newbie.

by m00dy 4y ago

amirhirsch 4y ago
FFT (“Fast Fourier Transform”) accelerates the computation of the Fourier Transform from the naive O(N^2) algorithm to O(N lg N) using divide and conquer. Because of the “Convolution Theorem” which says “convolution in the time domain is multiplication in frequency domain” the FFT allows you to compute the convolution of two vectors by performing: (1) two O(N lg N) FFTs, (2) one O(N) product in the spectral domain, (3) and one O(N lg N) inverse FFT. This is a asymptotic speed up over the naive O(N^2) convolution. Convolution is the mathematical operation used to compute linear filters, correlate two signals, and multiply polynomials. For example, if you have a string of length M and want to find copies of it in another string of length N, the FFT blows away the O(NM) naive approach (for big enough M).
JKCalhoun 4y ago
As has been pointed out, a music visualizer is an obvious use-case. Audio data (via microphone) digitized in real-time and sampled by the Arduino is necessarily in the in the "time domain". To bucket the audio into frequency bands (perhaps your visualizer is simple and just wants to light up LEDs relative to the amplitude of low, mid and high frequencies) you need to run that time-domain data through an FFT to get frequency-domain data out of it.
yunruse 4y ago
If you have 26 minutes spare, Veritaserum's video [0] on the history of FTs and FFTs is quite good. Effectively, a Fourier Transform can turn a signal into its underlying frequencies using a neat property of maths. For a piece of music, say, you could produce a spectrogram [1] – Foobar2000 [2] has a nice one built in – to visualise the frequency of music with time. In general, this is all sorts of useful applications any time you have a signal – electronics, climate physics, astrophysics, detecting nuclear explosion testing underground, and so on. It's essential to modern medical imaging, and a whole bunch of differential equations can be solved a lot faster by using this. The FFT takes the naive O(N^2) algorithm and makes it O(n log n) by bunching together repeated calculations, so if you have a million samples, that's some 70,000 times faster. At the time of its discovery it was critical for Fourier analysis to actually be reasonable to do on a computer, taking days instead of years. [0] https://www.youtube.com/watch?v=nmgFG7PUHfo https://www.youtube.com/watch?v=nmgFG7PUHfo [1] https://en.wikipedia.org/wiki/Spectrogram https://en.wikipedia.org/wiki/Spectrogram [2] https://www.foobar2000.org https://www.foobar2000.org
borodi 4y ago
Veritasium has a recent video that goes into the algorithm a little bit. So does 3blue1brown. But basically anything that processes signals digitally will probably use the FFT somewhere. But even outside of that, you can use it for some kinds of matrixes in linear algebra and probably many other places :)

where would be the use cases for FFT ? I'm a newbie.

by m00dy 4y ago

where would be the use cases for FFT ? I'm a newbie.

FFT (“Fast Fourier Transform”) accelerates the computation of the Fourier Transform from the naive O(N^2) algorithm to O(N lg N) using divide and conquer. Because of the “Convolution Theorem” which says “convolution in the time domain is multiplication in frequency domain” the FFT allows you to compute the convolution of two vectors by performing: (1) two O(N lg N) FFTs, (2) one O(N) product in the spectral domain, (3) and one O(N lg N) inverse FFT. This is a asymptotic speed up over the naive O(N^2) convolution. Convolution is the mathematical operation used to compute linear filters, correlate two signals, and multiply polynomials. For example, if you have a string of length M and want to find copies of it in another string of length N, the FFT blows away the O(NM) naive approach (for big enough M).

JKCalhoun 4y ago

As has been pointed out, a music visualizer is an obvious use-case. Audio data (via microphone) digitized in real-time and sampled by the Arduino is necessarily in the in the "time domain". To bucket the audio into frequency bands (perhaps your visualizer is simple and just wants to light up LEDs relative to the amplitude of low, mid and high frequencies) you need to run that time-domain data through an FFT to get frequency-domain data out of it.

yunruse 4y ago

If you have 26 minutes spare, Veritaserum's video [0] on the history of FTs and FFTs is quite good. Effectively, a Fourier Transform can turn a signal into its underlying frequencies using a neat property of maths. For a piece of music, say, you could produce a spectrogram [1] – Foobar2000 [2] has a nice one built in – to visualise the frequency of music with time. In general, this is all sorts of useful applications any time you have a signal – electronics, climate physics, astrophysics, detecting nuclear explosion testing underground, and so on. It's essential to modern medical imaging, and a whole bunch of differential equations can be solved a lot faster by using this. The FFT takes the naive O(N^2) algorithm and makes it O(n log n) by bunching together repeated calculations, so if you have a million samples, that's some 70,000 times faster. At the time of its discovery it was critical for Fourier analysis to actually be reasonable to do on a computer, taking days instead of years. [0] https://www.youtube.com/watch?v=nmgFG7PUHfo https://www.youtube.com/watch?v=nmgFG7PUHfo [1] https://en.wikipedia.org/wiki/Spectrogram https://en.wikipedia.org/wiki/Spectrogram [2] https://www.foobar2000.org https://www.foobar2000.org

borodi 4y ago

Veritasium has a recent video that goes into the algorithm a little bit. So does 3blue1brown. But basically anything that processes signals digitally will probably use the FFT somewhere. But even outside of that, you can use it for some kinds of matrixes in linear algebra and probably many other places :)