▲ 309 points
back
158 comments
My favorite story about the Fourier Transform is that Carl Friedrich Gauss stumbled upon the algorithm for the Fast Fourier Algorthim over a century before Cooley and Tukey’s publication in 1965 (which itself revolutionized digital signal processing).[1] He was apparently studying the motion of the asteroids Pallas and Juno and wrote the algorithm down in his notes but it never made it into public knowledge.
[1] https://www.cis.rit.edu/class/simg716/Gauss_History_FFT.pdf
There is a saying about Gauss: when another mathematician came to show him a new result, Gauss would remark that he had already worked on it, open a drawer in his desk, and pull out a pile of papers on the same topic.
Gauss's notes and margins is riddled with proofs he didn't bother to publish - he was wild.
Not sure if true, but allegedy he insisted his son not go into maths, as he would simply end up in his father's shadow as he deemed it utterly Impossible to surpass his brilliance in maths :'D
When I interned at Chevron someone said they (or some other oil company) were using Fourier transforms in the 1950's for seismic analysis but kept it a secret for obvious reasons. I think you couldn't (can't?) patent math equations.
Gauss is gonna Gauss.
How was Gauss so productive with 6 children?
People go all dopey eyed about "frequency space", that's a red herring. The take away should be that a problem centric coordinate system is enormously helpful.
After all, what Copernicus showed is that the mind bogglingly complicated motion of planets become a whole lot simpler if you change the coordinate system.
Ptolemaic model of epicycles were an adhoc form of Fourier analysis - decomposing periodic motions over circles over circles.
Back to frequencies, there is nothing obviously frequency like in real space Laplace transforms *. The real insight is that differentiation and integration operations become simple if the coordinates used are exponential functions because exponential functions remain (scaled) exponential when passed through such operations.
For digital signals what helps is Walsh-Hadamard basis. They are not like frequencies. They are not at all like the square wave analogue of sinusoidal waves. People call them sequency space as a well justified pun.
My suspicion is that we are in Ptolemaic state as far as GPT like models are concerned. We will eventually understand them better once we figure out what's the better coordinate system to think about their dynamics in.
* There is a connection though, through the exponential form of complex numbers, or more prosaically, when multiplying rotation matrices the angles combine additively. So angles and logarithms have a certain unity, or character.
All these transforms are switching to an eigenbasis of some differential operator (that usually corresponds to a differential equation of interest). Spherical harmonics, Bessel and Henkel functions, which are the radial versions of sines/cosines and complex exponential, respectively, and on and on.
The next big jumps were to collections of functions not parameterized by subsets of R^n. Wavelets use a tree shapes parameter space.
There’s a whole, interesting area of overcomplete basis sets that I have been meaning to look into where you give up your basis functions being orthogonal and all those nice properties in exchange for having multiple options for adapting better to different signal characteristics.
I don’t think these transforms are going to be relevant to understanding neural nets, though. They are, by their nature, doing something with nonlinear structures in high dimensions which are not smoothly extended across their domain, which is the opposite problem all our current approaches to functional analysis deal with.
> My suspicion is that we are in Ptolemaic state as far as GPT like models are concerned. We will eventually understand them better once we figure out what's the better coordinate system to think about their dynamics in.
Most deep learning systems are learned matrices that are multiplied by "problem-instance" data matrices to produce a prediction matrix. The time to do said matrix-multiplication is data-independent (assuming that the time to do multiply-adds is data-independent).
If you multiply both sides by the inverse of the learned matrix, you get an equation where finding the prediction matrix is a solving problem, where the time to solve is data dependent.
Interestingly enough, that time is sort-of proportional to the difficulty of the problem for said data.
Perhaps more interesting is that the inverse matrix seems to have row artifacts that look like things in the training data.
These observations are due to Tsvi Achler.
I feel like this is the way we should have learned Fourier and Laplace transforms in my DSP class. Not just blindly applying formulas and equations.
> exponential functions remain (scaled) exponential when passed through such operations.
See also: eigenvalue, differential operator, diagonalisation, modal analysis
It’s kind of intriguing that predicting the future state of any quantum system becomes almost trivial—assuming you can diagonalize the Hamiltonian. But good luck with that in general. (In other words, a “simple” reference frame always exists via unitary conjugation, but finding it is very difficult.)
A signal cannot be both time and frequency band limited. Many years ago I was amazed when I read that this fact I learned in my undergraduate is equivalent to the Uncertainty Principle!
On a more mundane note: my wife and I always argue whose method of loading the dishwasher is better: she goes slow and meticulously while I do it fast. It occurred to me we were optimizing for frequency and time domains, respectively, ie I was minimizing time so spent while she was minimizing number of washes :-)
Signals can be approximately frequency and time bandlimited, though, meaning the set of values such that the absolute value exceeds any epsilon is compact in both domains. A Gaussian function is one example.
It’s literally the Heisenberg uncertainty principle, applied to signal processing.
Another example: ears are excellent at breaking down the frequency of sounds, but are imprecise about where the sound is coming from; whereas eyes are excellent at telling you where light is coming from, but imprecise about how its frequencies break down.
> I was minimizing time so spent while she was minimizing number of washes
I'm probably just slow, but I'm not following. Do you mean because you went fast, you had to run another cycle to clean everything properly?
If you haven't already, you should watch the Technology Connections series on dishwashers.
The self loading dishwasher would be the greatest marriage saving invention since car navigation systems.
Once you start looking at the world through the lens of frequency domain a lot of neat tricks become simple. I have some demo code that uses fourier transform on webcam video to read a heartrate off a person's face, basically looking for what frequency holds peak energy.
It's effectively the underpinning of all modern lossy compression algorithms. The DCT which underlies codecs like Jpeg, h264, mp3, is really just a modified FFT.
>Once you start looking at the world through the lens of frequency domain a lot of neat tricks become simple.
Not the first time I've heard this on HN. I remember a user commenting once that it was one of the few perspective shifts in his life that completely turned things upside down professionally.
There is also a loose analogy with finance: act (trade) when prices cross a certain threshold, not after a specific time.
I don't think pulsing skin (due to blood flow) is visible from a webcam though.
I would heartily recommend Sebastian Lague's latest video, which covers this in a very approachable way: https://www.youtube.com/watch?v=08mmKNLQVHU
Okay, who's gonna write the story
> The unreasonable effectiveness of The Unreasonable Effectiveness title?
It's a play on the famous essay 1960 "The Unreasonable Effectiveness of Mathematics in the Natural Sciences".
I agree this is getting old after 75 years. Not least because it seems slightly manipulative to disguise a declarative claim ("The Fourier transform is unreasonably effective."), which could be false, as a noun phrase ("The unreasonable effectiveness of the Fourier transform"), which doesn't look like a thing that can be wrong.
Unreasonable effectiveness is all you need.
Given how much of the talk is about the original paper the title references, and how the Fourier transform turns out to be unreasonably effective at allowing communication over noisy channels, I'd say it's a reasonable reference.
The Antipode of unreasonable effectiveness ness
Agreed, these kind of titles are very silly.
FTs are actually very reasonable, in the sense that they are a easy to reason about conceptually and in practice.
There's another title referenced in that link which is equally asinine: "Eugene Wigner's original discussion, "The Unreasonable Effectiveness of Mathematics in the Natural Sciences". "
Like, wtf?
Mathematics is the language of science, science would not compound or be explainable, communicable, or model-able in code without mathematics.
It's actually both plainly obvious for mathematics then to be extremely effective (which it is) and also be evidently reasonable as to why, ergo it is not unreasonably effective.
Also the slides are just FTs 101 the same material as in any basic course.
How about The unreasonable effectiveness title considered harmful?
The Unreasonable Effectiveness of LLMs.
Ironically a very relevant and accurate title.
If you are from ML/Data science world, the analogy that finally unlocked FFT for me is feature size reduction using Principal Component Analysis. In both cases, you project data to a new "better" co-ordinate system ("time to frequency domain"), filter out the basis vectors that have low variance ("ignore high-frequency waves"), and project data back to real space from those truncated dimension ("Ifft: inverse transform to time domain").
Of course some differences exist (e.g. basis vectors are fixed in FFT, unlike PCA).
My biggest missing feature for Grafana is that I want a Fourier transform that can identify epicycles in spikes of traffic. Like the first Monday of the month, or noon on tuesdays.
I had a couple charts that showed a trend line of the last n days until someone in OPs noticed that three charts were fully half of our daily burn rate for Grafana. Oops. So I started showing a -7 days line instead, which helped me but confused everyone else.
That wouldn't really work well because the sparsity of the periodic spikes wouldn't fit the assumption that the signal has a frequency component 'everywhere', even though it's periodic. You can see that mathematically - if you take the Fourier transform of an impulse signal you get a smeared result in frequency space.
You'd probably want to use a tool like calculating the cepstrum rather than fourier transform. Cepstral methods are commonly used in mechanical analysis to detect periodic impacts like where a gear tooth gets damaged.
I dont like the Fourier Transform. It is infinite which makes it coarse and rough and it it gets everywhere.
Anybody who does anything in the real world with Fourier transforms uses the fast Fourier transform operating on windowed data. This eliminates all of that infinite support and infinite resolution of frequencies.
Not sure if an oblaque tomb raider reference or math metaphor.
not like here.
Moreover, The Unreasonable Effectiveness of Linear, Orthogonal Change of Basis.
You are spot on.
Too bad -- the article doesn't mention Gauss. The Fourier transform is best presented to students in its original mathematical form, then coded in the FFT form. It also serves as a practical introduction to complex numbers.
As to the listed patent, it moves uncomfortably close to being a patent on mathematics, which isn't permitted. But I wouldn't be surprised to see many outstanding patents that have this hidden property.
Pretty sure in the USA you can patent mathematics if it is an integral part of the realisation of a physical system.* There is a book "Math you Can't Use" that discusses this.
* not a legal definition, IANAL.
This talk was given at crowd supply’s 2025 teardown convention which after going for the first time last year I highly recommend it to anyone interested in hardware development. Met a lot of super cool people and managed to get my ticket price back 4x in the amount of free dev boards I got lol
Learning about the Fourier Transform in my Signals and Systems class was mind opening. The idea you can represent any cycling function with sinusoidal functions would not only never occur to me but I would have said it wasn't possible.
So he explains OFDM in a way that implicitly does Amplitude shift keying.
I guess if you want to use different modulations you treat the complex number corresponding to the subcarrier as an IQ point in quadrature. So you take the same symbols, but read them off in the frequency domain instead of the time domain.
And I guess this works out quite equivalently to normally modulating these symbols at properly offset frequencies (just by the superposition principle)
At the time of his death by a Roman soldier the ancient mathematician Archimedes is said to yell: Don't disturb my circles, while he was calculating on sand. Much later, a few years ago, one of his handbooks, an overwritten palimpsest, was found to contain elements of modern calculus. If both these concepts where saved and spread through the middle ages, human civilisation might have been developed 1000 years earlier.