Abstract
•We study the problem of finding a Fourier representation <b>R </b>of <i>m</i> terms for a given discrete signal <b>A</b> of length<i> N</i>. The Fast Fourier Transform (FFT) can find the optimal <i>N</i>-term representation in time <i>O</i>(<i>N </i>log <i>N</i>) time, but our goal is to get <i>sublinear</i> time algorithms when <i>m</i> << <i>N</i>. Suppose ||<b>A</b>||<sub>2</sub> ≤<i>M</i>||<b>A</b>-<b>R</b><sub>opt</sub>||<sub>2</sub>, where <b>R</b><sub>opt</sub> is the optimal output. The previously best known algorithms output <b>R</b> such that ||<b>A</b>-<b>R</b>||<sup>2</sup><sub>2</sub>≤(1+ε))||<b>A</b>-<b>R</b><sub>opt</sub>||<sup>2</sup><sub>2</sub> with probability at least 1-δ in time* poly(<i>m</i>,log(1/δ),log <i>N</i>,log <i>M</i>,1/ε). Although this is sublinear in the input size, the dominating expression is the polynomial factor in <i>m</i> which, for published algorithms, is greater than or equal to the bottleneck at <i>m</i><sup>2</sup> that we identify below. Our experience with these algorithms shows that this is serious limitation in theory and in practice. Our algorithm beats this <i>m</i><sup>2</sup> bottleneck. Our main result is a significantly improved algorithm for this problem and the <i>d</i>-dimensional analog. Our algorithm outputs an <b>R</b> with the same approximation guarantees but it runs in time <i>m</i>•poly(log(1/δ),log <i>N</i>,log <i>M</i>,1/ε). A version of the algorithm holds for all <i>N</i>, though the details differ slightly according to the factorization of <i>N</i>. For the <i>d</i>-dimensional problem of size <i>N</i><sub>1</sub> × <i>N</i><sub>2</sub> × •• × <i>N</i><sub>d</sub>, the linear-in-<i>m</i> algorithm extends efficiently to higher dimensions for certain factorizations of the <i>N<sub>i</sub></i>'s; we give a quadratic-in-<i>m</i> algorithm that works for any values of <i>N<sub>i</sub></i>'s. This article replaces several earlier, unpublished drafts.
Keywords
CombinatoricsFast Fourier transformBinary logarithmSublinear functionMathematicsAlgorithmDiscrete mathematics
Affiliated Institutions
Related Publications
Compressed sensing
Suppose x is an unknown vector in Ropf <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</sup> (a digital image or signal); we pla...
Sparse reconstruction by convex relaxation: Fourier and Gaussian measurements
This paper proves best known guarantees for exact reconstruction of a sparse signal f from few non-adaptive universal linear measurements. We consider Fourier measurements (rand...
Decoding by Linear Programming
This paper considers a natural error correcting problem with real valued input/output. We wish to recover an input vector f/spl isin/R/sup n/ from corrupted measurements y=Af+e....
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
This paper considers the model problem of reconstructing an object from incomplete frequency samples. Consider a discrete-time signal f ∈ C N and a randomly chosen set of freque...
First‐Year <i>Wilkinson Microwave Anisotropy Probe</i> ( <i>WMAP</i> ) Observations: Preliminary Maps and Basic Results
We present full sky microwave maps in five frequency bands (23 to 94 GHz) from the WMAP first year sky survey. Calibration errors are less than 0.5% and the low systematic error...
Publication Info
- Year
- 2005
- Type
- article
- Volume
- 5914
- Pages
- 59141A-59141A
- Citations
- 212
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
212
OpenAlex
Cite This
Anna C. Gilbert,
S. Muthukrishnan,
Michael Strauss
(2005).
Improved time bounds for near-optimal sparse Fourier representations.
Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE
, 5914
, 59141A-59141A.
https://doi.org/10.1117/12.615931
Identifiers
- DOI
- 10.1117/12.615931