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

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) 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.