A multiscale sub-linear time Fourier algorithm for noisy data

详细信息    查看全文

• 作者：Andrew Christlieb^a ; ¹ ; ^{christlieb@math.msu.edu" class="auth_mail" title="E-mail the corresponding author} ; David Lawlor^b ; ^c ; ^{djl@math.duke.edu" class="auth_mail" title="E-mail the corresponding author} ; Yang Wang^a ; ² ; ^{ywang@math.msu.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Fast Fourier algorithms ; Multiscale algorithms ; Fourier analysis
• 刊名：Applied and Computational Harmonic Analysis
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：40
• 期：3
• 页码：553-574
• 全文大小：621 K

文摘

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$k\ll 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))$\mathrm{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.