4 ms·

If you’re new to signal processing, then just remember that the basic algorithm of spectral analysis is the DFT and the FFT is just a clever way to compute it b

If you’re new to signal processing, then just remember that the basic algorithm of spectral analysis is the DFT and the FFT is just a clever way to compute it by skipping all the redundant operations. The DFT is trivial.

joppy 5y ago
Trivial, or just straightforward? I don’t think that it’s trivial to know why multiplying by this powers-of-roots-of-unity matrix is interesting, and does the things that it does.
- hasmanean 5y ago
  The Correlation of two signals a and b is just multiplying them (if they are vectors, multiply each element of a by the corresponding element of b) Corr(a,b) = sum(a. * b) The correlation of a signal s with a sine wave of frequency f just gives the signal power at that frequency. Repeat for a set of regularly spaced of frequency values from 0 to Fs/2 (the maximum frequency you can work with with data sampled at Fs) and you have the DFT. You can even clump the sine waves into a matrix and your DFT gets reduced to a single matrix multiply. This is much easier to reason about than worrying about how an FFT works which is just a speed optimization (which can be derived from dynamic programming applied to the DFT). For someone doing signal processing the results are the same. Introducing the FFT without making reference to the DFT is wrapping the subject up in an air of mystery.
ktpsns 5y ago
The DFT is not trivial at all. The standard way of teaching goes over calculus (including complex numbers), introduces the original Fourier transformation and then discretization (numerical mathematics). Having a PhD in physics, let me assert you that we still have to think twice many times when we "just do a dft" of something. This is also obvious if you look into the manuals, for instance the many variants of a FFT in https://docs.scipy.org/doc/scipy/reference/tutorial/fft.html https://docs.scipy.org/doc/scipy/reference/tutorial/fft.html or https://www.gnu.org/software/gsl/doc/html/fft.html https://www.gnu.org/software/gsl/doc/html/fft.html . This is not trivial.
- llukas 5y ago
  Application of DFT (or variants) is non-trivial. DFT itself is just a matrix multiply.
  - dls2016 5y ago
    And FFT is “just” a special factorization of the DFT matrix.
- rrss 5y ago
  sure, that’s the standard way of teaching and is useful background, but you don’t need calculus or the continuous Fourier transform to come up with or understand the DFT. Once you know what a basis is for a finite dimensional vector space, the DFT is a straightforward change of basis to a particularly useful set of basis vectors which are easy to write down. The manuals you cite cover several different transforms (not just the DFT) as well as the complexities of the FFT.
  - hasmanean 5y ago
    Or more generally, it’s the correlation of your signal with a set of sine waves of different frequencies. It doesn’t have to be a sine wave. You could correlate your signal to a fart sound (or a set of them). It’s a valid transform but it would not be invertible—given a vector of scalar values showing how much your signal resembled each type of fart, you could not reconstruct the original signal. However you can do that with the FT. It’s invertible and you can recover the signal from the spectrum. So in some sense it doesn’t lose information. Energy in the signal is equal to energy in the Fourier spectrum.
- hasmanean 5y ago
  Yes I know, I used to do research in signal processing. Part of that complexity is because the FFT only works on power-of-2 length (e.g. 1024) input vectors so they have special tricks to work with arbitrary length data. The DFT has no such restriction. I’ve read somewhere that if you apply dynamic programming to the DFT (recursive sub problems, memoization) then you end up with the FFT. One of these days I’ll try to derive that.

joppy 5y ago

Trivial, or just straightforward? I don’t think that it’s trivial to know why multiplying by this powers-of-roots-of-unity matrix is interesting, and does the things that it does.

hasmanean 5y ago
The Correlation of two signals a and b is just multiplying them (if they are vectors, multiply each element of a by the corresponding element of b) Corr(a,b) = sum(a. * b) The correlation of a signal s with a sine wave of frequency f just gives the signal power at that frequency. Repeat for a set of regularly spaced of frequency values from 0 to Fs/2 (the maximum frequency you can work with with data sampled at Fs) and you have the DFT. You can even clump the sine waves into a matrix and your DFT gets reduced to a single matrix multiply. This is much easier to reason about than worrying about how an FFT works which is just a speed optimization (which can be derived from dynamic programming applied to the DFT). For someone doing signal processing the results are the same. Introducing the FFT without making reference to the DFT is wrapping the subject up in an air of mystery.

ktpsns 5y ago

The DFT is not trivial at all. The standard way of teaching goes over calculus (including complex numbers), introduces the original Fourier transformation and then discretization (numerical mathematics). Having a PhD in physics, let me assert you that we still have to think twice many times when we "just do a dft" of something. This is also obvious if you look into the manuals, for instance the many variants of a FFT in https://docs.scipy.org/doc/scipy/reference/tutorial/fft.html https://docs.scipy.org/doc/scipy/reference/tutorial/fft.html or https://www.gnu.org/software/gsl/doc/html/fft.html https://www.gnu.org/software/gsl/doc/html/fft.html . This is not trivial.

llukas 5y ago
Application of DFT (or variants) is non-trivial. DFT itself is just a matrix multiply.
- dls2016 5y ago
  And FFT is “just” a special factorization of the DFT matrix.
rrss 5y ago
sure, that’s the standard way of teaching and is useful background, but you don’t need calculus or the continuous Fourier transform to come up with or understand the DFT. Once you know what a basis is for a finite dimensional vector space, the DFT is a straightforward change of basis to a particularly useful set of basis vectors which are easy to write down. The manuals you cite cover several different transforms (not just the DFT) as well as the complexities of the FFT.
- hasmanean 5y ago
  Or more generally, it’s the correlation of your signal with a set of sine waves of different frequencies. It doesn’t have to be a sine wave. You could correlate your signal to a fart sound (or a set of them). It’s a valid transform but it would not be invertible—given a vector of scalar values showing how much your signal resembled each type of fart, you could not reconstruct the original signal. However you can do that with the FT. It’s invertible and you can recover the signal from the spectrum. So in some sense it doesn’t lose information. Energy in the signal is equal to energy in the Fourier spectrum.
hasmanean 5y ago
Yes I know, I used to do research in signal processing. Part of that complexity is because the FFT only works on power-of-2 length (e.g. 1024) input vectors so they have special tricks to work with arbitrary length data. The DFT has no such restriction. I’ve read somewhere that if you apply dynamic programming to the DFT (recursive sub problems, memoization) then you end up with the FFT. One of these days I’ll try to derive that.