Hi there, argmin readers! Today’s post looks at part of OpenAI’s math repository that claims to compute faster Fourier transforms. It’s more technical than usual, but I tried to add some tutorial material for people who need a refresher course on signal processing or computational complexity.
The Fast Fourier Transform is one of the most important innovations in digital signal processing and one of my favorite algorithms. The FFT is a fast way to extract the frequency content of signals, letting you rapidly analyze, filter, and manipulate frequencies across different bands of the spectrum.
The Fourier transform computes the energy in each frequency band through a simple dot product. For digital signals, a bit of math shows you only need to compute n of these dot products, one at each multiple of the frequency 2π/n, to understand all of the frequency content. Naively, this requires n multiplications and additions for each frequency. Hence, computing the entire Fourier transform appears to require n² arithmetic operations.
The fast Fourier transform is a clever recursive procedure devised by James Cooley and John Tukey in 1965. Repeating this procedure iteratively log₂(n) times computes the full discrete Fourier transform in fewer than 5n log₂ n arithmetic operations.
Since the invention of the FFT, people have looked for even faster Fourier transforms. In the massive paper dump OpenAI took on the mathematics world last week, they claim to have a faster Fourier transform. The log(n) term, in theory, was a teeny tiny bit smaller than in the standard FFT.
Did I read this paper? Of course not. No one at OpenAI read this paper either, so why should I? I did what every other mathematician in the world does with AI slop mathematics: I fed it back into the slop machine and ran an information retrieval session with a chatbot interface to extract salient facts.
Unfortunately, I did not find a faster Fourier transform. Instead, I found the rot that develops inside applied mathematical theory when formalism becomes so detached from reality that a “breakthrough” is nothing more than an artifact of mathematicians not being able to properly specify the rules of their games in natural language.
Big-O notation allows for remarkable logical laziness. If we want a practically faster FFT, we want an algorithm that requires fewer than 50n operations for reasonably sized n. But O(n) does not mean 50n. It could mean 10⁸⁰n. Richard Lipton and Ken Regan call algorithms with unfathomably large hidden constants galactic algorithms.
The OpenAI FFT algorithm is definitely galactic. The estimated values for C were 10¹⁰⁰ when N=10¹². So even when n=10¹⁰⁰, the venerable Cooley-Tukey-Gauss FFT would be 10⁹⁹ times faster.
In big-O notation, it is technically asymptotically faster than the Cooley-Tukey algorithm because log(n) grows slower than log²(n). But given the constants, the algorithm runs faster only when n is impossibly large.
“The model uses exact complex arithmetic.” That means it assumes you can store and multiply complex numbers at arbitrary precision. The algorithm requires you to multiply complex numbers whose magnitudes grow superpolynomially with n. We do not have computers that can do this. So even if this theorem in main.pdf is “true”, it’s not actually solving the problem we set out to solve when looking for a faster FFT.
In 1973, Jacques Morgenstern proved that you couldn’t get a Fourier transform faster than ½n log n if you required that complex coefficients used in the computation had bounded magnitude. Forty years later, Nir Ailon showed that you couldn’t compute an FFT faster than n log n without severe numerical instabilities.
This new OpenAI result is thus less a mathematical breakthrough and more an oddity of computer scientists being bad at formalizing their design specifications. Many of the other “big” results in this OpenAI slopository could be critiqued in the same way. For example, one of those results was a galactic algorithm to multiply two matrices in O(n^2.25) operations.
Recht argues that the theory of computer science has a culture that actively discourages running algorithms on a computer, and that AI amplifies those tendencies by automating the production of useless theory papers.