A multiscale sub-linear time Fourier algorithm for noisy data

作者：Christlieb Andrew; Lawlor David^*; Wang Yang

来源：Applied and Computational Harmonic Analysis, 2016, 40(3): 553-574.

DOI：10.1016/j.acha.2015.04.002

• Fast Fourier algorithms
• Multiscale algorithms
• Fourier analysis

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 << 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 beta-encoders in analog-to-digital conversion [2]. On k-sparse signals corrupted with additive complex Gaussian noise, 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 [3], a highly optimized software package for computing the full discrete Fourier transform, over a wide range of sparsity and noise values.

• 出版日期2016-5