Name
Abstract | ||
|---|---|---|
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 β-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)) 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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1016/j.acha.2015.04.002 | Applied and Computational Harmonic Analysis |
Keywords | Field | DocType |
Fast Fourier algorithms,Multiscale algorithms,Fourier analysis | Noisy data,Superposition principle,Algorithm,Fourier transform,Bandwidth (signal processing),Software,Discrete Fourier transform,Time complexity,Mathematics | Journal |
Volume | Issue | ISSN |
40 | 3 | 1063-5203 |
Citations | PageRank | References |
7 | 0.50 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew J. Christlieb | 1 | 184 | 19.03 |
| David Lawlor | 2 | 38 | 2.36 |
| Yang Wang | 3 | 59 | 10.33 |