Model-Based Compressive Sensing
By Richard Baraniuk, Volkan Cevher, Marco F. Duarte, Chinmay Hegde. IEEE Transactions on Information Theory, 2008
2,612 citations recorded by the source corpus.
Compressive sensing (CS) is an alternative to Shannon/Nyquist sampling for the acquisition of sparse or compressible signals that can be well approximated by just K ¿ N elements from an N -dimensional basis. Instead of taking periodic samples, CS measures inner products with M < N random vectors and then recovers the signal via a sparsity-seeking optimization or greedy algorithm. Standard CS dictates that robust signal recovery is possible from M = O(K log(N/K)) measurements. It is possible to substantially decrease M without sacrificing robustness by leveraging more realistic signal models that go beyond simple sparsity and compressibility by including structural dependencies between the values and locations of the signal coefficients. This paper introduces a model-based CS theory that parallels the conventional theory and provides concrete guidelines on how to create model-based recovery algorithms with provable performance guarantees. A highlight is the introduction of a new class of structured compressible signals along with a new sufficient condition for robust structured compressible signal recovery that we dub the restricted amplification property, which is the natural counterpart to the restricted isometry property of conventional CS. Two examples integrate two relevant signal models-wavelet trees and block sparsity-into two state-of-the-art CS recovery algorithms and prove that they offer robust recovery from just M = O(K) measurements. Extensive numerical simulations demonstrate the validity and applicability of our new theory and algorithms.
Subfields: Applied Mathematics, Computational Mechanics, Control and Systems Engineering
View Paper: https://www.semanticscholar.org/paper/bf852287566cda9c2f391fa8f7f19122e0671558
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
- Richard Baraniuk
- Francis R. Bach
- Marco F. Duarte
- Yonina C. Eldar
- Bhaskar D. Rao
- Julien Mairal
- Steven L. Brunton
- Zhilin Zhang
In Computational Mechanics
- Francis R. Bach
- Julien Mairal
- Yonina C. Eldar
- Richard Baraniuk
- Marco F. Duarte
- Steven L. Brunton
- Jean Ponce
- Guillaume Obozinski
In Control and Systems Engineering
- Steven L. Brunton
- Francis R. Bach
- J. Nathan Kutz
- Peter Richtárik
- Joshua L. Proctor
- Bingni W. Brunton
- Mark W. Schmidt
- Tong Zhang
Citations in the corpus
- Structured Compressed Sensing: From Theory to Applications (2011, methodology): “Theorem 23 [20]: Let and let be a set of noisy CS measurements.”
- Convex Optimization for Big Data: Scalable, randomized, and parallel algorithms for big data analytics (2014, background): “Tree sparsity [33, 18, 2, 69] f (x)-ball G = {{1, 2, 3}, {2}, {3}} valid selection of nodes Structure: We seek the sparsest signal with a rooted connected subtree support.”
- Contrast Enhancement Based on Layered Difference Representation of 2D Histograms (2013, background): “Note that reasonable solutions can be found assuming the sparsity of the solutions [24].”
- Bayesian Coresets: Revisiting the Nonconvex Optimization Perspective (2021, methodology): “Here, we describe the plain sparsity case, but one can consider different realizations of C k as in (Baldassarre et al., 2016; Kyrillidis et al., 2015; Baraniuk et al., 2010).”
- WIRE: Wavelet Implicit Neural Representations (2023, background): “There are many forms of regularization, including ridge regression, Lasso [45], total variation (TV) [9], and sparsitybased [7] techniques that seek to penalize the 1 norm the signal or some transform thereof.”
- Robust Recovery of Signals From a Structured Union of Subspaces (2008, background): “The union model developed in this paper is broader than the block-sparse setting treated in [46] in the sense that it allows to model linear dependencies between the nonzero values rather than only between their locations, by appropriate choice of subspaces in (6), (7).”
- Roadmap on wavefront shaping and deep imaging in complex media (2021, background): “Compressive sensing is an innovative sampling framework for capturing object information with fewer measurements compared with the sampling theorem, thus overcoming the above compromise [166].”
- ReconNet: Non-Iterative Reconstruction of Images from Compressively Sensed Measurements (2016, methodology): “In the first, the image model is enforced explicitly [10, 1, 18, 28], wherein in each iteration the image estimate is projected onto the solution set defined by the model.”
- Finding and Leveraging Structure in Learning Problems (2012, background): “[23] and Soni and Haupt [175] have analyzed different forms of structured sparsity in the vector setting, e.”
- Combinatorial Penalties: Structure preserved by convex relaxations (2017, neutral): “Non-convex approaches were also proposed in [4, 18].”
- Off-Grid Direction of Arrival Estimation Using Sparse Bayesian Inference (2011, background): “The topic of sparse signal representation and reconstruction has recently been developed into the well-known area named compressed/compressive sensing (CS) [13–15], and a broad spectrum of different applications can be found in excellent references [16–23].”
- Tradeoffs Between Convergence Speed and Reconstruction Accuracy in Inverse Problems (2016, neutral): “zeros of only certain sparsity patterns, which are bounded by R, we have the model-based IHT of [36].”