Name
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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1142/S1793536913500039 | ADVANCES IN DATA SCIENCE AND ADAPTIVE ANALYSIS |
Keywords | Field | DocType |
Fourier algorithm | Discrete-time Fourier transform,Non-uniform discrete Fourier transform,Adaptive-additive algorithm,Mathematical optimization,Fourier analysis,Prime-factor FFT algorithm,Discrete Fourier series,Short-time Fourier transform,Algorithm,Discrete Fourier transform,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 1 | 2424-922X |
Citations | PageRank | References |
23 | 0.96 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Lawlor | 1 | 38 | 2.36 |
| Yang Wang | 2 | 59 | 10.33 |
| Andrew J. Christlieb | 3 | 184 | 19.03 |