ADAPTIVE SUB-LINEAR TIME FOURIER ALGORITHMS
Authors:
- 1 January 2013
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in Advances in Adaptive Data Analysis
- Vol. 05 (01)
Abstract
We present a new deterministic algorithm for the sparse Fourier transform problem, in which we seek to identify k ≪ N significant Fourier coefficients from a signal of bandwidth N. Previous deterministic algorithms exhibit quadratic runtime scaling, while our algorithm scales linearly with k in the average case. Underlying our algorithm are a few simple observations relating the Fourier coefficients of time-shifted samples to unshifted samples of the input function. This allows us to detect when aliasing between two or more frequencies has occurred, as well as to determine the value of unaliased frequencies. We show that empirically our algorithm is orders of magnitude faster than competing algorithms.Keywords
All Related Versions
This publication has 30 references indexed in Scilit:
- Compressive Wave ComputationFoundations of Computational Mathematics, 2011
- Concentration of Measure for the Analysis of Randomized Algorithms2009
- Compressed sensing and best 𝑘-term approximationJournal of the American Mathematical Society, 2008
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency informationIEEE Transactions on Information Theory, 2006
- Finding Smooth Integers in Short Intervals Using CRT DecodingJournal of Computer and System Sciences, 2002
- Guest Editors Introduction to the top 10 algorithmsComputing in Science & Engineering, 2000
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Rapid Computation of the Discrete Fourier TransformSIAM Journal on Scientific Computing, 1996
- Fast Fourier Transforms for Nonequispaced DataSIAM Journal on Scientific Computing, 1993
- Construction of a Thin Set with small Fourier CoefficientsBulletin of the London Mathematical Society, 1990