  We extend the recent sparse Fourier transform algorithm of (Lawlor,
Christlieb, and Wang, 2013) to the noisy setting, in which a signal of
bandwidth N is given as a superposition of k << N frequencies and additive
noise. We present two such extensions, the second of which exhibits a novel
form of error-correction in its frequency estimation not unlike that of the
beta-encoders in analog-to-digital conversion (Daubechies et al, 2006). The
algorithm runs in time O(k log(k) log(N/k)) on average, provided the noise is
not overwhelming. The error-correction property allows the algorithm to
outperform FFTW, a highly optimized software package for computing the full
discrete Fourier transform, over a wide range of sparsity and noise values, and
is to the best of our knowledge novel in the sparse Fourier transform context.
