کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4604937 | 1631329 | 2016 | 22 صفحه PDF | دانلود رایگان |
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.
Journal: Applied and Computational Harmonic Analysis - Volume 40, Issue 3, May 2016, Pages 553–574