The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing

DOI10.1109/TIT.2010.2094817zbMATH Open1366.94079arXiv1001.3448OpenAlexW3098848552MaRDI QIDQ5281076FDOQ5281076

Authors: Mohsen Bayati, Andrea Montanari 

Publication date: 27 July 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: Approximate message passing algorithms proved to be extremely effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical experiments further showed that their dynamics is accurately tracked by a simple one-dimensional iteration termed state evolution. In this paper we provide the first rigorous foundation to state evolution. We prove that indeed it holds asymptotically in the large system limit for sensing matrices with independent and identically distributed gaussian entries. While our focus is on message passing algorithms for compressed sensing, the analysis extends beyond this setting, to a general class of algorithms on dense graphs. In this context, state evolution plays the role that density evolution has for sparse graphs. The proof technique is fundamentally different from the standard approach to density evolution, in that it copes with large number of short loops in the underlying factor graph. It relies instead on a conditioning technique recently developed by Erwin Bolthausen in the context of spin glass theory.

Full work available at URL: https://arxiv.org/abs/1001.3448

Mathematics Subject Classification ID

Applications of graph theory (05C90) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Random matrices (probabilistic aspects) (60B20) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08)

Cited In (only showing first 100 items - show all)

• Title not available (Why is that?)
• Approximate message passing with spectral initialization for generalized linear models*
• Notes on computational-to-statistical gaps: predictions using statistical physics
• Constrained low-rank matrix estimation: phase transitions, approximate message passing and applications
• Asymptotic mutual information for the balanced binary stochastic block model
• LASSO risk and phase transition under dependence
• Unbiasing in iterative reconstruction algorithms for discrete compressed sensing
• Statistical limits of spiked tensor models
• Overcoming the limitations of phase transition by higher order analysis of regularization techniques
• Robust subspace clustering
• Community detection and stochastic block models: recent developments
• Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator
• Phase transition in the spiked random tensor with Rademacher prior
• Optimal low-degree hardness of maximum independent set
• A Unifying Tutorial on Approximate Message Passing
• Statistical mechanics approach to 1-bit compressed sensing
• Approximate message passing algorithms for rotationally invariant matrices
• Regularization by denoising via fixed-point projection (RED-PRO)
• Debiasing the Lasso: optimal sample size for Gaussian designs
• Analysis of Bayesian inference algorithms by the dynamical functional approach
• The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square
• Fundamental limits of weak recovery with applications to phase retrieval
• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• A message-passing approach to phase retrieval of sparse signals
• High dimensional robust M-estimation: asymptotic variance via approximate message passing
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• Recovering structured signals in noise: least-squares meets compressed sensing
• Universality of regularized regression estimators in high dimensions
• Computational barriers to estimation from low-degree polynomials
• Which bridge estimator is the best for variable selection?
• Fast and reliable parameter estimation from nonlinear observations
• Learning low-dimensional nonlinear structures from high-dimensional noisy data: an integral operator approach
• The existence of maximum likelihood estimate in high-dimensional binary response generalized linear models
• Message-Passing De-Quantization With Applications to Compressed Sensing
• Universality of approximate message passing algorithms
• Statistical mechanics of low-rank tensor decomposition
• The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising
• Sharp MSE bounds for proximal denoising
• Phase transition in random tensors with multiple independent spikes
• A dynamical mean-field theory for learning in restricted Boltzmann machines
• The distribution of the Lasso: uniform control over sparse balls and adaptive parameter tuning
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Optimization of mean-field spin glasses
• An iterative construction of solutions of the TAP equations for the Sherrington-Kirkpatrick model
• Algorithmic pure states for the negative spherical perceptron
• Submatrix localization via message passing
• The committee machine: computational to statistical gaps in learning a two-layers neural network
• Analysis of random sequential message passing algorithms for approximate inference
• TAP free energy, spin glasses and variational inference
• Detangling robustness in high dimensions: composite versus model-averaged estimation
• Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
• Blind sensor calibration using approximate message passing
• Consistent parameter estimation for Lasso and approximate message passing
• Optimal combination of linear and spectral estimators for generalized linear models
• Estimation of low-rank matrices via approximate message passing
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Accelerating cross-validation in multinomial logistic regression with \(\ell_1\)-regularization
• Semi-analytic resampling in Lasso
• Optimality and sub-optimality of PCA. I: Spiked random matrix models
• Fundamental barriers to high-dimensional regression with convex penalties
• Data assimilation -- mathematical foundation and applications. Abstracts from the workshop held February 20--26, 2022
• Critical behavior and universality classes for an algorithmic phase transition in sparse reconstruction
• Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
• Matrix inference and estimation in multi-layer models*
• A power analysis for Model-X knockoffs with \(\ell_p\)-regularized statistics
• Algorithmic obstructions in the random number partitioning problem
• Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising
• Local algorithms for maximum cut and minimum bisection on locally treelike regular graphs of large degree
• Semi-analytic approximate stability selection for correlated data in generalized linear models
• Plug in estimation in high dimensional linear inverse problems a rigorous analysis
• Infinite-width limit of deep linear neural networks
• Statistical mechanics analysis of generalized multi-dimensional knapsack problems
• Thouless-Anderson-Palmer equations for the multi-species Sherrington-Kirkpatrick model
• Characterizing the SLOPE trade-off: a variational perspective and the Donoho-Tanner limit
• Fluctuations, bias, variance and ensemble of learners: exact asymptotics for convex losses in high-dimension
• Multi-layer state evolution under random convolutional design
• The replica-symmetric free energy for Ising spin glasses with orthogonally invariant couplings
• Noisy linear inverse problems under convex constraints: exact risk asymptotics in high dimensions
• Automatic bias correction for testing in high‐dimensional linear models
• Universality of approximate message passing algorithms and tensor networks
• Perfect reconstruction of sparse signals with piecewise continuous nonconvex penalties and nonconvexity control
• Fundamental limits of low-rank matrix estimation with diverging aspect ratios
• Weighted message passing and minimum energy flow for heterogeneous stochastic block models with side information
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• The scaling limit of high-dimensional online independent component analysis
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• A tradeoff between false discovery and true positive proportions for sparse high-dimensional logistic regression
• On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models
• Tight Lipschitz hardness for optimizing mean field spin glasses
• Equilibria of large random Lotka-Volterra systems with vanishing species: a mathematical approach
• On the universality of noiseless linear estimation with respect to the measurement matrix
• Bayesian Imaging Using Plug & Play Priors: When Langevin Meets Tweedie
• Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022
• Disordered systems insights on computational hardness
• Dense limit of the Dawid–Skene model for crowdsourcing and regions of sub-optimality of message passing algorithms
• Title not available (Why is that?)
• Approximate survey propagation for statistical inference
• Replica analysis of overfitting in generalized linear regression models
• Approximate message passing for sparse matrices with application to the equilibria of large ecological Lotka-Volterra systems
• Optimization algorithms for multi-species spherical spin glasses

This page was built for publication: The Dynamics of Message Passing on Dense Graphs, with Applications to Compressed Sensing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281076)