A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data
Authors:
- Andrew ChristliebACAndrew Christlieb
- David LawlorDLDavid Lawlor
- Yang WangYWYang Wang
Preprint
Abstract
We extend the recent sparse Fourier transform algorithm of (Lawlor, Christlieb, and Wang, 2013) to the noisy setting, in which a signal of bandwidth N is given as a superposition of k << N frequencies and additive noise. We present two such extensions, the second of which exhibits a novel form of error-correction in its frequency estimation not unlike that of the beta-encoders in analog-to-digital conversion (Daubechies et al, 2006). 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, a highly optimized software package for computing the full discrete Fourier transform, over a wide range of sparsity and noise values, and is to the best of our knowledge novel in the sparse Fourier transform context.Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- ADAPTIVE SUB-LINEAR TIME FOURIER ALGORITHMSAdvances in Adaptive Data Analysis, 2013
- Combinatorial Sublinear-Time Fourier AlgorithmsFoundations of Computational Mathematics, 2010
- Empirical evaluation of a sub-linear time sparse DFT algorithmCommunications in Mathematical Sciences, 2007
- A/D conversion with imperfect quantizersIEEE Transactions on Information Theory, 2006
- The Earth Mover's Distance as a Metric for Image RetrievalInternational Journal of Computer Vision, 2000
- Rapid Computation of the Discrete Fourier TransformSIAM Journal on Scientific Computing, 1996