Message-passing algorithms for compressed sensing

By David L. Donoho, Arian Maleki, Andrea Montanari. 2009

2,543 citations recorded by the source corpus.

Compressed sensing aims to undersample certain high-dimensional signals yet accurately reconstruct them by exploiting signal characteristics. Accurate reconstruction is possible when the object to be recovered is sufficiently sparse in a known basis. Currently, the best known sparsity–undersampling tradeoff is achieved when reconstructing by convex optimization, which is expensive in important large-scale applications. Fast iterative thresholding algorithms have been intensively studied as alternatives to convex optimization for large-scale problems. Unfortunately known fast algorithms offer substantially worse sparsity–undersampling tradeoffs than convex optimization. We introduce a simple costless modification to iterative thresholding making the sparsity–undersampling tradeoff of the new algorithms equivalent to that of the corresponding convex optimization procedures. The new iterative-thresholding algorithms are inspired by belief propagation in graphical models. Our empirical measurements of the sparsity–undersampling tradeoff for the new algorithms agree with theoretical calculations. We show that a state evolution formalism correctly derives the true sparsity–undersampling tradeoff. There is a surprising agreement between earlier calculations based on random convex polytopes and this apparently very different theoretical formalism.

Subfields: Computational Mechanics, Computer Networks and Communications, Signal Processing

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Harnessing Wireless Channels for Scalable and Privacy-Preserving Federated Learning (2020, methodology): “Applying compressive sensing techniques is promising, in which a sparsified update is encoded by multiplying a random matrix before transmission [26], and the received update is decoded using the approximate message passing (AMP) algorithm [27].”
Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation (2019, methodology): “Approximate Message Passing is an algorithm for recovering a ground truth vector from noisy measurements (Compressed Sensing) (Donoho et al., 2009).”
A Fast Approach for Overcomplete Sparse Decomposition Based on Smoothed $\ell ^{0}$ Norm (2008, background): “In addition to EM-BP, the belief propagation approach to the sparse recovery problem has been widely investigated in [2],[3],[4],[5],[6],[7].”
A deep learning approach to structured signal recovery (2015, methodology): “This line ar program can be solved either based on convex optimization methods [6] or iterative greedy algorithms [7]–[10] that ar e generally first order methods and as a result are more suitabl e for high-dimensional problems.”
Generalized approximate message passing for estimation with random linear mixing (2010, methodology): “BP has been successfully applied to linear mixing problems in CDMA multiuser detection [2]–[4], lattice codes [5] and compressed sensing [6]– [8].”
Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers (2011, neutral): “There are other approaches as well, such as Bregman iterative algorithms [176] and iterative thresholding algorithms [51] implementable in a message-passing framework.”
Compressive sensing: From theory to applications, a survey (2013, background): “Message passing (MP) algorithms [26] are an important modiﬁcation of iterative algorithms in which basic variables (messages) are associated with directed graph edges.”
Tensor Programs III: Neural Matrix Laws (2020, neutral): “Asymmetric message passing [10] is an algorithm that tries to recover a ground truth signal v from a noisy measurement Wv of it obtained by a matrix W .”
Three-dimensional irregular seismic data reconstruction via low-rank matrix completion (2013, neutral): “, Γ 0 τk ðxÞ 1⁄4 ð∂∕∂xÞΓτkðxÞ (Donoho et al., 2009).”
Statistical Mechanics of Optimal Convex Inference in High Dimensions (2016, background): “[35] to study compressed sensing with Gaussian measurements.”
DR2-Net: Deep Residual Reconstruction Network for Image Compressive Sensing (2017, methodology): “Finally, we summarize the procedure that DR2-Net reconstructs an image.”
Expectation-Maximization Gaussian-Mixture Approximate Message Passing (2012, methodology): “(The latter two converge in the large system limit [3].”
Capturing the learning curves of generic features maps for realistic data sets with a teacher-student model (2021, background): “Teacher-student models are a popular framework to study the high-dimensional asymptotic performance of machine learning problems with synthetic data, and have been the subject of intense investigations spanning three decades [1, 2, 3, 4, 5, 6, 7].”
Community detection and stochastic block models: recent developments (2017, methodology): “Community detection is used in particular to understand sociological behavior Goldenberg et al. (2010); Fortunato (2010); Newman et al.”
AMP-Inspired Deep Networks for Sparse Linear Inverse Problems (2016, methodology): “In particular, we show how “Onsager correction,” which lies at the heart of the approximate message passing (AMP) [11] and vector AMP (VAMP) [12] algorithms, can be employed to construct deep networks that i) require fewer layers to reach a given level of accuracy and ii) yield greater accuracy over”
Compressive phase retrieval via generalized approximate message passing (2012, methodology): “Hence, the recent realization by Donoho, Maleki, Montanari, and Bayati that definitions: p Z|Y,P (z|y, ˆ p; µ p ) = p Y |Z (y|z) CN (z; ˆ p,µ p ) z ′ p Y |Z (y|z ′ ) CN (z ′ ; ˆ p,µ p ) (D1) g out (y, ˆ p, µ p ) = 1 µ p E Z|Y,P {Z|y, ˆ p; µ p } − ˆ p (D2) g ′ out (y, ˆ p, µ p ) = 1 µ p var Z|Y,P {Z|”