In high-dimensional linear inverse problems, we aim to recover a hidden sparse vector $x$ from a set of noisy linear measurements $y = Ax + w$. Among the various algorithmic frameworks developed to solve this problem, Approximate Message Passing (AMP) stands out. It is celebrated for its exceptional speed—scaling linearly with the problem size—and its exact asymptotic predictability via a scalar recursion known as State Evolution.
Yet, standard AMP possesses a notorious Achilles' heel: it is exceptionally brittle. As highlighted by Andre Manoel et al. in Swept Approximate Message Passing for Sparse Estimation and Jeremy P. Vila et al. in Expectation-Maximization Gaussian-Mixture Approximate Message Passing, the algorithm's optimality relies entirely on the assumption that the measurement matrix $A$ consists of independent and identically distributed (i.i.d.) Gaussian entries.
When confronted with real-world physical systems—such as Cartesian sampling masks in MRI (Subrata Sarkar et al. in MRI Image Recovery using Damped Denoising Vector AMP), structured communication preambles (Yandong Shi et al. in Algorithm Unrolling for Massive Access via Deep Neural Network with Theoretical Guarantee), or highly correlated data matrices—standard AMP frequently suffers from catastrophic divergence.
Understanding why this instability occurs, and how modern variants resolve it, requires looking closely at how error propagation is managed during message passing.
The Breakdown of Onsager Cancellation
To build intuition for why standard AMP fails on structured matrices, consider what happens in standard iterative thresholding algorithms. When we compute a residual $y - Ax^t$ at iteration $t$ and project it back via $A^T$, the resulting error becomes highly coupled with the measurement matrix $A$ over subsequent iterations. This coupling creates feedback loops that destroy the statistical independence required for simple denoisers to function optimally.
AMP elegantly solves this problem by introducing a correction term, known as the Onsager correction. As explained by Philip Schniter in A Simple Derivation of AMP and its State Evolution via First-Order Cancellation, the Onsager term acts as a first-order cancellation mechanism. It subtracts the correlated "echo" of past estimations from the current residual. This ensures that the input to the denoiser at each step behaves exactly like the true signal corrupted by clean, white Gaussian noise.
Standard Iterative Step: x^{t+1} = Denoiser( x^t + A^T (y - Ax^t) )
^-- Error becomes coupled with A
AMP Iterative Step: x^{t+1} = Denoiser( x^t + A^T (y - Ax^t) + Onsager_Correction )
^-- Cancels the coupling!
However, this mathematical cancellation relies entirely on the isotropic nature of i.i.d. Gaussian matrices. When the matrix $A$ is ill-conditioned or highly structured, its singular values are no longer uniform. The "echo" of past iterations is no longer a simple scalar multiple of the previous residual; instead, it becomes heavily distorted along the dominant singular vectors of $A$.
Because a standard scalar Onsager term cannot account for this multi-directional distortion, the error cancellation fails. The residual errors compound exponentially across iterations, leading to rapid numerical divergence. As demonstrated by Philip Schniter et al. in On the convergence of approximate message passing with arbitrary matrices, the stability of standard message passing is fundamentally dictated by the peak-to-average ratio of the matrix's squared singular values. When this ratio is high, standard AMP lacks the geometric flexibility to converge.
Vector AMP and Rotation Invariance
To restore stability without sacrificing the linear computational complexity of message passing, researchers shifted their perspective from scalar-level approximations to vector-level approximations. This insight led to the development of Vector Approximate Message Passing (VAMP), introduced by Philip Schniter et al. in Denoising based Vector Approximate Message Passing.
Instead of requiring strictly independent matrix entries, VAMP expands the class of permissible measurement matrices to those that are right-rotationally invariant. A matrix $A$ satisfies this property if its Singular Value Decomposition (SVD), $A = U\Sigma V^T$, features an arbitrary distribution of singular values ($\Sigma$) but a completely random, orthogonal set of right-singular vectors ($V$). This accommodates highly ill-conditioned or correlated matrices.
VAMP achieves robustness by decoupling the estimation process into two alternating, vector-valued estimation steps:
- A Non-Linear Denoising Step: This step enforces the signal prior (such as sparsity or structural constraints) on the current estimate.
- A Linear MMSE Estimation Step: This step explicitly handles the measurement matrix $A$, utilizing its full singular value spectrum $\Sigma$ to perform a vector-valued correction.
+-----------------------------------------------------------------+
| |
| +-------------------+ +-------------------+ |
| | | Est.
+ Error | | |
| | Linear MMSE Step | --------------> | Denoiser Step | |
| | (Handles \Sigma) | | (Handles Prior) | |
| | | <-------------- | | |
| +-------------------+ Vector Onsager +-------------------+ |
| |
+-----------------------------------------------------------------+
By operating in the coordinate space defined by the singular vectors $V$, VAMP replaces the scalar Onsager correction with a vector-valued correction tailored to the exact spectrum of $A$. This ensures that the estimation errors remain perfectly decoupled and independent at every iteration, regardless of how ill-conditioned the matrix is.
The theoretical validity of this approach was established by Alyson K. Fletcher et al. in Rigorous Dynamics and Consistent Estimation in Arbitrarily Conditioned Linear Systems and further extended in Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis. They proved that VAMP’s performance can be rigorously tracked by a vector-valued State Evolution framework, guaranteeing predictable convergence even when utilizing complex, non-separable deep learning models as denoisers.
Alternative Paths to Robustness
While VAMP offers an elegant geometric solution via the SVD, computing the full spectrum of a matrix can be computationally expensive for massive datasets. Consequently, several alternative paradigms have emerged to mitigate matrix sensitivity:
- Adaptive Damping and Mean Removal: For generalized linear models where an SVD is impractical, Jeremy P. Vila proposed Adaptive damping and mean removal for the generalized approximate message passing algorithm. Damping dynamically scales down the step size of message updates to suppress feedback loops, while mean-removal explicitly strips out non-zero matrix offsets that would otherwise introduce systemic bias into the Onsager term.
- Free Probability Theory: Rather than explicitly decoupling the matrix spectrum, the framework introduced by Burak Çakmak et al. in S-AMP for Non-linear Observation Models leverages free probability theory. By utilizing the asymptotic properties of the S-transform, S-AMP bypasses matrix inversions entirely, providing a robust message-passing alternative for generic rotationally invariant ensembles.
- Deep Algorithm Unrolling: A highly pragmatic approach involves "unrolling" the iterations of message-passing algorithms into the layers of a deep neural network. In AMP-Inspired Deep Networks for Sparse Linear Inverse Problems, Mark Borgerding introduced LAMP and LVAMP. These architectures embed the structural form of the Onsager correction directly into the network's layers. By training the network end-to-end on specific measurement ensembles, the model learns to adaptively tune its internal weights to compensate for matrix ill-conditioning, combining the speed of message passing with the empirical robustness of deep learning.