Near-optimal sparse fourier representations via sampling

By Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthu Muthukrishnan, Martin J. Strauss. 2002

292 citations recorded by the source corpus.

Subfields: Applied Mathematics, Computational Mechanics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Numerical Analysis

Citations in the corpus

Local, Private, Efficient Protocols for Succinct Histograms (2015, background): “For example, the use of hashing to isolate unique “heavy” items appears in the context of sparse approximations to a vector’s Fourier representation [12] (and arguably that idea has roots in learning algorithms for Fourier coefficients such as [18]).”
Spectral compressive sensing (2013, unknown): “selection technique results in a random sampling acquisition scheme [39, 40, 41, 42, 43, 44].”
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples (2008, unknown): “Gilbert, Strauss, and their collaborators showed how to incorporate greedy iterative strategies into fast algorithms for sparse approximation problems, and they established the first rigorous guarantees for greedy methods [19, 20].”
Sparse Solution of Underdetermined Systems of Linear Equations by Stagewise Orthogonal Matching Pursuit (2012, background): “Recently, there has been considerable interest both from theorists [7], [8], [17], [33] and from practitioners [31], [40]–[42], [47] in the possibility of dramatically reducing the “number of samples’ that “have to be measured” in various remote sensing problems.”
Beyond Nyquist: Efficient Sampling of Sparse Bandlimited Signals (2009, background): “We believe that these applications will be easier to achieve in the near future because suitable ADC and DSP technology is already available.”
Sparse Solution Of Underdetermined Linear Equations By Stagewise Orthogonal Matching Pursuit (2006, background): “1 Compressed Sensing Recently, there has been considerable interest both from theorists [33, 7, 17, 8] and from practitioners [42, 47, 31, 40, 41] in the possibility of dramatically reducing the ‘number of samples’ that ‘have to be measured’ in various remote sensing problems.”
Compressed sensing (2006, background): “Finally, in Section VIII, we note the ongoing work by two groups (Gilbert et al. [12] and Candès et al. [13], [14]), which although not written in the -widths/OR/IBC tradition, imply (as we explain), closely related results.”
Fast Solution of $\ell _{1}$ -Norm Minimization Problems When the Solution May Be Sparse (2008, background): “Partial Fourier matrices and partial Hadamard matrices have drawn considerable attention in the sparse approximation community [7], [6], [55], [54], [31].”
Combining geometry and combinatorics: A unified approach to sparse signal recovery (2008, background): “The early work on this topic includes the algebraic approach of [Man92](cf. [GGI + 02a]).”
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information (2004, background): “The algorithm in [22], [23], which operates by estimating the frequencies present in the signal from a small number of randomly placed samples, produces with high probability an approximation in sublinear time with error within a constant of the best -term approximation.”
Simple and practical algorithm for sparse Fourier transform (2012, methodology): “The algorithms in [GGI + 02, Man92] perform this update by going through O ( k ) iterations each of which updates at least O ( k ) time samples, resulting in an O ( k 2 ) term in the runtime.”
Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies? (2004, background): “In this context, it is unclear how the methodology presented in [18], [45], would allow reconstructing the signal from poly arbitrary sampled values.”
Extensions of compressed sensing (2006, unknown): “Several recent papers [20, 3, 14, 5], have shown that, under various assumptions, it may be possible to directly acquire a form of compressed representation.”