1 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 [1]–[4]), or via AMP [5]–[8]. 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 [4], [6]. In [4], 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 [9]. Another closely related work [10] provides sharp benchmarks for parameter estimation with binary observations. More broadly, the CGMT has been used to analyze nonlinear Gaussian models [11], binary and Gaussian-mixture classification [12]–[14], ridge-regularized ERM in generalized linear models [15], multiclass classification [16], and distributionally robust binary learning [17].

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): \[\begin{align} \Phi(A)&=\min_{w\in\mathcal{S}_w}\max_{u\in\mathcal{S}_u}\; u^\top A w+\psi(w,u), \tag{1}\\ \phi(g,h)&=\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), \tag{2} \end{align}\] 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 A w\) 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 \[\label{eq:rlr} \hat{x}\in\mathop{\mathrm{arg\,min}}_{x\in\mathbb{R}^n} \left\{\frac{1}{2}\left\lVert y-Ax \right\rVert_2^2+\lambda F(x)\right\},\tag{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 \[\label{eq:po95rlr} \begin{align} \Phi(G)&=\min_{e\in\mathbb{R}^n}\max_{u\in\mathbb{R}^m} \Bigl\{-\frac{1}{\sqrt{m}}u^\top G e+u^\top w\\ & -\frac{1}{2}\left\lVert u \right\rVert_2^2+\lambda F(x_0+e)\Bigr\}. \end{align}\tag{4}\] 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 12 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 \[\begin{align} r^t &= y-Ax^t, \tag{5}\\ v^t &= x^t+\gamma A^\top r^t, \tag{6}\\ x^{t+1} &= \eta(v^t;\lambda\gamma), \tag{7} \end{align}\] The scalar map \(\eta\) used here and throughout is defined by writing \(F(x)=\sum_{i=1}^n f(x_i)\) and setting \[\label{eq:prox} \begin{align} \eta(v;\theta) &=\mathop{\mathrm{prox}}_{\theta f}(v)\\ &:=\mathop{\mathrm{arg\,min}}_{x\in\mathbb{R}} \left\{\frac{1}{2}(x-v)^2+\theta f(x)\right\}, \quad \theta>0 . \end{align}\tag{8}\] 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 [5], formalized in [6], and used to characterize the LASSO risk for Gaussian designs [18]. Subsequent extensions include broader AMP recursions, spatial coupling, universality, nonseparable nonlinearities, and variants such as GAMP, D-AMP, VAMP, and OAMP [7], [8], [19]–[24].

For the linear model above, the standard AMP recursion with \(m/n\to\delta\) is \[\begin{align} v^t &= x^t+A^\top z^t,\tag{9}\\ x^{t+1} &= \eta_t(v^t),\tag{10}\\ z^t &= y-Ax^t+ \underbrace{\frac{1}{\delta}z^{t-1} \bigl\langle\eta_{t-1}'(v^{t-1})\bigr\rangle} _{\text{Onsager correction}},\tag{11} \end{align}\] 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 [25], [26], 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 [14], [27], [28]. 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 the fixed-point structure and state-evolution equations of AMP and GAMP.

1.1 Contributions↩︎

1. Under the proportional high-dimensional regime with Gaussian design matrices, and for the regularized linear regression problem, we show that the fixed-point equations of the AMP recursion 9 –11 can be recovered using only the CGMT framework under the assumption that the AO and PO solutions match. In particular, the scalar saddle point obtained from the CGMT auxiliary optimization determines the Onsager coefficient appearing in the fixed-point equations. This is formally stated in Theorem 3.

2. More generally, for separable smooth output losses, we show that the same stationarity comparison recovers the fixed point of scalar-variance max-sum GAMP. This connection is detailed in Section 4 and Appendix 6.

3. We provide an asymptotic interpretation of the AO Gaussian vectors. Under the assumption that the AO and PO solutions match, \(h\) determines the noise in primal AMP channel \(v^* \approx x_0+\tau_*h\), while \(g\) determines the noise in the residual AMP channel \(z^* \approx w+\sigma_*g\). This is formally stated in Theorem 4 and Theorem 6.

This connection shows how the AMP (and GAMP) can be derived from CGMT, and suggests a possible route for algorithm design beyond the settings where standard AMP applies directly. The CGMT can handle a range of convex losses, regularizers, and robust variants. Understanding when its stationarity structure has an AMP-like interpretation may help derive new iterative schemes for problems where the usual AMP construction does not fit cleanly.

1.2 Organization↩︎

The paper is organized as follows. Section 2 introduces the notation, the observation model, the regularized linear regression problem, and reviews the AMP and CGMT frameworks. Section 3 and Section 4 state the main results: the recovery of the AMP and GAMP fixed-point equations from the CGMT and an interpretation of the AO Gaussian vectors.

2 Notation and Problem Setup↩︎

2.1 Notation↩︎

For a vector \(a\in\mathbb{R}^N\), write \(\langle a\rangle=N^{-1}\sum_{i=1}^N a_i\). We write \(X\sim p_X\) to denote that \(X\) has law \(p_X\), and reserve \(Z\) for a standard normal random variable independent of all other scalar variables unless stated otherwise. The symbols \(\xrightarrow{p}\) and \(\xrightarrow{\mathrm{a.s.}}\) denote convergence in probability and almost sure convergence, respectively. The regularizer is separable. Throughout, \(f:\mathbb{R}\to(-\infty,\infty]\) is proper, closed, and convex, and for \(x \in \mathbb{R}^n\), \(F(x)=\sum_{i=1}^n f(x_i)\). The scalar map \(\eta\) is defined in 8 and is applied coordinatewise to vectors. The LASSO corresponds to the choice \(f(x)=|x|\).

2.2 Problem Setup↩︎

We consider instances of \(y=Ax_0+w\) in the proportional regime \(m,n\to\infty\) with \(m/n\to\delta\in(0,\infty)\). The matrix \(A\in\mathbb{R}^{m\times n}\) has independent entries \(A_{ij}\sim\mathcal{N}(0,1/m)\) and is independent of the signal and noise, whose entries satisfy \(x_{0,i}\stackrel{\mathrm{i.i.d.}}{\sim}p_{X_0}\) and \(w_j\stackrel{\mathrm{i.i.d.}}{\sim}p_W\). We write \(\sigma_0^2:=\delta^{-1}\mathbb{E}[X_0^2]\) and \(\sigma_w^2:=\mathbb{E}[W^2]\), and study the estimator 3 .

This estimator is the squared-loss, separable-regularizer instance of the regularized \(M\)-estimators analyzed in [4].

2.3 AMP analysis↩︎

We use the AMP recursion 9 –11 introduced in the Introduction. In the proximal setting considered here, the coordinatewise denoiser is \(\eta_t(v)=\eta(v;\theta_t)\), where \(\eta\) is defined in 8 . The associated state evolution is formally stated as follows.

Informally, Theorem 1 says that, for every fixed iteration \(t\), the high-dimensional AMP iterates decouple into scalar Gaussian channels as \(m,n\to\infty\). The input to the denoiser behaves coordinatewise as \[(v^t)_i \;\approx\; X_0+\tau_t Z,\] so the next estimate behaves as \(\eta(X_0+\tau_t Z;\theta_t)\). Similarly, the residual behaves in empirical distribution as \[(z^t)_i \;\approx\; W+\sigma_t Z.\] Thus the full AMP trajectory is asymptotically summarized by the scalar state variables \((\tau_t,\sigma_t)\).

2.4 CGMT Analysis↩︎

This subsection revisits the CGMT reduction for regularized linear regression from [4] and the scalar saddle equations used later. The CGMT is formally stated as follows.

For the regularized regression problem 3 , we use the PO 4 introduced in the Introduction, with \(e=x-x_0\) and \(G=\sqrt m A\). We now record only the corresponding AO and its scalar reduction. The corresponding auxiliary optimization is \[\label{eq:ao95rlr} \begin{align} \phi(g,h)&=\min_{e\in\mathbb{R}^n}\max_{u\in\mathbb{R}^m} \Bigl\{\frac{\left\lVert e \right\rVert_2}{\sqrt{m}}g^\top u -\frac{\left\lVert u \right\rVert_2}{\sqrt{m}}h^\top e\\ & +u^\top w-\frac{1}{2}\left\lVert u \right\rVert_2^2+\lambda F(x_0+e)\Bigr\}, \end{align}\tag{12}\] where \(g\sim\mathcal{N}(0,I_m)\) and \(h\sim\mathcal{N}(0,I_n)\) are independent.² Scalarizing 12 yields the deterministic saddle \[\label{eq:D95tau95beta} \begin{align} \max_{\beta\ge 0}\min_{\tau>0}\quad &\frac{\delta\beta\sigma_w^2}{2\tau} +\frac{\delta\beta\tau}{2} -\frac{\delta\beta^2}{2} -\frac{\beta\tau}{2} +\mathcal{M}(\tau,\beta), \end{align}\tag{13}\] where the envelope term is \[\label{eq:M95def} \begin{align} \mathcal{M}(\tau,\beta) :=\mathbb{E}_{X_0,H}\!\left[ \min_{x\in\mathbb{R}}\left\{ \frac{\beta}{2\tau}(x-X_0+\tau H)^2 +\lambda f(x)\right\}\right]. \end{align}\tag{14}\] Here, \(X_0\sim p_{X_0}\) and \(H\sim\mathcal{N}(0,1)\) is independent of \(X_0\). Let \((\tau_*,\beta_*)\) denote the saddle point and define \[\label{eq:theta95star} \theta_*:=\frac{\lambda\tau_*}{\beta_*}, \qquad \sigma_*^2:=\tau_*^2-\sigma_w^2.\tag{15}\] The inner minimization in the envelope term 14 is equivalent to the proximal problem defined in 8 . For fixed \((\tau,\beta)\), the minimizer in 14 is \(\eta(X_0-\tau H;\lambda\tau/\beta)\).

3 Main Results↩︎

We now present our main results. Theorem 3 states that at the scalar CGMT saddle point, the AO and PO optimality conditions together have the structure of an AMP fixed point.

We now state the assumptions under which the CGMT PO and AO can be compared in terms of their optimizers. The motivation is the high-dimensional interpretation of the CGMT: for Gaussian \(A\), the PO and AO optimal values and optimizer properties concentrate around the same deterministic scalar saddle. Thus, in the proportional limit, it is natural to study a setting in which there exist realizations of the auxiliary Gaussian vectors \(g,h\) for which the AO and PO select the same primal-dual solution.

Assumption 1 implicitly couples \(g,h\). However, we still take \(g,h\) to be independent standard Gaussian AO realizations. Making this coupling fully rigorous is left for future work. See Appendix 6.2 for further discussion. After Assumption 1, the remaining issue is that the regularizer may be nonsmooth, so the AO and PO stationarity equations must also select a common subgradient at the shared optimizer. We formalize this in Assumption 2. The matched AO and PO optimizers have the same \(x^*\), but their KKT equations may select different elements of the set \(\partial F(x^*)\). We assume that there is a common \(s^*\in\partial F(x^*)\) satisfying both AO and PO stationarity equations. This is always true when \(F\) is differentiable at \(x^*\).

The assumptions above allow us to compare the AO and PO at the optimal solutions. The next theorem uses this assumption to recover the AMP fixed-point equations from the CGMT scalar saddle point equations. The following theorem then relates the AO Gaussian vectors themselves with the corresponding primal and residual AMP channels.

We now show that under Assumption 1, the Gaussian-vectors \(g, h\) in the AO correspond to the effective channels in the AMP.

Equations ?? and ?? follow from the stationarity relations 17 –20 ; the detailed proof is given in Appendix 5.

4 Extension to General Output Losses↩︎

We now extend the analysis to non-quadratic output losses. For a separable, proper, closed and convex loss \(L(r)=\sum_{i=1}^m\ell(r_i)\), the estimator of interest is \[\label{eq:smooth95loss95problem} \hat{x} \in \arg\min_{x\in\mathbb{R}^n} L(y-Ax)+\lambda F(x).\tag{16}\] This can be written in Fenchel-dual form, producing a PO–AO pair with the same bilinear/separated Gaussian structure as in the squared-loss case. The detailed proofs for this section are provided in Appendix 6. Let \(e=x-x_0\) and \(w=y-Ax_0\). Moreover, for \(\tau_p>0\) and \(\tau_r>0\), define the output and input proximal maps \[\begin{align} g_{\rm out}(a,\tau_p) &:= \frac{a-\mathop{\mathrm{prox}}_{\tau_p L}(a)}{\tau_p},\\ g_{\rm in}(r_{\rm in},\tau_r) &:= \mathop{\mathrm{prox}}_{\lambda\tau_r F}\left(r_{\rm in}\right), \end{align}\] with the proximal maps applied coordinatewise.

Appendix 6 contains the proofs for Theorems 5 and 6.

Taken together, Theorem 3 (and Theorem 5) recover the AMP (and GAMP) fixed points using only the CGMT framework for regularized \(M\)-estimation. Theorem 4 and (Theorem 6) then provide an interpretation of AO Gaussian vectors as the channel noise in the AMP (and GAMP) channels.

5 Proofs of the Main Results↩︎

5.1 Proof of Theorem 3↩︎

We first compare the exact finite AO and PO KKT systems. At the matched saddle of the AO 12 , the \(e\)-stationarity condition gives \[0\in \frac{g^\top u^*}{\sqrt m\,\left\lVert e^* \right\rVert_2}e^* -\frac{\left\lVert u^* \right\rVert_2}{\sqrt m}h +\lambda\partial F(x_0+e^*) .\] Assuming \(\left\lVert e^* \right\rVert_2>0\), define the coefficients \[\widehat\beta :=\frac{\left\lVert u^* \right\rVert_2}{\sqrt m}, \qquad \widehat\mu :=\frac{g^\top u^*}{\sqrt m\,\left\lVert e^* \right\rVert_2},\] and set \[\widehat\tau:=\frac{\widehat\beta}{\widehat\mu}, \qquad \widehat\theta:=\frac{\lambda}{\widehat\mu}.\] With \(x^*=x_0+e^*\), the AO 12 KKT condition is therefore equivalent to the existence of \(s^*\in\partial F(x^*)\) such that \[\label{eq:ao95kkt95for95amp} x_0+\widehat\tau h-x^*=\widehat\theta s^* .\tag{17}\] Equivalently, \[x^*=\eta(x_0+\widehat\tau h;\widehat\theta) .\] The PO KKT condition is \[\label{eq:po95kkt95for95amp} A^\top(y-Ax^*)=\lambda s^*, \qquad s^*\in\partial F(x^*) .\tag{18}\] Assumption 2 allows the same selected subgradient \(s^*\) to be used in the AO and PO stationarity equations. Since \(\lambda/\widehat\theta=\widehat\mu\), combining 17 and 18 gives \[A^\top(y-Ax^*) =\widehat\mu(x_0+\widehat\tau h-x^*).\] Dividing by \(\widehat\mu\) and shifting \(x^*\) to the left gives \[\label{eq:main95vz95underbrace} x^*+A^\top \underbrace{\left(\frac{y-Ax^*}{\widehat\mu}\right)}_{=:z^*} = \underbrace{x_0+\widehat\tau h}_{=:v^*}.\tag{19}\] Thus \(v^*=x^*+A^\top z^* = x_0+\widehat\tau h\). Substituting this identity into the AO proximal relation 17 gives \[x^*=\eta(v^*;\widehat\theta)= \eta(x^*+A^\top z^*;\widehat\theta),\] which is ?? ; the definition of \(v^*\) gives ?? . Set \(c^*:=1-\widehat\mu\). Since \(y-Ax^*=\widehat\mu z^*\), \[z^*=y-Ax^*+c^*z^*,\] which is ?? .

It remains to relate the finite KKT coefficients above to the scalar AO variables. Let \[a^*:=w+\frac{\left\lVert e^* \right\rVert_2}{\sqrt m}g, \qquad \bar\tau:=\frac{\left\lVert a^* \right\rVert_2}{\sqrt m}.\] The maximization over the direction of \(u\) in the AO 12 aligns \(u^*\) with \(a^*\), so \(g^\top u^*=\left\lVert u^* \right\rVert_2 g^\top a^*/\left\lVert a^* \right\rVert_2\). Hence \[\begin{align} \frac{\widehat\tau}{\bar\tau} &= \frac{\left\lVert e^* \right\rVert_2\left\lVert a^* \right\rVert_2}{g^\top a^*} \frac{\sqrt m}{\left\lVert a^* \right\rVert_2} \\ &= \frac{\sqrt m\,\left\lVert e^* \right\rVert_2}{g^\top\left(w+\frac{\left\lVert e^* \right\rVert_2}{\sqrt m}g\right)} = \left( \frac{\left\lVert g \right\rVert_2^2}{m} +\frac{g^\top w}{\sqrt m\,\left\lVert e^* \right\rVert_2} \right)^{-1}. \end{align}\] The scalarized AO 13 calibrates \(\bar\tau\) and \(\widehat\beta\): \[\bar\tau-\tau_*\xrightarrow{p}0, \qquad \widehat\beta-\beta_*\xrightarrow{p}0.\] Moreover, the scalar AO error-norm calibration gives \(\left\lVert e^* \right\rVert_2/\sqrt m\xrightarrow{p}\sigma_*\), and the assumption \(\sigma_*^2=\tau_*^2-\sigma_w^2>0\) keeps this denominator bounded away from zero with high probability. Thus \(\left\lVert g \right\rVert_2^2/m\xrightarrow{p}1\) and \(g^\top w/(\sqrt m\,\left\lVert e^* \right\rVert_2)\xrightarrow{p}0\) imply \(\widehat\tau/\bar\tau\xrightarrow{p}1\). Therefore \[\widehat\tau-\tau_*\xrightarrow{p}0, \qquad \widehat\mu-\frac{\beta_*}{\tau_*}\xrightarrow{p}0, \qquad \widehat\theta-\theta_*\xrightarrow{p}0 .\] Let \(\mu_*:=\beta_*/\tau_*\). Since \(c^*=1-\widehat\mu\), the convergence above gives \(c^*-(1-\mu_*)\xrightarrow{p}0\). By ?? , \[1-\mu_* =\frac{1}{\delta}\mathbb{E}[\eta'(X_0-\tau_*H;\theta_*)].\] Together with \(v^*=x_0+\widehat\tau h\) and \(\widehat\theta-\theta_*\xrightarrow{p}0\), this yields \[c^* -\frac{1}{\delta} \bigl\langle\eta'(v^*;\widehat\theta)\bigr\rangle \xrightarrow{p}0,\] namely ?? .

5.2 Proof of Theorem 4↩︎

Equation 19 gives \(v^*=x^*+A^\top z^*=x_0+\widehat\tau h\), and Theorem 3 gives \(\widehat\tau-\tau_*\xrightarrow{p}0\).

It remains to identify the residual Gaussian channel. Define \[\begin{align} \widehat\sigma:=\frac{\left\lVert e^* \right\rVert_2}{\sqrt m}, \qquad& a^*:=w+\widehat\sigma g,\\ \bar\tau:=\frac{\left\lVert a^* \right\rVert_2}{\sqrt m}, \qquad& \widehat\kappa:= \frac{h^\top e^*}{\sqrt m\,\left\lVert u^* \right\rVert_2}. \end{align}\] The vector AO 12 \(u\)-stationarity condition is \[\label{eq:kkt95ao95u95simplified} 0=\widehat\sigma g+w-u^*-\widehat\kappa u^*, \qquad\text{hence}\qquad (1+\widehat\kappa)u^*=w+\widehat\sigma g .\tag{20}\] On the PO side, \(u\)-stationarity gives \(u^*=w-Ae^*=y-Ax^*\). Since Theorem 3 defines \(z^*=(y-Ax^*)/\widehat\mu\), we have \(u^*=\widehat\mu z^*\). Set \(\widehat k:=\widehat\mu(1+\widehat\kappa)\). Substituting this into 20 gives \[\widehat k z^*=w+\widehat\sigma g,\] which is ?? . The AO 12 maximization over the direction of \(u\) gives \[u^*=\frac{\left\lVert u^* \right\rVert_2}{\left\lVert a^* \right\rVert_2}a^* =\frac{\widehat\beta}{\bar\tau}(w+\widehat\sigma g).\] Comparing this with \((1+\widehat\kappa)u^*=w+\widehat\sigma g\) gives \(1+\widehat\kappa=\bar\tau/\widehat\beta\). Hence the scalar bridge in the proof of Theorem 3 gives \[\widehat k = \widehat\mu(1+\widehat\kappa) =\frac{\widehat\beta}{\widehat\tau} \frac{\bar\tau}{\widehat\beta} =\frac{\bar\tau}{\widehat\tau} \xrightarrow{p}1.\] Finally, the scalar AO norm calibration gives \(\widehat\sigma-\sigma_*\xrightarrow{p}0\).

5.3 Scalar AO Derivation↩︎

Starting from the AO 12 , write \(\left\lVert u \right\rVert_2=\beta\sqrt{m}\) with \(\beta\ge 0\). Maximizing over the direction of \(u\) aligns \(u\) with \(w+\left\lVert e \right\rVert_2g/\sqrt{m}\), giving \[\begin{align} \phi(g,h) =\min_{e\in\mathbb{R}^n}\max_{\beta\ge0}\Biggl\{ &\beta\sqrt{m}\left\| w+\frac{\left\lVert e \right\rVert_2}{\sqrt{m}}g \right\|_2-\beta h^\top e\\ &-\frac{m\beta^2}{2} +\lambda F(x_0+e)\Biggr\}. \end{align}\] Since \(g\) is independent of \(w\), \[\frac{1}{\sqrt{m}}\left\|\frac{\left\lVert e \right\rVert_2}{\sqrt{m}}g+w\right\|_2 \xrightarrow{p} \sqrt{\frac{\left\lVert e \right\rVert_2^2}{m}+\sigma_w^2}.\] Introducing \(\tau>0\) through \(\sqrt{x}=\min_{\tau>0}\{x/(2\tau)+\tau/2\}\) gives a convex-concave optimization in \((e,\tau,\beta)\). After normalization by \(n\), and using \(m/n\to\delta\), the scalarized AO is \[\begin{align} \max_{\beta\ge0}\min_{\tau>0}\min_{e\in\mathbb{R}^n} \Biggl\{ &\frac{\delta\beta\sigma_w^2}{2\tau} +\frac{\delta\beta\tau}{2} -\frac{\delta\beta^2}{2} +\frac{1}{n}\sum_{i=1}^n\\ &\left[ \frac{\beta}{2\tau}e_i^2-\beta h_i e_i +\lambda f(x_{0,i}+e_i) \right]\Biggr\}. \end{align}\] For fixed \((\tau,\beta)\), the minimization over \(e\) now separates coordinatewise. Completing the square gives \[\begin{align} \frac{\beta}{2\tau}e_i^2-\beta h_i e_i +\lambda f(x_{0,i}+e_i) &= \frac{\beta}{2\tau}(e_i-\tau h_i)^2\\ &\quad +\lambda f(x_{0,i}+e_i) -\frac{\beta\tau}{2}h_i^2 . \end{align}\] With \(x=x_0+e_i\), this coordinate problem is \[\min_{x\in\mathbb{R}}\left\{ \frac{\beta}{2\tau}\bigl(x-(x_0+\tau h)\bigr)^2+\lambda f(x) \right\}.\] Since \(h\) and \(-h\) have the same distribution, this yields the same limiting envelope 14 . Therefore the limiting scalar objective is \[D(\tau,\beta) :=\frac{\delta\beta\sigma_w^2}{2\tau} +\frac{\delta\beta\tau}{2} -\frac{\delta\beta^2}{2} -\frac{\beta\tau}{2} +\mathcal{M}(\tau,\beta),\] where \(\mathcal{M}\) is defined in 14 . Applying the law of large numbers gives the scalar saddle \(\max_{\beta\ge0}\min_{\tau>0}D(\tau,\beta)\), equivalently 13 .

Let \(\widehat X=\eta(X_0-\tau H;\lambda\tau/\beta)\) and \(V=X_0-\tau H\). The envelope theorem gives \[\begin{align} 0=\partial_\tau D =&-\frac{\delta\beta\sigma_w^2}{2\tau^2} +\frac{\delta\beta}{2}-\frac{\beta}{2}\\ &-\frac{\beta}{2\tau^2}\mathbb{E}[(\widehat X-V)^2] +\frac{\beta}{\tau}\mathbb{E}[(\widehat X-V)H]. \end{align}\] Using \[\mathbb{E}[(\widehat X-V)^2]-2\tau\mathbb{E}[(\widehat X-V)H] =\mathbb{E}[(\widehat X-X_0)^2]-\tau^2\] yields the state-evolution identity ?? . Similarly, \(\partial_\beta D=0\) implies \[\delta\sigma_w^2+\delta\tau^2-2\delta\beta\tau-\tau^2 +\mathbb{E}[(\widehat X-V)^2]=0.\] Expanding \(\widehat X-V=(\widehat X-X_0)+\tau H\) and applying Stein’s lemma, \[\mathbb{E}[(\widehat X-X_0)H] =-\tau\mathbb{E}[\eta'(X_0-\tau H;\lambda\tau/\beta)],\] together with ?? , gives ?? .

6 Extension to General Output Losses and the Abstract AMP Recursion↩︎

This appendix extends the results to the \(M\)-estimation problem: \[\label{eq:gen95problem} \hat{x} \in \arg\min_{x\in\mathbb{R}^n} L(y-Ax)+\lambda F(x) ,\tag{21}\] where \(L(r)=\sum_{i=1}^m \ell(r_i)\) is a separable convex loss and \(F(x)=\sum_{j=1}^n f(x_j)\) is a separable convex regularizer. Let \(e=x-x_0\) and \(w=y-Ax_0\), so that the residual is \(w-Ae\). Using \[L(r)=\max_{u\in\mathbb{R}^m}\{u^\top r-L^*(u)\},\] the Primary Optimization (PO) can be written as \[\label{eq:po95gen} \begin{align} \Phi(G)=\min_{e\in\mathbb{R}^n}\max_{u\in\mathbb{R}^m} \Bigl\{ &-\frac{1}{\sqrt m}u^\top G e+u^\top w\\ &-L^*(u)+\lambda F(x_0+e) \Bigr\}, \end{align}\tag{22}\] with \(G=\sqrt m A\). The corresponding Auxiliary Optimization (AO) is \[\label{eq:ao95gen} \begin{align} \phi(g,h) &=\min_{e\in\mathbb{R}^n}\max_{u\in\mathbb{R}^m} \Biggl\{ \frac{\left\lVert e \right\rVert_2}{\sqrt m}g^\top u -\frac{\left\lVert u \right\rVert_2}{\sqrt m}h^\top e\\ &\qquad +u^\top w-L^*(u) +\lambda F(x_0+e) \Biggr\}. \end{align}\tag{23}\]

6.1 Problem Setup↩︎

To express the nonlinear loss-side map in primal-loss variables, use the biconjugate representation \[\label{eq:loss95biconjugate} -L^*(u)=\min_{r\in\mathbb{R}^m}\{L(r)-u^\top r\}.\tag{24}\] Thus, at the level of stationarity, we use the residual-augmented PO \[\label{eq:po95gen95residual} \begin{align} \Phi(G) &=\min_{\substack{e\in\mathbb{R}^n\\ r\in\mathbb{R}^m}} \max_{u\in\mathbb{R}^m}\Psi_{\rm PO}(e,u,r),\\ \Psi_{\rm PO}(e,u,r) &=-\frac{1}{\sqrt m}u^\top G e+u^\top w-u^\top r\\ &\quad +L(r)+\lambda F(x_0+e), \end{align}\tag{25}\] and the corresponding residual-augmented AO \[\label{eq:ao95gen95residual} \begin{align} \phi(g,h) &=\min_{\substack{e\in\mathbb{R}^n\\ r\in\mathbb{R}^m}} \max_{u\in\mathbb{R}^m}\Psi_{\rm AO}(e,u,r),\\ \Psi_{\rm AO}(e,u,r) &=\frac{\left\lVert e \right\rVert_2}{\sqrt m}g^\top u -\frac{\left\lVert u \right\rVert_2}{\sqrt m}h^\top e\\ &\quad +u^\top w-u^\top r+L(r)+\lambda F(x_0+e). \end{align}\tag{26}\] ³

6.2 Finite KKT Comparison↩︎

Under Assumptions 3 and 4, let \(s^*\in\partial F(x_0+e^*)\) denote the commonly selected regularizer subgradient. Define the norm scalars and finite-dimensional AO alignment scalars \[\label{eq:kkt95scalars95gen} \begin{align} \widehat\sigma&:=\frac{\left\lVert e^* \right\rVert_2}{\sqrt m}, &\qquad \widehat\beta&:=\frac{\left\lVert u^* \right\rVert_2}{\sqrt m},\\ \widehat\mu&:=\frac{g^\top u^*}{m\widehat\sigma}, &\qquad \widehat\kappa&:=\frac{h^\top e^*}{m\widehat\beta}, \end{align}\tag{27}\] and introduce \[h_*:=\widehat\beta h,\qquad b_*:=\widehat\sigma g .\]

The \(e\), \(u\), and \(r\) stationarity conditions for the PO 25 are \[\begin{align} -A^\top u^*+\lambda s^* &=0, \tag{28}\\ -Ae^*+w-r^* &=0, \tag{29}\\ u^*&\in\partial L(r^*). \tag{30} \end{align}\] The \(e\), \(u\), and \(r\) stationarity conditions for the AO 26 are \[\begin{align} \widehat\mu e^*-h_*+\lambda s^* &=0, \tag{31}\\ b_*-\widehat\kappa u^*+w-r^* &=0, \tag{32}\\ u^*\in\partial L(r^*). \tag{33} \end{align}\] Comparing 28 with 31 , and 29 with 32 , gives \[\begin{align} h_*&=A^\top u^*+\widehat\mu e^*, \tag{34}\\ b_*&=-Ae^*+\widehat\kappa u^*. \tag{35} \end{align}\] These identities also indicate why treating the AO vectors \(g\) and \(h\) as asymptotically independent is plausible. The dependence created by reusing the same matrix \(A\) appears through the selected vectors \(e^*\) and \(u^*\), and the terms \(\widehat\mu e^*\) and \(\widehat\kappa u^*\) remove this leading self-interaction. After this correction, the remaining randomness is expected to behave like independent Gaussian channel noise, as in the usual AMP decoupling arguments. These are the two linear steps of the Bayati–Montanari abstract AMP recursion [6], with \(e^*\) in place of \(q\) and \(u^*\) in place of \(m\).

6.3 Abstract AMP Form and Proof of Theorem 5↩︎

We now derive the nonlinear maps that appear in the proximal relations ?? and ?? of Theorem 5. The linear identities 34 –35 will then convert these maps into the GAMP variables.

First consider the input side. The AO stationarity condition 31 is, for \(\widehat\mu>0\), equivalent to \[0\in e^*-\frac{h_*}{\widehat\mu} +\frac{\lambda}{\widehat\mu}\partial F(x_0+e^*).\] This is exactly the optimality condition for the proximal map \[\label{eq:f95prox95gen} e^* = \mathop{\mathrm{prox}}_{\frac{\lambda}{\widehat\mu}F} \left(x_0+\frac{h_*}{\widehat\mu}\right)-x_0 =:\mathsf f_{\widehat\mu}(h_*,x_0).\tag{36}\] On the output side, 32 –33 give \[r^*=w+b_*-\widehat\kappa u^*, \qquad u^*\in\partial L(r^*).\] Equivalently, \[\label{eq:g95resolvent95gen} r^*=\mathop{\mathrm{prox}}_{\widehat\kappa L}(w+b_*).\tag{37}\] Combining 32 and 37 gives \[\label{eq:g95prox95gen} u^* = \frac{(w+b_*)-\mathop{\mathrm{prox}}_{\widehat\kappa L}(w+b_*)}{\widehat\kappa} =:\mathsf g_{\widehat\kappa}(b_*,w).\tag{38}\] Finally, combining 36 and 38 with 34 –35 gives the finite abstract AMP fixed point \[\begin{align} h_*&=A^\top u^*+\widehat\mu e^*, & e^*&=\mathsf f_{\widehat\mu}(h_*,x_0),\\ b_*&=-Ae^*+\widehat\kappa u^*, & u^*&=\mathsf g_{\widehat\kappa}(b_*,w). \end{align}\]

We now relate this finite abstract AMP fixed point to the GAMP variables. Set \(x^*=x_0+e^*\) and define \[r_{\rm in}^* :=x^*+\frac{1}{\widehat\mu}A^\top u^*.\] Then 34 gives \[r_{\rm in}^* =x_0+\frac{1}{\widehat\mu}h_*,\] and 36 becomes \[x^* = \mathop{\mathrm{prox}}_{\frac{\lambda}{\widehat\mu}F}(r_{\rm in}^*),\] Similarly, defining \(a^*=w+b_*\), 35 gives \[a^*=y-Ax^*+\widehat\kappa u^*,\] and 38 gives \[u^* = \frac{a^*-\mathop{\mathrm{prox}}_{\widehat\kappa L}(a^*)}{\widehat\kappa} =g_{\rm out}(a^*,\widehat\kappa),\] which proves ?? –?? . Finally, writing \(\widehat\mu_r:=1/\widehat\mu\) recovers ?? –?? . The Onsager-coefficient limits in ?? –?? are verified in the Onsager-coefficients subsection below.

6.4 Proof of Theorem 6↩︎

Use \(x^*=x_0+e^*\), \(\widehat\mu_r=1/\widehat\mu\), \(h_*=\widehat\beta h\), and \(b_*=\widehat\sigma g\). Then ?? , 34 , ?? , and 35 give \[\begin{align} r_{\rm in}^* &=x^*+\widehat\mu_r A^\top u^* =x_0+e^*+\widehat\mu_r(h_*-\widehat\mu e^*)\\ &=x_0+\widehat\mu_r\widehat\beta h,\\ a^* &=y-Ax^*+\widehat\kappa u^* =w-Ae^*+\widehat\kappa u^*\\ &=w+\widehat\sigma g. \end{align}\] Thus ?? –?? hold with \(\widehat\tau:=\widehat\mu_r\widehat\beta\). The stated convergence relations follow from the scalar AO limits in 47 .

6.5 Onsager Coefficients↩︎

It remains to verify the scalar limits in ?? –?? . Since \(b_*=\widehat\sigma g\) and \(u^*=\mathsf g_{\widehat\kappa}(b_*,w)\), \[\widehat\mu =\frac{g^\top u^*}{m\widehat\sigma} =\frac{b_*^\top u^*}{m\widehat\sigma^2} =\frac{1}{\widehat\sigma^2}\frac{1}{m} \sum_{i=1}^m (b_*)_i \mathsf g_{\widehat\kappa}((b_*)_i,w_i).\] The standard empirical Stein concentration for this separable Gaussian channel gives \[\label{eq:stein95mu} \widehat\mu -\bigl\langle \partial_b\mathsf g_{\widehat\kappa}(b_*,w) \bigr\rangle \xrightarrow{p}0 .\tag{39}\] Because \(a^*=w+b_*\) and \(\mathsf g_{\widehat\kappa}(b_*,w)=g_{\rm out}(a^*,\widehat\kappa)\), \[\partial_b\mathsf g_{\widehat\kappa}(b_*,w) = \partial_a g_{\rm out}(a^*,\widehat\kappa).\] Together with \(\widehat\mu_r=1/\widehat\mu\), this is ?? . Similarly, since \(h_*=\widehat\beta h\) and \(e^*=\mathsf f_{\widehat\mu}(h_*,x_0)\), \[\widehat\kappa =\frac{h^\top e^*}{m\widehat\beta} =\frac{h_*^\top e^*}{m\widehat\beta^2} =\frac{1}{\delta\widehat\beta^2}\frac{1}{n} \sum_{j=1}^n (h_*)_j \mathsf f_{\widehat\mu}((h_*)_j,x_{0,j}).\] The same argument gives \[\label{eq:stein95kappa} \widehat\kappa -\frac{1}{\delta} \bigl\langle \partial_{h_*}\mathsf f_{\widehat\mu}(h_*,x_0) \bigr\rangle \xrightarrow{p}0 .\tag{40}\] Since \[\mathsf f_{\widehat\mu}(h_*,x_0) =g_{\rm in}(x_0+\widehat\mu_r h_*,\widehat\mu_r)-x_0,\] \[\partial_{h_*}\mathsf f_{\widehat\mu}(h_*,x_0) = \widehat\mu_r\, \partial_{r_{\rm in}}g_{\rm in}(r_{\rm in}^*,\widehat\mu_r).\] Thus 40 is the same as ?? .

6.6 Scalar AO Reduction↩︎

This scalarization is standard in the CGMT analysis of regularized \(M\)-estimators [4]. We include the steps for completeness. As in [4], one may first impose large compact constraints on the normalized primal and dual variables. For sufficiently large bounds, these constraints are inactive with probability tending to one. Write \[F(x_0+e)=\max_{s\in\mathbb{R}^n} \{s^\top(x_0+e)-F^*(s)\}.\] Using the sign symmetry of the Gaussian vectors \(g,h\), the AO can be written in the form \[\label{eq:ao95fenchel95complete} \begin{align} \min_{e,v}\max_{u,s}\Bigl\{ &\frac{\left\lVert e \right\rVert_2}{\sqrt m}g^\top u -\frac{\left\lVert u \right\rVert_2}{\sqrt m}h^\top e\\ &+u^\top w-u^\top v+L(v)\\ &+\lambda s^\top(x_0+e)-\lambda F^*(s) \Bigr\}. \end{align}\tag{41}\]

Fixing the norm of the dual variable and optimizing over its direction gives the first reduction. With \(\left\lVert u \right\rVert_2=\beta\sqrt m\), \[a_e:=\frac{\left\lVert e \right\rVert_2}{\sqrt m}g+w-v, \qquad \max_{\left\lVert u \right\rVert_2=\beta\sqrt m}u^\top a_e =\beta\sqrt m\left\lVert a_e \right\rVert_2 .\] Thus the AO is \[\label{eq:after95u95direction95complete} \begin{align} \min_{e,v}\max_{\beta\ge0,s}\Bigl\{ &\beta\sqrt m \left\| \frac{\left\lVert e \right\rVert_2}{\sqrt m}g+w-v \right\|_2\\ &-\beta h^\top e+L(v) +\lambda s^\top(x_0+e)-\lambda F^*(s) \Bigr\}. \end{align}\tag{42}\] Following [4], we analyze the reordered version of 42 , obtained by swapping the minimization over \((e,v)\) and the maximization over \((\beta,s)\). This reordered problem yields the same high-dimensional CGMT characterization. Fix \(\sigma:=\left\lVert e \right\rVert_2/\sqrt m\). Optimizing over the direction of \(e\) gives \[\min_{\left\lVert e \right\rVert_2=\sigma\sqrt m} (\lambda s-\beta h)^\top e = -\sigma\sqrt{\delta n}\,\left\lVert \beta h-\lambda s \right\rVert_2 .\] Consequently, after normalizing by \(n\) and using the sign symmetry of \(g\), the reduced AO has the form \[\label{eq:after95e95direction95complete} \begin{align} \max_{\beta\ge0,s}\min_{\sigma\ge0,v}\Bigl\{ &\delta\beta\frac{1}{\sqrt m} \left\lVert \sigma g+w-v \right\rVert_2 +\frac{1}{n} L(v)\\ &-\sigma\sqrt{\delta}\frac{1}{\sqrt n} \left\lVert \beta h-\lambda s \right\rVert_2 +\frac{\lambda}{n}s^\top x_0-\frac{\lambda}{n}F^*(s) \Bigr\}. \end{align}\tag{43}\]

Using \[\left\lVert t \right\rVert_2=\inf_{\tau>0} \left\{\frac{\tau}{2}+\frac{\left\lVert t \right\rVert_2^2}{2\tau}\right\},\] The objective can be written as, \[\label{eq:two95sqrt95complete} \begin{align} R_n :=&\frac{\delta\beta\tau_g}{2} +\frac{1}{n} E_L -\frac{\sigma\sqrt\delta\,\tau_h}{2} -\frac{1}{n} E_F,\\ E_L :=&\min_v \left[ \frac{\beta}{2\tau_g} \left\lVert \sigma g+w-v \right\rVert_2^2 +L(v) \right],\\ E_F :=&\min_s \left[ \frac{\sigma\sqrt\delta}{2\tau_h} \left\lVert \beta h-\lambda s \right\rVert_2^2 -\lambda s^\top x_0+\lambda F^*(s) \right], \end{align}\tag{44}\] with optimization \(\inf_{\sigma,\tau_g}\sup_{\beta,\tau_h}R_n\). The loss-side minimizer is \[v_L := \mathop{\mathrm{prox}}_{\frac{\tau_g}{\beta}L} \left(\sigma g+w\right),\] and therefore \[\label{eq:loss95moreau95complete} E_L= \frac{\beta}{2\tau_g} \left\lVert \sigma g+w-v_L \right\rVert_2^2 +L(v_L).\tag{45}\] For the second minimization, set \[\begin{align} \gamma_F&:=\frac{\sigma\sqrt\delta\,\lambda}{\tau_h}, & q_F&:=x_0+\frac{\sigma\sqrt\delta\,\beta}{\tau_h}h,\\ x_F&:=\mathop{\mathrm{prox}}_{\gamma_F F}(q_F). \end{align}\] Completing the square and using the Moreau identity gives \[\label{eq:regularizer95moreau95complete} E_F= \frac{\sigma\sqrt\delta\,\beta^2}{2\tau_h}\left\lVert h \right\rVert_2^2 -\lambda\left[ \frac{1}{2\gamma_F}\left\lVert q_F-x_F \right\rVert_2^2+F(x_F) \right],\tag{46}\] which is the identity used in [4]. Let \[\begin{align} P_L(c,\tau)&:=\mathop{\mathrm{prox}}_{\tau L}(cg+w),\\ P_F(c,\tau)&:=\mathop{\mathrm{prox}}_{\tau F}(x_0+c h). \end{align}\] \[\begin{align} \mathcal{L}(c,\tau) &:=\lim_{m\to\infty}\frac{1}{m} \Biggl[ \frac{1}{2\tau}\left\lVert cg+w-P_L(c,\tau) \right\rVert_2^2\\ &\qquad\qquad +L\!\left(P_L(c,\tau)\right) \Biggr],\\ \mathcal{F}(c,\tau) &:=\lim_{n\to\infty}\frac{1}{n} \Biggl[ \frac{1}{2\tau}\left\lVert x_0+c h-P_F(c,\tau) \right\rVert_2^2\\ &\qquad\qquad +F\!\left(P_F(c,\tau)\right) \Biggr]. \end{align}\] The scalar AO is \[\label{eq:gen95scalar95ao95final} \inf_{\sigma\ge0,\tau_g>0} \sup_{\beta\ge0,\tau_h>0} D_{\rm gen}(\sigma,\tau_g,\beta,\tau_h),\tag{47}\] with \[\label{eq:gen95scalar95D95final} \begin{align} D_{\rm gen} :=&\frac{\delta\beta\tau_g}{2} +\delta\,\mathcal{L}\left(\sigma,\frac{\tau_g}{\beta}\right) -\frac{\sigma\sqrt\delta\,\tau_h}{2} -\frac{\sigma\sqrt\delta\,\beta^2}{2\tau_h}\\ &+\lambda\, \mathcal{F}\left(\frac{\sigma\sqrt\delta\,\beta}{\tau_h}, \frac{\sigma\sqrt\delta\,\lambda}{\tau_h}\right). \end{align}\tag{48}\] This is the scalar optimization in [4]. The relation to the non-asymptotic scalars used above is \[\widehat\sigma=\frac{\left\lVert e^* \right\rVert_2}{\sqrt m} \xrightarrow{p}\sigma_*, \qquad \widehat\beta=\frac{\left\lVert u^* \right\rVert_2}{\sqrt m} \xrightarrow{p}\beta_*.\] The GAMP scalar limits induced by the saddle are \[\kappa_*:=\frac{\tau_{g,*}}{\beta_*}, \qquad \mu_{r,*}:=\frac{\sqrt\delta\,\sigma_*}{\tau_{h,*}}.\] The coefficients satisfy \[\widehat\kappa\xrightarrow{p}\kappa_*, \qquad \widehat\mu_r\xrightarrow{p}\mu_{r,*},\] and hence \[\widehat\tau:=\widehat\mu_r\widehat\beta \xrightarrow{p} \frac{\sqrt\delta\,\sigma_*\beta_*}{\tau_{h,*}}.\]

References↩︎

---

1. Vikrant Malik and Babak Hassibi are with the Department of Electrical Engineering, California Institute of Technology (Caltech), Pasadena, CA, USA (e-mail: vmalik@caltech.edu; hassibi@caltech.edu).↩︎

2. We write the negative sign on the \(h\)-term. Since all Gaussian variables are symmetric, this is distributionally equivalent to 1 –2 .↩︎

3. As in 12 , we write the negative sign on the \(h\)-term. Since all Gaussian variables are symmetric, this is distributionally equivalent to 1 –2 .↩︎