A deterministic sparse FFT for functions with structured Fourier sparsity

In this paper, a deterministic sparse Fourier transform algorithm is presented which breaks the quadratic-in-sparsity runtime bottleneck for a large class of periodic functions exhibiting structured frequency support. These functions include, e.g., the often considered set of block frequency sparse functions of the form f(x) = Sigma(n)(j=1)Sigma(B-1)(k=0) c(omega j)+k(ei()(omega j+k)x), {omega(1), ...,omega(n)} subset of (-inverted right perpendicular N/2 inverted left perpendicular, right perpendicular N/2 left perpendicular]boolean AND Z as a simple subclass. Theoretical error bounds in combination with numerical experiments demonstrate that the newly proposed algorithms are both fast and robust to noise. In particular, they outperform standard sparse Fourier transforms in the rapid recovery of block frequency sparse functions of the type above.