The dynamics of message passing on dense graphs, with applications to compressed sensing

By Mohsen Bayati, Andrea Montanari. 2010

1,095 citations recorded by the source corpus.

Subfields: Atomic and Molecular Physics, and Optics, Computational Mechanics, Computer Networks and Communications, Graph Learning, 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 Atomic and Molecular Physics, and Optics

In Computational Mechanics

In Computer Networks and Communications

In Graph Learning

In Signal Processing

Citations in the corpus

Feature Learning in Infinite-Width Neural Networks (2020, background): “(9)Actually, it is more similar to the Gaussian matrix in asymmetric message passing [4] in that care must be taken to keep track of correlation between W and W>.”
Scaling Limits of Wide Neural Networks with Weight Sharing: Gaussian Process Behavior, Gradient Independence, and Neural Tangent Kernel Derivation (2019, methodology): “Again, these two tools were not accessible to Bayati & Montanari (2011) because of their assumptions of only a finite number of input moments.”
Sparse Signal Processing for Grant-Free Massive Connectivity: A Future Paradigm for Random Access Protocols in the Internet of Things (2018, methodology): “This particular choice of user pilot sequence is convenient for use with the AMP algorithm for two reasons: first, the convergence of the AMP algorithm for device activity detection is guaranteed if A is generated in this way [8]; second, with such a Gaussian sensing matrix, the state evolution of t”
An Iterative Construction of Solutions of the TAP Equations for the Sherrington–Kirkpatrick Model (2012, methodology): “Bayati, M., Montanari, A.: The dynamics of message passing on dense graphs, with applications to compressed sensing.”
Sparse Activity Detection for Massive Connectivity (2018, background): “For example, [13] generalizes the AMP algorithm to a broad family of iterative thresholding algorithms, and provides a rigorous proof of the framework of the state evolution.”
0-1 Phase Transitions in Sparse Spiked Matrix Estimation (2019, methodology): “On one hand, the approximate message passing (AMP) algorithm has been analyzed by state evolution [6, 7].”
Compressed Sensing for Wireless Communications: Useful Tips and Tricks (2015, positive): “Algorithms based iterative thresholding yet exhibiting improved performance have been proposed in [91] and [92].”
Compressive phase retrieval via generalized approximate message passing (2012, background): “LBP-based compressive sensing is not only feasible [24] for dense matrices A, but provably accurate [29], [30], can be recognized as quite a breakthrough.”
Expectation-Maximization Gaussian-Mixture Approximate Message Passing (2012, methodology): “[10] D. L. Donoho, A. Maleki, and A. Montanari, “Message passing algorithms for compressed sensing,”Proc.”
Statistical Mechanics of Optimal Convex Inference in High Dimensions (2016, background): “[36] to yield the same answer as that obtained via a direct solution of the convex optimization problem.”
The committee machine: computational to statistical gaps in learning a two-layers neural network (2018, background): “While the behavior of AMP can be rigorously studied [17, 18, 58], it is useful and instructive to see how the derivation can be performed in the framework of belief-propagation and the cavity method, as was pioneered in [38, 40] for the single layer problem.”
Orthogonal AMP (2016, methodology): “3The function ψ is said to be pseudo-Lipschitz (or order two) [3] if there exists a constant L > 0 such that for all x, y, |ψ(x)−ψ(y)| ≤ L(1+‖x‖+ ‖y‖)‖x− y‖.”
An equivalence between high dimensional Bayes optimal inference and M-estimation (2016, positive): “…can be expressed as special cases of a generalized AMP (gAMP) algorithm [9], which we first describe. gAMP is a set of iterative equations, ηt = Xŝt + λtηGy(λ t−1 η ,y,η t−1) ŝt+1 = Gs ( λth, ŝ t − λthX TGy(λ t η,y,η t) ) (6) λth = ( γα N N∑ ν=1 ∂ ∂η Gy(λ t η, yν , η t ν) )−1 λt+1η…”
AMP-Inspired Deep Networks for Sparse Linear Inverse Problems (2016, background): “, M, N →∞ with M/N converging to a positive constant) [21], [22].”
Learned D-AMP: Principled Neural Network based Compressive Image Recovery (2017, background): “This state-evolution is distinct from the widely studied “probabilistic” state-evolution proposed in [16], proven, for some contexts, in [40], and veriﬁed for LAMP and LVAMP in [14].”
The LASSO Risk for Gaussian Matrices (2010, methodology): “For greater convenience of the reader, we also restate two lemmas from [3] (namely, Lemmas F.”
Tensor Programs III: Neural Matrix Laws (2020, methodology): “[6] Mohsen Bayati and Andrea Montanari.”