Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem
Abstract
Approximate message passing (AMP) provides fast iterative algorithms for high-dimensional signal recovery with Gaussian design matrices, while the Convex Gaussian Min--max Theorem (CGMT) gives a static optimization framework for obtaining sharp asymptotic characterizations of convex estimators. Although these two frameworks often lead to the same scalar state-evolution equations, their connection is usually indirect. In this paper, we establish a direct connection between the two for regularized linear regression in the proportional high-dimensional regime. When the CGMT Auxiliary Optimization (AO) and Primary Optimization (PO) give the same primal-dual solution, we show that the CGMT framework recovers the AMP fixed-point equations, including the Onsager correction. We further identify the AO Gaussian vectors with the Gaussian perturbations in the primal and residual AMP channels. For regularized M-estimation, the same viewpoint recovers the fixed point of scalar-variance max-sum Generalized AMP (GAMP). These results show that the AMP (and GAMP) fixed-point equations can be recovered from the CGMT framework and may suggest AMP-like algorithms in settings where standard derivations are unavailable.
Related
- Quantitative Universality of Approximate Message Passing for Rank-One Quadratic Sensing
- Universality of approximate message passing under a fourth-moment tail condition
- On the State Evolution of Approximate Message Passing with Discontinuous Denoisers
- Almost Sharp Equivalence between Approximate Message Passing and Low-Degree Polynomials
- DAIF: A Data-Driven Intermediate Fusion Framework for Multimodal Supervised Learning via Approximate Message Passing
BibTeX
@misc{malik2026deriving,
title = {{Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem}},
author = {Vikrant Malik and Babak Hassibi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.27769},
eprint = {2606.27769},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.27769},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Deriving Approximate Message Passing from the Convex Gaussian Min-Max Theorem
AU - Vikrant Malik
AU - Babak Hassibi
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2606.27769
UR - https://arxiv.org/abs/2606.27769
AB - Approximate message passing (AMP) provides fast iterative algorithms for high-dimensional signal recovery with Gaussian design matrices, while the Convex Gaussian Min--max Theorem (CGMT) gives a static optimization framework for obtaining sharp asymptotic characterizations of convex estimators. Although these two frameworks often lead to the same scalar state-evolution equations, their connection is usually indirect. In this paper, we establish a direct connection between the two for regularized linear regression in the proportional high-dimensional regime. When the CGMT Auxiliary Optimization (AO) and Primary Optimization (PO) give the same primal-dual solution, we show that the CGMT framework recovers the AMP fixed-point equations, including the Onsager correction. We further identify the AO Gaussian vectors with the Gaussian perturbations in the primal and residual AMP channels. For regularized M-estimation, the same viewpoint recovers the fixed point of scalar-variance max-sum Generalized AMP (GAMP). These results show that the AMP (and GAMP) fixed-point equations can be recovered from the CGMT framework and may suggest AMP-like algorithms in settings where standard derivations are unavailable.
ER -