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

DOI10.1109/TIT.2010.2094817MaRDI QIDQ5281076zbMATH OpenOpenAlexFDO

Authors Mohsen Bayati, Andrea Montanari

Publication date 27 July 2017

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

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

Mathematics Subject Classification ID

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

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.

Cited in

(only showing first 100 items - show all)

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

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)