Rotationally Invariant Approximate Message Passing

27 concepts19 papers1 proposal

Approximate Message Passing (AMP) is a powerful iterative framework used to solve high-dimensional linear inverse problems and statistical inference tasks. At its core, AMP relies on a elegant mechanism known as the Onsager correction term. This term mathematically subtracts the correlated feedback ("echoes") that builds up when information passes back and forth between the variables and the measurements.

However, standard AMP has a fragile assumption: its mathematical derivation requires the measurement matrix $\mathbf{A}$ to have independent and identically distributed (i.i.d.) Gaussian entries. In real-world applications—such as wireless communications, medical imaging, or neural network inference—data matrices are highly structured, correlated, or ill-conditioned. When standard AMP is applied to these non-ideal matrices, the Onsager term fails to accurately track the feedback error, causing the algorithm to catastrophically diverge.

To overcome this limitation, a robust paradigm has emerged: Rotationally Invariant Approximate Message Passing. By redesigning message passing to be invariant to unitary transformations, this framework maintains perfect convergence and stability even when dealing with highly ill-conditioned or heavily correlated data structures.

The Intuition: Decoupling Geometry from Spectrum

To understand why standard AMP fails and why rotational invariance fixes it, consider the Singular Value Decomposition (SVD) of a measurement matrix: $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^T$.

The matrix $\mathbf{V}$ represents a rotation in the space of the signal, $\boldsymbol{\Sigma}$ contains the singular values (the spectrum) which scale the data, and $\mathbf{U}$ represents a rotation in the measurement space.

  • Standard AMP's Failure: Standard AMP treats the matrix as an isotropic cloud of i.i.d. points. It assumes a completely flat singular value spectrum. If the matrix is ill-conditioned (meaning some singular values are massive while others are near zero), the error feedback builds up anisotropically along specific geometric directions. Standard AMP's scalar Onsager term cannot account for this direction-dependent stretching, leading to algorithm divergence.
  • The Rotationally Invariant Solution: If an algorithm is designed to be invariant to the right singular vectors $\mathbf{V}$ (meaning its statistical behavior doesn't change when the signal space is rotated), it can decouple the geometric directions of the data from its scaling factors. This allows the algorithm to explicitly adjust its error tracking based on the entire spectrum of singular values $\boldsymbol{\Sigma}$, rather than assuming they are all equal.

As demonstrated by Fletcher et al. in Rigorous Dynamics and Consistent Estimation in Arbitrarily Conditioned Linear Systems and Schniter et al. in Denoising based Vector Approximate Message Passing, frameworks built on this right-rotational invariance can handle extreme ill-conditioning—maintaining stability at condition numbers up to 10,000 where traditional message passing completely collapses.

The Mechanism: Unitary Transformations and Adaptive Scaling

How do these robust algorithms actually implement this invariance? The primary strategy is to apply a unitary transformation to the problem space or to leverage advanced statistical physics tools like free probability theory.

In frameworks like Vector AMP (VAMP), Orthogonal AMP (OAMP), and Unitary AMP (UAMP), the algorithm transforms the original non-i.i.d. problem into a mathematically stable form. Instead of passing scalar variances that assume independent variables, the messages track vector-valued or matrix-valued error states.

For instance, Zhu et al. in A Unitary Transform Based Generalized Approximate Message Passing and Liu et al. in Blind Grant-Free Random Access With Message-Passing-Based Matrix Factorization in mmWave MIMO mMTC show that applying a unitary transform directly to the message-passing framework stabilizes matrix factorization and signal recovery. This prevents divergence when processing generic, non-Gaussian measurement matrices because the unitary transform effectively "whitens" the correlated feedback loop.

Alternatively, Çakmak et al. in S-AMP for Non-linear Observation Models utilized the S-transform from free probability theory. This mathematical tool allows the algorithm to compute the exact asymptotic behavior of the sum and product of highly correlated, rotationally invariant random matrices, bypassing computationally expensive matrix inversions entirely while ensuring rigorous algorithmic stability.

Rigorous Predictability via State Evolution

One of the most celebrated features of standard AMP is State Evolution—a deterministic scalar framework that precisely predicts the algorithm's mean squared error (MSE) at every single iteration in the high-dimensional limit. A major breakthrough in this research direction was proving that this exact predictability is preserved under rotational invariance.

In a foundational single-author paper, Fletcher established in Plug-in Estimation in High-Dimensional Linear Inverse Problems: A Rigorous Analysis that VAMP's performance is exactly predictable via state evolution, even when paired with complex, non-separable "plug-in" denoisers like deep neural networks. This theoretical guarantee means that engineers do not have to treat robust message passing as a black box; its convergence path and final accuracy can be mathematically calculated beforehand.

Similarly, Bu et al. in Algorithmic Analysis and Statistical Estimation of SLOPE via Approximate Message Passing extended this exact statistical characterization to advanced high-dimensional regression estimators like SLOPE, confirming that the theoretical benefits of advanced estimators remain robust under rotationally invariant designs.

Applications and Extensions

By freeing message passing from the restrictive assumption of i.i.d. Gaussian matrices, researchers have successfully deployed these algorithms across a wide range of complex domains:

Key Foundational Work

S-AMP for Non-linear Observation Models (2015) — contributed 2 concept elements to this direction.
Denoising based Vector Approximate Message Passing (2016) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_robust_message_passing_50e4ffff,
  title = {robust message passing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-message-passing/rdr_50e4ffff18994e59a9f8fcfd3634ee7f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_robust_message_passing_50e4ffff_v1,
  title = {robust message passing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-message-passing/rdr_50e4ffff18994e59a9f8fcfd3634ee7f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake