On the Convergence of Approximate Message Passing With Arbitrary Matrices

DOI10.1109/TIT.2019.2913109MaRDI QIDQ5211372zbMATH OpenOpenAlexWikidataFDO

Authors Sundeep Rangan, Philip Schniter, Alyson K. Fletcher, Subrata Sarkar

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/1402.3210

Mathematics Subject Classification ID

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

Abstract: Approximate message passing (AMP) methods and their variants have attracted considerable recent attention for the problem of estimating a random vector $mathbfx$ observed through a linear transform $mathbfA$. In the case of large i.i.d. zero-mean Gaussian $mathbfA$, the methods exhibit fast convergence with precise analytic characterizations on the algorithm behavior. However, the convergence of AMP under general transforms $mathbfA$ is not fully understood. In this paper, we provide sufficient conditions for the convergence of a damped version of the generalized AMP (GAMP) algorithm in the case of quadratic cost functions (i.e., Gaussian likelihood and prior). It is shown that, with sufficient damping, the algorithm is guaranteed to converge, although the amount of damping grows with peak-to-average ratio of the squared singular values of the transforms $mathbfA$. This result explains the good performance of AMP on i.i.d. Gaussian transforms $mathbfA$, but also their difficulties with ill-conditioned or non-zero-mean transforms $mathbfA$. A related sufficient condition is then derived for the local stability of the damped GAMP method under general cost functions, assuming certain strict convexity conditions.

Cited in

(16)

• 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
• Approximate Message Passing With Consistent Parameter Estimation and Applications to Sparse Learning
• Bilinear Generalized Approximate Message Passing—Part I: Derivation
• Hybrid Approximate Message Passing
• Convergence of Min-Sum Message Passing for Quadratic Optimization
• scientific article; zbMATH DE number 7625169 (Why is no real title available?)
• Compressive Computed Tomography Reconstruction through Denoising Approximate Message Passing
• Analysis of Approximate Message Passing With Non-Separable Denoisers and Markov Random Field Priors
• Denoising AMP for MRI reconstruction: BM3D-AMP-MRI
• A message-passing approach to phase retrieval of sparse signals
• Semi-analytic resampling in Lasso
• A Unifying Tutorial on Approximate Message Passing
• Replica analysis of overfitting in generalized linear regression models
• A tradeoff between false discovery and true positive proportions for sparse high-dimensional logistic regression

This page was built for publication: On the Convergence of Approximate Message Passing With Arbitrary Matrices

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