Sample Efficient Estimation and Recovery in Sparse FFT via Isolation on Average

Michael Kapralov

The problem of computing the Fourier Transform of a signal whose spectrum is dominated by a small number $k$ of frequencies quickly and using a small number of samples of the signa…