State evolution for general approximate message passing algorithms, with applications to spatial coupling

DOI10.1093/IMAIAI/IAT004zbMath1335.94015arXiv1211.5164OpenAlexW2963072996MaRDI QIDQ5175645

Adel Javanmard, Andrea Montanari

Publication date: 24 February 2015

Published in: Information and Inference (Search for Journal in Brave)

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

zbMATH Keywords

signal recoverymessage passingcompressed sensingspatial couplingstate evolution

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items (51)

Fundamental barriers to high-dimensional regression with convex penalties ⋮ Approximate message passing algorithms for rotationally invariant matrices ⋮ The asymptotic distribution of the MLE in high-dimensional logistic models: arbitrary covariance ⋮ Approximate message passing with spectral initialization for generalized linear models* ⋮ Disordered systems insights on computational hardness ⋮ Dense limit of the Dawid–Skene model for crowdsourcing and regions of sub-optimality of message passing algorithms ⋮ Computational barriers to estimation from low-degree polynomials ⋮ High dimensional robust M-estimation: asymptotic variance via approximate message passing ⋮ Estimation of low-rank matrices via approximate message passing ⋮ Statistical limits of spiked tensor models ⋮ Bayesian Imaging Using Plug & Play Priors: When Langevin Meets Tweedie ⋮ Algorithmic pure states for the negative spherical perceptron ⋮ Perturbative construction of mean-field equations in extensive-rank matrix factorization and denoising ⋮ Fundamental limits of weak recovery with applications to phase retrieval ⋮ 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 ⋮ A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists ⋮ 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 ⋮ Optimizing mean field spin glasses with external field ⋮ On the TAP equations via the cavity approach in the generic mixed \(p\)-spin models ⋮ Asymptotic mutual information for the balanced binary stochastic block model ⋮ Metamodel construction for sensitivity analysis ⋮ Notes on computational-to-statistical gaps: predictions using statistical physics ⋮ The overlap gap property and approximate message passing algorithms for \(p\)-spin models ⋮ 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 ⋮ Optimization of the Sherrington--Kirkpatrick Hamiltonian ⋮ Phase transition in random tensors with multiple independent spikes ⋮ ROCKET: robust confidence intervals via Kendall's tau for transelliptical graphical models ⋮ Online rules for control of false discovery rate and false discovery exceedance ⋮ Submatrix localization via message passing ⋮ The likelihood ratio test in high-dimensional logistic regression is asymptotically a rescaled Chi-square ⋮ Optimality and sub-optimality of PCA. I: Spiked random matrix models ⋮ Universality of approximate message passing algorithms ⋮ Optimization of mean-field spin glasses ⋮ Phase transition in the spiked random tensor with Rademacher prior ⋮ Optimal combination of linear and spectral estimators for generalized linear models ⋮ 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 ⋮ Approximate survey propagation for statistical inference ⋮ Semi-analytic approximate stability selection for correlated data in generalized linear models ⋮ Generalized approximate survey propagation for high-dimensional estimation ^* ⋮ Universality in polytope phase transitions and message passing algorithms ⋮ A Unifying Tutorial on Approximate Message Passing ⋮ Information theory and recovery algorithms for data fusion in Earth observation ⋮ LASSO risk and phase transition under dependence ⋮ Optimal low-degree hardness of maximum independent set ⋮ Prediction errors for penalized regressions based on generalized approximate message passing

This page was built for publication: State evolution for general approximate message passing algorithms, with applications to spatial coupling