Notes on the discrete Fourier transform (DFT) (eli.thegreenplace.net)
87 points by kouosi 14 hours ago
perlgeek 3 hours ago
DFT works great if you have a single with equal spacing in the time domain (e.g. you have a microphone, and you measure the signal every 1/20k s or so).
If that's not the case, rather than interpolating into a time grid, it's often better to use a generalization of the DFT called the "Lomb-Scargle Periodogram".
For example if you have a periodic process like measuring the distance between two planets, but you only get measurements at random timestamps, that's the way to go.
See for example https://docs.astropy.org/en/stable/timeseries/lombscargle.ht...
geokon 27 minutes ago
I get the sense that in many cases newer methods like compressed sensing should produce much better results that periodograms. I'm not an expert in this, but I see a lot of periodograms in geological data - and you always get these broad frequency peaks which to me seem non-physical (maybe it's a plotting issue though? They plot it as a continuous result, when in reality it seems like it's discrete)
abnry 2 hours ago
There are four Fourier Transforms:
1. The (traditional) Fourier Transform for real-domain functions.
2. The Discrete Time Fourier Transform (DTFT) for integer-domain function.
3. The Continuous Time Fourier Transform (CTFT) for unit circle-domain (or periodic) functions, also known as Fourier Series decomposition.
4. The Discrete Fourier Transform (DFT) for finite integer domain functions.
You might say there are only three of these transforms because 2 and 3 are essentially, but not quite, inverses of each other.
But really there is only one Fourier transform. In a few senses actually. There's character theory which unites them all based on the (topology and group structure of the) function domain. So reals, integers, unit circle, and finite integers are the function example domains.
But another way they are all united is with distributions and dirac delta functions. The dirac comb is very important for understanding it. Any time you have a discrete series, represent it as dirac impulses and apply the normal Fourier Transform (operating on distributions) maps it to the other transforms.
You can represent the DFT as a periodic sequence of impulses and just apply the normal transform.
You can also interpret the DFT as the DTFT operating on a finitely supported discrete sequence. The math is the same but you just compute it at a finite grid in frequency space. This is why zero padding increases your frequency resolution or interpolates in the frequency domain.
nayuki 4 hours ago
I really enjoyed learning the different aspects of Fourier transforms from "The Scientist and Engineer's Guide to Digital Signal Processing", a free online book: https://www.dspguide.com/pdfbook.htm
slow_typist 13 hours ago
The matrix approach for calculating the DFT also gives us a nice way to proof that the DFT can always be inverted. We just need to show that matrix F is always (for any positive integer N) invertible.
That can be proved in a number of ways. E.g. showing that det(F)!=0 or showing linear independence of the columns of F is sufficient.
uecker 12 hours ago
The simplest way to show this is that the adjoint (complex transpose) DFT matrix is the inverse, so U^H U = I.
(For DFT there are different scaling conventions which may be taken into account.)
slow_typist 9 hours ago
Maybe not the simplest way but constructive proofs are always nice.
eliben 6 hours ago
Yes! It's discussed in the "Inverse DFT: reconstructing the signal" section, which relies on the earlier post https://eli.thegreenplace.net/2026/notes-on-the-complex-root...
lefra 13 hours ago
I like that this takes care not to conflate the DFT (the computed value), with the FFT (a family of algorithm to compute it).
brcmthrowaway 12 hours ago
During college, this guy had some banger articles. Had completely forgotten about the blog.
Now I check it and the burning question.. is it full of AI slop/psychosis (i.e. similar to the https://nullprogram.com guy..) Seems to have escaped the scourge.
Likely made enough $ at GOOG to retire.
eliben 6 hours ago
All posts are 100% written by me.
AI is very useful for brainstorming, checking the math, helping with some of the visualizations etc.
throwaway2046 3 hours ago
I don't see any AI writing on nullprogram, what makes you say that?