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.
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 n2 arithmetic operations.
