# Random-start learned AMP

- ID: 1681
- Canonical URL: https://synthcore.org/idea/1681/random-start-learned-amp
- API JSON: https://synthcore.org/api/idea/1681.json
- API Markdown: https://synthcore.org/api/idea/1681.md
- Verification status: unverified
- Source: [arXiv:2608.01654](https://arxiv.org/abs/2608.01654)
- Category: architecture
- Solves: accuracy, stability, speedup
- ML areas: optimizer, training-dynamics, world-model
- Math tags: stochastic-processes, probability, random-matrix, dynamical-systems
- Ratings: usefulness 6/10; difficulty 5/10; novelty 4/10

## Idea description

Construct an unrolled phase-retrieval network that begins with an isotropic Gaussian estimate rather than a spectral initializer. Retain the AMP residual correction and Onsager subtraction, but learn the scalar measurement denoisers and step sizes; use several random starts and select the iterate with the lowest measurement residual.

## Mathematical statement

The paper decomposes the AMP trajectory into a signal component plus Gaussian components: \(\begin{pmatrix}\eta^{t+1}\\\theta^{t+1}\end{pmatrix}=\begin{pmatrix}\gamma_{t,-1}\eta^{\star}\\\rho_{t+1}\theta^{\star}\end{pmatrix}+\begin{pmatrix}\sum_{\ell=0}^{t}\gamma_{t,\ell}g^{\ell}\\\sum_{\ell=0}^{t}\lambda_{t,\ell}s^{\ell}\end{pmatrix}\). Here \(\theta^{\star}\) is the unknown signal, \(\theta^{t+1}\) is the signal-side iterate, \(\eta^{\star}\) and \(\eta^{t+1}\) are auxiliary measurement-side variables, \(\rho_{t+1}\), \(\gamma_{t,\ell}\), and \(\lambda_{t,\ell}\) are scalar coefficients, \(g^{\ell}\) are Gaussian vectors, and \(s^{\ell}\) are measurement-side residual vectors. The important property is that the signal coefficient can grow from a random initialization whose overlap is only \(O(d^{-1/2})\), while the remaining trajectory is approximately Gaussian. Implement the AMP-style correction as \(r^t=\psi_t(y,A x^t)-b_t r^{t-1}\), where \(A\) is the sensing matrix, \(y_i=(a_i^{\top}\theta^{\star})^2\), \(\psi_t\) is a learned scalar denoiser, and \(b_t\) is the average denoiser derivative.

## Key formulas

- $$\begin{pmatrix}\eta^{t+1}\\\theta^{t+1}\end{pmatrix}=\begin{pmatrix}\gamma_{t,-1}\eta^{\star}\\\rho_{t+1}\theta^{\star}\end{pmatrix}+\begin{pmatrix}\displaystyle\sum_{\ell=0}^{t}\gamma_{t,\ell}g^{\ell}\\[4pt]\displaystyle\sum_{\ell=0}^{t}\lambda_{t,\ell}s^{\ell}\end{pmatrix}$$
- $$r^t=\psi_{\phi_t}(y,A x^t)-b_t r^{t-1},\qquad x^{t+1}=x^t+\alpha_t A^{\top}r^t$$
- $$b_t=\frac{1}{n}\sum_{i=1}^{n}\frac{\partial}{\partial z_i}\psi_{\phi_t}(y_i,z_i)\bigg|_{z=Ax^t},\qquad x^0\sim\mathcal{N}(0,\sigma_0^2 I_d)$$
- $$t^{\star}=\arg\min_{0\leq t\leq T}\frac{1}{n}\left\|y-(A x^t)^{\odot 2}\right\|_2^2$$

## Implementation notes

(1) Integration point: replace the iterative core of a phase-retrieval solver with 10 to 50 AMP layers. Let \(A\in\mathbb{R}^{n\times d}\), \(y\in\mathbb{R}^n\), and \(x^t\in\mathbb{R}^d\). Avoid eigendecomposition and initialize \(x^0\sim\mathcal{N}(0,I_d/d)\). Each layer uses a shared or lightly untied two-layer MLP applied independently to \((y_i,(Ax^t)_i)\), followed by Onsager correction and back-projection. Constrain \(\alpha_t\) to be positive with a softplus parameterization. (2) Pseudocode: set \(r^{-1}=0\), draw \(x^0\), and for \(t=0,\ldots,T-1\) compute \(z=Ax^t\), \(u_i=\psi_{\phi_t}(y_i,z_i)\), \(b_t=n^{-1}\sum_i \partial\psi_{\phi_t}(y_i,z_i)/\partial z_i\), \(r^t=u-b_t r^{t-1}\), and \(x^{t+1}=x^t+\alpha_t A^{\top}r^t\). Optionally normalize \(x^{t+1}\) only when its norm becomes unstable. Return the iterate with minimum measurement residual. (3) Compute the Onsager coefficient from automatic differentiation; learn \(\phi_t\) and \(\alpha_t\) end-to-end. The mathematical prediction is the signal-plus-Gaussian trajectory structure and the need for a growing horizon; estimate signal emergence empirically using reconstruction error on synthetic data, iterate norms, residuals, and cosine similarity between independent runs. (4) First experiment: generate Gaussian sensing matrices with \(d\in\{256,512\}\) and measurement ratios \(\delta=n/d\in\{0.6,0.8,1.2,2.0\}\). Compare random-start learned AMP against spectral-initialized learned AMP, vanilla gradient descent, and the same unrolled network with the Onsager term removed. Train on noiseless quadratic measurements and evaluate relative error modulo global sign, measurement residual, number of layers, and wall-clock time. A positive result is random-start AMP reaching the spectral baseline for \(\delta>0.5\), with stable loss reduction over more layers and no eigensolve overhead.

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.