Sparse Recovery Using Sparse Matrices

By Anna C. Gilbert, Piotr Indyk. Proceedings of the IEEE, 2010

415 citations recorded by the source corpus.

In this paper, we survey algorithms for sparse recovery problems that are based on sparse random matrices. Such matrices has several attractive properties: they support algorithms with low computational complexity, and make it easy to perform incremental updates to signals. We discuss applications to several areas, including compressive sensing, data stream computing, and group testing.

Subfields: Artificial Intelligence, Computational Mechanics, Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/2874730dde419b7989e12e5d97dac9b2a9fad455

How researchers see this paper

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

In Artificial Intelligence

In Computational Mechanics

In Computer Networks and Communications

Citations in the corpus

Compressed Sensing for Energy-Efficient Wireless Telemonitoring of Noninvasive Fetal ECG Via Block Sparse Bayesian Learning (2012, background): “ensing matrix is based on the result in [11]. However, it is possible to design a speciﬁc sparse binary sensing matrix which leads to higher reconstruction performance or lower algorithmic complexity [40]. Other practical issues such as quantization [41] also have to be studied. VI. CONCLUSIONS Feta”
Minimax rates for memory-bounded sparse linear regression (2015, background): “It satisfies the following: Proposition 2 (Gilbert and Indyk (2010), Theorem 2) Let 0 , δ 1 and k ≤ 1 .”
A Probabilistic and RIPless Theory of Compressed Sensing (2010, background): “These robust error bounds do not require either: 1) a random model on the signal or 2) the RIP nor one of a few closely related strong conditions such as the RIP-1 [25], the restricted eigenvalue assumption [5] or the compatibility condition [49]—all conditions that would imply uniform recovery.”
Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known Patterns (2017, methodology): “Greedy algorithms are often used [105], [106], [107], [108], [109], including the compressed sampling matching pursuit (CoSaMP) algorithm [110].”
Schatten Norms in Matrix Streams: Hello Sparsity, Goodbye Dimension (2019, methodology): “l techniques known for sparse vectors. For instance, methods like sparse recovery and heavy-hitters can be easily used to approximate ℓp norms of a k-sparse vector given as a stream using O˜(k) space [GI10]. However, they appear to be ineﬀective for approximating Schatten norms of k-sparse matrices ”
CoSaMP: Iterative signal recovery from incomplete and inaccurate samples (2008, neutral): “See [23] for a much more detailed comparison of compressive sampling recovery algorithms.”
Graph sketches: sparsification, spanners, and subgraphs (2012, methodology): “This paper also uses several techniques which are standard in streaming such as hierarchical sampling [23, 28], "0 sampling [21, 31] and sparse recovery [24].”
Memory, Communication, and Statistical Queries (2016, background): “Similarly, while there were a number of efforts to develop noise-tolerant learning algorithms, the introduction of the statistical query model of Kearns [1998] allowed for the development of a more general theory of how learning algorithms may be robust to noise, and the development of a common set ”