We present a sublinear-time algorithm for computing the Fourier transform of a signal whose spectrum is approximately block-sparse.  Specifically, for a signal whose spectrum is approximated by $k_0$ blocks of width $k_1$, we prove a sample complexity of $O(k_0k_1 + k_0 log(1+k_0) log n)$ in the constant-SNR regime, thus strictly improving on the best-known $O(k log n)$ sample complexity for general $k$-sparse signals. 

Our algorithm is based on a novel energy-based importance sampling scheme that is inherently adaptive, meaning it uses previous samples to guide the selection of further samples.  While adaptivity may be viewed as weakness, we prove that it is in fact essential for achieving the above gains, by proving an $Omega( k_0k1 log(n/(k_0k_1)) )$ algorithm-independent lower bound for the non-adaptive case.