← All Cracked Math projects
PM-B11NOT STARTEDBEGINNERMATHPYTHONIMPACT ★★☆☆☆

A hand-written FFT that denoises a real recording

Recursive, then iterative, then any length: write your own FFT and use it on real audio.

EST.7 h
REWARD+200 XP
AFTERJez Swanson

ML-ARENA BENCHMARKS

PROOF: BENCH
METRICINDUSTRYMINE
Max abs error vs numpy.fft and wall time at n = 2^20 complex points; FFT-convolution speedup
GOAL · Error <= 1e-9 * log2(n) relative to the signal norm. Within 10x of numpy.fft's time at 2^20. FFT convolution >= 100x faster than np.convolve at 2^18 taps (filter length).
numpy.fft (pocketfft) · measured locally—
no results yet
YOUR RESULTS

Your recorded results appear here.

Brief

The FFT (fast Fourier transform) splits a signal into its frequency components in O(n log n) time instead of O(n^2). Implement a recursive radix-2 FFT, which halves the problem at each step and so needs a power-of-2 length. Then write an iterative, in-place, vectorised version with bit-reversal (the reordering of the inputs that the iterative version needs). Add a Bluestein path for lengths that are not powers of 2 (it rewrites an FFT of any length as a convolution that can use power-of-2 FFTs). Use your FFT for spectral-subtraction denoising of a voice recording (estimate the noise spectrum and subtract it from each frame), and for FFT convolution via the convolution theorem (convolution in time equals multiplication of spectra).

VICTORY CONDITIONS

  1. Error <= 1e-9 * log2(n) relative to the signal norm. Within 10x of numpy.fft's time at 2^20. FFT convolution >= 100x faster than np.convolve at 2^18 taps (filter length). (Max abs error vs numpy.fft and wall time at n = 2^20 complex points; FFT-convolution speedup).
  2. A public repository with a README that shows your result and how to reproduce it.

Terms in plain words

Radix-2 FFT
An FFT that splits the input into even and odd samples at each level, so it works on lengths that are powers of 2.
Bit-reversal permutation
Reordering the inputs by reversing the binary digits of each index, which lets the FFT run in place without recursion.
Bluestein's algorithm
A way to compute an FFT of any length by turning it into a convolution, which is then done with power-of-2 FFTs.
Convolution theorem
The fact that convolving two signals is the same as multiplying their Fourier transforms, which makes long convolutions fast.
Spectral subtraction
A denoising method that estimates the noise's frequency content and subtracts it from each short frame of the signal.

Why it rates ★★☆☆☆

Everyone writes an FFT once. Doing Bluestein plus a real application shows care.