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 | Venue | Field |
|---|---|---|
2012 | CoRR | Discrete-time Fourier transform,Mathematical optimization,Algorithm,Quadratic equation,Fourier transform,Aliasing,Fourier series,Bandwidth (signal processing),Deterministic algorithm,Discrete Fourier transform,Mathematics |
DocType | Volume | Citations |
Journal | abs/1207.6368 | 8 |
PageRank | References | Authors |
0.56 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| David Lawlor | 1 | 38 | 2.36 |
| Yang Wang | 2 | 59 | 10.33 |
| Andrew J. Christlieb | 3 | 184 | 19.03 |