An Adaptive Sublinear-Time Block Sparse Fourier Transform

Volkan Cevher, Michael Kapralov, Jonathan Scarlett +1

The problem of approximately computing the $k$ dominant Fourier coefficients of a vector $X$ quickly, and using few samples in time domain, is known as the Sparse Fourier Transform…