One sketch for all: fast algorithms for compressed sensing

By Anna C. Gilbert, Martin J. Strauss, Joel A. Tropp, Roman Vershynin. Symposium on the Theory of Computing, 2007

311 citations recorded by the source corpus.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/2f3de80819d1981c6a9f5e3c8ec1d48a8c109499

How researchers see this paper

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

In Biomedical Engineering

In Computational Mechanics

In Signal Processing

Citations in the corpus

Sparse Recovery Using Sparse Matrices (2010, background): “HHS differs from the simple sublinear algorithm we sketched in Section II in three major parts.”
Uncertainty Principles and Vector Quantization (2006, unknown): “The algorithm to compute Kashin’s representations resembles the Chaining Algorithm of [18], which also detects a few biggest coefficients and iterates on the residual, but it serves to find all big coefficients rather than to spread them out.”
Compressive sensing: From theory to applications, a survey (2013, methodology): “Representative algorithms are Fourier sampling algorithm [44], chaining pursuits [45], heavy hitters on steroids (HHS) [46], etc.”
Distributed Private Heavy Hitters (2012, background): “Gilbert, et al. [GSTV07] present a sparse recovery algorithm (we refer to it as the GLPS algorithm) that takes linear measurements from a sparse vector, and reconstructs the original vector to high accuracy.”
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples (2008, unknown): “This class includes Fourier sampling [20, 22], chaining pursuit [17], and HHS pursuit [18], as well as some algorithms of Cormode–Muthukrishnan [9] and Iwen [24].”
Compressed Sensing (2012, methodology): “From the various types of algorithms, we mention the HHS pursuit [35] and a sub-linear Fourier transform [37].”
Optimally Tuned Iterative Reconstruction Algorithms for Compressed Sensing (2009, unknown): “This scheme again presents the ‘recipe ingredients without recipe amounts’ obstacle: users may be turned off by the requirement to specify many such tunable parameters.”
Uniform Uncertainty Principle and Signal Recovery via Regularized Orthogonal Matching Pursuit (2007, methodology): “No iterative methods have been known to feature such uniform guarantees, with the exception of Chaining Pursuit [14] and the HHS Algorithm [15] which however only work with specifically designed structured measurement matrices.”
General Deviants: An Analysis of Perturbations in Compressed Sensing (2009, background): “First we generalize a lemma in [12] about the image of an arbitrary signal.”
Agnostically learning decision trees (2008, background): “There are numerous algorithm that give strong guarantees in this setting (see for instance [9]).”
Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity (2008, background): “Recovery Distortion under Signal and Measurement Perturbations The proof of Corollary 1 is based on the following two lemmas, which are proved in [16] and [17], respectively.”
A Nonparametric Approach to Modeling Choice with Limited Data (2009, methodology): “The distribution defines our choice model as follows: Define the set Sj4M5= 8 ∈ SN 2 4j5 4i51 ∀ i ∈M1 i 6= j91 where Sj4M5 is simply the set of all customer types that would purchase product j when the offer set is M.”
Subspace Pursuit for Compressive Sensing Signal Reconstruction (2008, unknown): “Recovery Distortion Under Signal and Measurement Perturbations The proof of Corollary 1 is based on the following two lemmas, which are proved in [21] and [22], respectively.”