  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 oft-considered set of block frequency sparse functions of
the form $$f(x) = \sum^{n}_{j=1} \sum^{B-1}_{k=0} c_{\omega_j + k}
e^{i(\omega_j + k)x},~~\{ \omega_1, \dots, \omega_n \} \subset
\left(-\left\lceil \frac{N}{2}\right\rceil, \left\lfloor
\frac{N}{2}\right\rfloor\right]\cap\mathbb{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.
