A multiscale sub-linear time Fourier algorithm for noisy data

We extend the recent sparse Fourier transform algorithm of [1] to the noisy setting, in which a signal of bandwidth N   is given as a superposition of k≪Nk≪N frequencies and additive random noise. We present two such extensions, the second of which exhibits a form of error-correction in its frequency estimation not unlike that of the β-encoders in analog-to-digital conversion [2]. On k  -sparse signals corrupted with additive complex Gaussian noise, the algorithm runs in time O(klog⁡(k)log⁡(N/k))O(klog⁡(k)log⁡(N/k)) on average, provided the noise is not overwhelming. The error-correction property allows the algorithm to outperform FFTW [3], a highly optimized software package for computing the full discrete Fourier transform, over a wide range of sparsity and noise values.