Deriving Approximate Message Passing from the Convex Gaussian Min–Max Theorem

Vikrant Malik, Babak Hassibi · 2026

Read Deriving Approximate Message Passing from the Convex Gaussian Min–Max Theorem by Vikrant Malik, Babak Hassibi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-27769.txt.

Introduction

Two frameworks dominate high-dimensional signal recovery. Approximate message passing gives fast iterative algorithms. The Convex Gaussian Min–Max Theorem gives asymptotic descriptions of convex estimators. Both often produce the same state-evolution equations. Their link has usually been indirect. Vikrant Malik and Babak Hassibi make the link direct in 2026, for regularised linear regression.

The bridge uses the theorem's two optimisations, called primary and auxiliary. When both yield the same primal-dual solution, the static framework recovers the dynamic one. The message-passing fixed-point equations come out, including the Onsager correction. The auxiliary problem's Gaussian vectors match the perturbations in its primal and residual channels. The same viewpoint handles regularised M-estimation. It recovers the fixed point of scalar-variance max-sum generalised message passing. A general payoff is suggested: new message-passing-like algorithms may be derived wherever the min–max theorem applies, where standard derivations are missing.

Catalog record

CREATORVikrant Malik, Babak Hassibi
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE47 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.27769

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Deriving Approximate Message Passing from the Convex Gaussian Min–Max Theorem Vikrant Malik, Babak Hassibi 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 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) iterations are suggested, and can be derived, from the CGMT framework, and may further suggest a way to derive AMP-like algorithms in settings where CGMT applies but standard AMP derivations are unavailable. I Introduction Signal recovery from noisy linear measurements is a central problem in high-dimensional statistics, information theory, and machine learning. Given observations of the form y=Ax_{0}+w , with A\in\mathbb{R}^{m\times n} , x_{0}\in\mathbb{R}^{n} , and y,w\in\mathbb{R}^{m} , the goal is to reconstruct the unknown signal x_{0} from m measurements in ambient dimension n . This model captures a wide range of applications, including compressed sensing, sparse regression, imaging, wireless communication, and feature selection in modern data analysis. Over the past few years, substantial effort has been devoted to understanding the performance characterizations for standard high-dimensional estimators (linear regression and its regularized versions) in the proportional high-dimensional regime, where the ambient dimension and number of measurements grow at a fixed ratio. A recurring theme in the literature is to analyze the resulting random optimization problems via either the CGMT (a convex extension of Gordon’s Gaussian min-max comparison inequality [ 3 , 4 , 5 , 6 ] ), or via AMP [ 21 , 7 , 9 , 22 ] . When the measurement matrix is Gaussian, both approaches show that the estimation error is described by just a few scalar quantities which can be obtained by solving a deterministic, scalar optimization problem. These same quantities can then be used to predict performance metrics like the norm and geometry of the recovered signal, margins, and the resulting estimation or classification error [ 6 , 7 ] . In [ 6 ] , a general CGMT-based framework is developed that yields asymptotically exact predictions for broad classes of losses and regularizers, and characterizes performance in the proportional regime where m and n grow proportionally. In the supervised learning literature, explicit test-error characterizations have been derived for linear models learned via regression-style estimators under Gaussian-mixture-type models [ 26 ] . Another closely related work [ 27 ] provides sharp benchmarks for parameter estimation with binary observations. More broadly, the CGMT has been used to analyze nonlinear Gaussian models [ 13 ] , binary and Gaussian-mixture classification [ 14 , 15 , 16 ] , ridge-regularized ERM in generalized linear models [ 17 ] , multiclass classification [ 18 ] , and distributionally robust binary learning [ 28 ] . Despite their common asymptotic predictions, CGMT and AMP have usually been viewed as tools of a different nature. The CGMT is a static comparison theorem. It compares a Primary Optimization ( 1 ) (PO) with an Auxiliary Optimization ( 2 ) (AO): \displaystyle\Phi(A) \displaystyle=\min_{w\in\mathcal{S}_{w}}\max_{u\in\mathcal{S}_{u}}\;u^{\top}Aw+\psi(w,u), (1) \displaystyle\phi(g,h) \displaystyle=\min_{w\in\mathcal{S}_{w}}\max_{u\in\mathcal{S}_{u}}\;\left\lVert w\right\rVert_{2}\,g^{\top}u+\left\lVert u\right\rVert_{2}\,h^{\top}w+\psi(w,u), (2) where A,g, and h have i.i.d. standard normal entries. Under convexity and compactness assumptions, the optimal values of ( 1 ) and ( 2 ) concentrate together, and properties of optimizers can be transferred from the AO to the PO. This is stated formally later in Theorem 2 . The analytic simplification in the AO comes from the replacement of the matrix bilinear term u^{\top}Aw by the two decoupled Gaussian terms \left\lVert w\right\rVert_{2}g^{\top}u and \left\lVert u\right\rVert_{2}h^{\top}w . This decoupling makes the AO amenable to analysis. It also motivates the question pursued in this paper: for a given PO solution, which auxiliary Gaussian vectors g,h would make the AO KKT system select the same primal-dual solution? Within this framework, we first study the quadratic regularized regression problem \hat{x}\in\argmin_{x\in\mathbb{R}^{n}}\left\{\frac{1}{2}\left\lVert y-Ax\right\rVert_{2}^{2}+\lambda F(x)\right\}, (3) where F is a separable convex regularizer and \lambda>0 . Setting e=x-x_{0} and G=\sqrt{m}\,A , the Fenchel dual of the quadratic loss gives the min–max Primary Optimization \displaystyle\Phi(G) \displaystyle=\min_{e\in\mathbb{R}^{n}}\max_{u\in\mathbb{R}^{m}}\Bigl\{-\frac{1}{\sqrt{m}}u^{\top}Ge+u^{\top}w (4) \displaystyle-\frac{1}{2}\left\lVert u\right\rVert_{2}^{2}+\lambda F(x_{0}+e)\Bigr\}. Since G has i.i.d. standard normal entries, ( 4 ) is an instance of the CGMT PO form ( 1 ), with e as the primal variable and u as the dual variable. The corresponding AO ( 13 ) replaces the matrix bilinear term in ( 4 ) by separated Gaussian terms, producing an optimization with the same saddle variables but a more tractable Gaussian structure. To solve the quadratic objective above, the basic proximal-gradient method is ISTA. With stepsize \gamma>0 , its recursions are \displaystyle r^{t} \displaystyle=y-Ax^{t}, (5) \displaystyle v^{t} \displaystyle=x^{t}+\gamma A^{\top}r^{t}, (6) \displaystyle x^{t+1} \displaystyle=\eta(v^{t};\lambda\gamma), (7) The scalar map \eta used here and throughout is defined by writing F(x)=\sum_{i=1}^{n}f(x_{i}) and setting \displaystyle\eta(v;\theta) \displaystyle=\prox_{\theta f}(v) (8) \displaystyle:=\argmin_{x\in\mathbb{R}}\left\{\frac{1}{2}(x-v)^{2}+\theta f(x)\right\},\quad\theta>0. We apply \eta coordinatewise to vectors. These iterations represent proximal gradient descent applied to ( 3 ). AMP, on the other hand, is an algorithmic method whose iterates are tracked by state evolution. It was introduced for compressed sensing [ 21 ] , formalized in [ 7 ] , and used to characterize the LASSO risk for Gaussian designs [ 8 ] . Subsequent extensions include broader AMP recursions, spatial coupling, universality, nonseparable nonlinearities, and variants such as GAMP, D-AMP, VAMP, and OAMP [ 9 , 10 , 11 , 12 , 22 , 23 , 24 , 25 ] . For the linear model above, the standard AMP recursion with m/n\to\delta is \displaystyle v^{t} \displaystyle=x^{t}+A^{\top}z^{t}, (9) \displaystyle x^{t+1} \displaystyle=\eta_{t}(v^{t}), (10) \displaystyle z^{t} \displaystyle=y-Ax^{t}+\underbrace{\frac{1}{\delta}z^{t-1}\bigl\langle\eta_{t-1}^{\prime}(v^{t-1})\bigr\rangle}_{\text{Onsager correction}}, (11) where \eta_{t} is a coordinatewise denoising function and \langle\cdot\rangle denotes the empirical average. For large Gaussian design matrices, AMP is often computationally faster compared to generic first-order convex solvers such as ISTA and FISTA [ 1 , 2 ] , because its iterates are tailored to the random matrix geometry through the Onsager correction term. Thus AMP has the same proximal update structure as ISTA, but replaces the raw residual by the Onsager-corrected residual in ( 11 ). The motivation for the correction term is that it cancels the correlation between the current iterate and the measurement matrix A , making the effective input to the denoiser behave asymptotically as the true signal plus independent Gaussian noise. Previous works have noticed that the state equations arising from AMP and from CGMT reductions can be equivalent after suitable changes of variables [ 16 , 19 , 20 ] . In this paper, we make this connection explicit for M -estimation. Starting from the CGMT framework, we show how the scalar saddle point of the AO, its stationarity conditions, and the auxiliary Gaussian vectors recover

Read the complete text