3 ms·

The DFT is not trivial at all. The standard way of teaching goes over calculus (including complex numbers), introduces the original Fourier transformation and t

by 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.

by ktpsns 5y ago

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.