Hacker News Reader

Comment by ktpsns | Hacker News Reader

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 or https://www.gnu.org/software/gsl/doc/html/fft.html . This is not trivial.

View on HN

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.

Application of DFT (or variants) is non-trivial. DFT itself is just a matrix multiply.

And FFT is “just” a special factorization of the DFT matrix.

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.

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.

Reply on news.ycombinator.com