State evolution for approximate message passing with non-separable functions

DOI10.1093/IMAIAI/IAY021MaRDI QIDQ5006514zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 16 August 2021

Published in Information and Inference: A Journal of the IMA (Search for Journal in Brave)

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

zbMATH Keywords

compressed sensingmessage passingrandom matricesstatistical estimation

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Random matrices (probabilistic aspects) (60B20) Statistical aspects of information-theoretic topics (62B10) Communication theory (94A05)

Abstract: Given a high-dimensional data matrix $$, Approximate Message Passing (AMP) algorithms construct sequences of vectors $$, $$, indexed by $tin0,1,2dots$ by iteratively applying $$ or $$, and suitable non-linear functions, which depend on the specific application. Special instances of this approach have been developed --among other applications-- for compressed sensing reconstruction, robust regression, Bayesian estimation, low-rank matrix recovery, phase retrieval, and community detection in graphs. For certain classes of random matrices $$, AMP admits an asymptotically exact description in the high-dimensional limit $m,noinfty$, which goes under the name of `state evolution.' Earlier work established state evolution for separable non-linearities (under certain regularity conditions). Nevertheless, empirical work demonstrated several important applications that require non-separable functions. In this paper we generalize state evolution to Lipschitz continuous non-separable nonlinearities, for Gaussian matrices $$. Our proof makes use of Bolthausen's conditioning technique along with several approximation arguments. In particular, we introduce a modified algorithm (called LAMP for Long AMP) which is of independent interest.

Recommendations

• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Universality of approximate message passing algorithms
• A Unifying Tutorial on Approximate Message Passing
• Approximate message passing algorithms for rotationally invariant matrices
• Estimation of low-rank matrices via approximate message passing

Cited in

(39)

• 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
• Fundamental barriers to high-dimensional regression with convex penalties
• Approximate message passing algorithms for rotationally invariant matrices
• The overlap gap property and approximate message passing algorithms for \(p\)-spin models
• Universality in polytope phase transitions and message passing algorithms
• Estimation of low-rank matrices via approximate message passing
• Algorithmic pure states for the negative spherical perceptron
• Approximate message passing for nonconvex sparse regularization with stability and asymptotic analysis
• Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• State evolution for general approximate message passing algorithms, with applications to spatial coupling
• Large dimensional analysis of general margin based classification methods
• Regularization by denoising via fixed-point projection (RED-PRO)
• A Unifying Tutorial on Approximate Message Passing
• 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
• 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
• Linear operator approximate message passing (OpAMP)
• Fundamental limits of community detection from multi-view data: multi-layer, dynamic and partially labeled block models
• Entrywise dynamics and universality of general first order methods
• A leave-one-out approach to approximate message passing
• Optimization of the Sherrington-Kirkpatrick Hamiltonian
• Statistical inference in classification of high-dimensional Gaussian mixture
• Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation
• Stein's method for the TAP equations an iterative scheme for the SK model
• Equivalence of state equations from different methods in high-dimensional regression
• Diaconis-Ylvisaker prior penalized likelihood for p/n(0, 1) logistic regression
• Gradient descent inference in empirical risk minimization
• Uncertainty quantification for iterative algorithms in linear models with application to early stopping

This page was built for publication: State evolution for approximate message passing with non-separable functions

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