Vector Approximate Message Passing

DOI10.1109/TIT.2019.2916359MaRDI QIDQ5211467zbMATH OpenOpenAlexFDO

Authors Sundeep Rangan, Philip Schniter, Alyson K. Fletcher

Publication date 28 January 2020

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

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

Mathematics Subject Classification ID

Random matrices (algebraic aspects) (15B52) Linear regression; mixed models (62J05) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: The standard linear regression (SLR) problem is to recover a vector $mathbf{x}^0$ from noisy linear observations $mathbfy=mathbf{Ax}^0+mathbfw$. The approximate message passing (AMP) algorithm recently proposed by Donoho, Maleki, and Montanari is a computationally efficient iterative approach to SLR that has a remarkable property: for large i.i.d. sub-Gaussian matrices $mathbfA$, its per-iteration behavior is rigorously characterized by a scalar state-evolution whose fixed points, when unique, are Bayes optimal. The AMP algorithm, however, is fragile in that even small deviations from the i.i.d. sub-Gaussian model can cause the algorithm to diverge. This paper considers a "vector AMP" (VAMP) algorithm and shows that VAMP has a rigorous scalar state-evolution that holds under a much broader class of large random matrices $mathbfA$: those that are right-orthogonally invariant. After performing an initial singular value decomposition (SVD) of $mathbfA$, the per-iteration complexity of VAMP can be made similar to that of AMP. In addition, the fixed points of VAMP's state evolution are consistent with the replica prediction of the minimum mean-squared error recently derived by Tulino, Caire, Verd'u, and Shamai. Numerical experiments are used to confirm the effectiveness of VAMP and its consistency with state-evolution predictions.

Cited in

(37)

• Marginals of a spherical spin Glass model with correlated disorder
• Unbiasing in iterative reconstruction algorithms for discrete compressed sensing
• Fundamental barriers to high-dimensional regression with convex penalties
• Approximate message passing algorithms for rotationally invariant matrices
• Asymptotic risk and phase transition of \(l_1\)-penalized robust estimator
• An introduction to compressed sensing
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Hybrid Approximate Message Passing
• Matrix inference and estimation in multi-layer models*
• scientific article; zbMATH DE number 7625169 (Why is no real title available?)
• Bayesian Imaging with Data-Driven Priors Encoded by Neural Networks
• Analysis of random sequential message passing algorithms for approximate inference
• Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
• Denoising AMP for MRI reconstruction: BM3D-AMP-MRI
• Semi-analytic resampling in Lasso
• High-temperature expansions and message passing algorithms
• Semi-analytic approximate stability selection for correlated data in generalized linear models
• A dynamical mean-field theory for learning in restricted Boltzmann machines
• A Unifying Tutorial on Approximate Message Passing
• Replica analysis of overfitting in generalized linear regression models
• scientific article; zbMATH DE number 7750674 (Why is no real title available?)
• APPROXIMATE BAYESIAN INFERENCE AND FORECASTING IN HUGE‐DIMENSIONAL MULTICOUNTRY VARs
• A Friendly Tutorial on Mean-Field Spin Glass Techniques for Non-Physicists
• Universality of approximate message passing with semirandom matrices
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Tight-frame-like analysis-sparse recovery using nontight sensing matrices
• 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
• Approximate message passing with rigorous guarantees for pooled data and quantitative group testing
• Optimality of approximate message passing for spiked matrix models with rotationally invariant noise
• Linear operator approximate message passing (OpAMP)
• Elliptic approximate message passing and an application to theoretical ecology
• Spectral estimators for structured generalized linear models via approximate message passing
• A leave-one-out approach to approximate message passing
• Spectrum-aware debiasing: a modern inference framework with applications to principal components regression
• Optimal thresholds and algorithms for a model of multi-modal learning in high dimensions

This page was built for publication: Vector Approximate Message Passing

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