Ferkans — Interactive Telecom Tutor

The OAMP Idea — Orthogonalize, Then Denoise

AMP fails for structured matrices because the residual is correlated with the estimate. The fix is conceptually simple: replace the scalar Onsager correction with a linear operator that explicitly orthogonalizes the error.

OAMP (Orthogonal AMP) achieves this by alternating two steps:

LMMSE step: A linear estimator that uses the full SVD of $\mathbf{A}$ to produce an estimate whose error is uncorrelated with the input.
Denoiser step: A (possibly nonlinear) denoiser that exploits the prior on $\mathbf{c}$ .

The orthogonality between the errors of the two steps is the key invariant that enables state evolution for arbitrary right-rotationally-invariant matrices — a much larger class than i.i.d. Gaussian.

Definition:
Right-Rotationally-Invariant Matrices

A random matrix $\mathbf{A} \in \mathbb{C}^{M \times N}$ is right-rotationally invariant if its distribution is unchanged under right multiplication by any unitary matrix:

$\mathbf{A} \stackrel{d}{=} \mathbf{A}\mathbf{U} \qquad \text{for all unitary } \mathbf{U}.$

Equivalently, the SVD $\mathbf{A} = \mathbf{U}_L \boldsymbol{\Sigma} \mathbf{V}^H$ has $\mathbf{V}$ uniformly distributed on the unitary group (Haar-distributed), independent of $\boldsymbol{\Sigma}$ .

I.i.d. Gaussian matrices are right-rotationally invariant, but the class is much larger. For instance, any matrix of the form $\mathbf{A} = \mathbf{B}\mathbf{V}$ with $\mathbf{V}$ Haar and $\mathbf{B}$ deterministic is right-rotationally invariant — this includes matrices with arbitrary prescribed singular values.

Historical Note: The Parallel Development of OAMP and VAMP

2017–2019

OAMP and VAMP were developed independently and nearly simultaneously. Ma and Ping (2017) derived OAMP by imposing a divergence-free condition on the linear estimator — they showed that the LMMSE estimator with a specific bias subtraction produces orthogonal errors. Rangan, Schniter, and Fletcher (2019) derived VAMP from the expectation consistency framework, arriving at an equivalent algorithm with a more symmetric structure. The two formulations are now understood to be equivalent for right-rotationally invariant matrices; we use "OAMP" throughout this chapter but note the correspondence.

,

Definition:
OAMP Algorithm

Let $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^H$ be the (compact or full) SVD. OAMP alternates:

LMMSE step (linear estimator):

$\hat{\mathbf{c}}_1^t = \mathbf{W}_t\,\mathbf{y} + (\mathbf{I} - \mathbf{W}_t\mathbf{A})\, \hat{\mathbf{c}}_2^{t-1},$

where $\mathbf{W}_t = v_2^{t-1}\,\mathbf{A}^{H} (\sigma^2\mathbf{I} + v_2^{t-1}\, \mathbf{A}\mathbf{A}^{H})^{-1}$ is the LMMSE filter with prior variance $v_2^{t-1}$ (the MSE from the previous denoiser step).

MSE of LMMSE step:

$v_1^t = \frac{1}{N}\text{tr}\bigl[ v_2^{t-1}\mathbf{I} - v_2^{t-1}\,\mathbf{A}^{H} (\sigma^2\mathbf{I} + v_2^{t-1}\mathbf{A}\mathbf{A}^{H})^{-1} \mathbf{A}\,v_2^{t-1}\bigr].$

Denoiser step (nonlinear estimator):

$\hat{\mathbf{c}}_2^t = \eta_t\!\bigl( \hat{\mathbf{c}}_1^t\bigr),$

$v_2^t = \frac{1}{N}\|\hat{\mathbf{c}}_2^t - \hat{\mathbf{c}}_1^t\|^2 \;\Big/\;\bigl(1 - \text{div}(\eta_t)\bigr)^2,$

where $\text{div}(\eta_t) = \frac{1}{N}\sum_{i} \frac{\partial [\eta_t(\hat{\mathbf{c}}_1^t)]_i} {\partial [\hat{\mathbf{c}}_1^t]_i}$ .

,

OAMP for Linear Inverse Problems

Complexity: Dominated by the SVD (computed once):

O(\min(M,N) \cdot MN)

. Per iteration:

O(MN)

for the LMMSE matrix-vector product.

Input:

\mathbf{y}

,

\mathbf{A}

,

\sigma^2

,

denoiser

\eta_t

, max iterations

T

Preprocessing: Compute SVD

\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^H

;

store singular values

\{s_i\}

Initialize:

\hat{\mathbf{c}}_2^0 = \mathbf{0}

,

v_2^0 = \mathbb{E}[|\mathbf{c}|^2]

(prior variance)

for

t = 1, 2, \ldots, T

:

1. LMMSE step:

\mathbf{W}_t = v_2^{t-1}\mathbf{A}^{H} (\sigma^2\mathbf{I} + v_2^{t-1}\mathbf{A}\mathbf{A}^{H})^{-1}

\hat{\mathbf{c}}_1^t = \mathbf{W}_t\mathbf{y} + (\mathbf{I} - \mathbf{W}_t\mathbf{A}) \hat{\mathbf{c}}_2^{t-1}

v_1^t = \frac{1}{N}\sum_{i=1}^{\min(M,N)} \frac{\sigma^2\,v_2^{t-1}} {\sigma^2 + v_2^{t-1}\,s_i^2} + \frac{N - M}{N}\,v_2^{t-1} \cdot \mathbb{1}_{N > M}

2. Denoiser step:

\hat{\mathbf{c}}_2^t = \eta_t(\hat{\mathbf{c}}_1^t)

d_t = \text{div}(\eta_t)

(analytical or via Hutchinson estimator)

v_2^t = v_1^t \cdot d_t / (1 - d_t)

3. Convergence check:

If

|\hat{\mathbf{c}}_2^t - \hat{\mathbf{c}}_2^{t-1}| / |\hat{\mathbf{c}}_2^t| < \varepsilon

, stop.

Output:

\hat{\mathbf{c}}_2^T

The SVD is computed once as preprocessing. All subsequent LMMSE steps use the precomputed singular values and vectors to evaluate the Woodbury-form inverse efficiently.

,

Theorem: Orthogonality of OAMP Error Vectors

Let $\mathbf{A}$ be right-rotationally invariant with singular values $\{s_i\}$ . Define the errors $\mathbf{e}_1^t = \hat{\mathbf{c}}_1^t - \mathbf{c}$ and $\mathbf{e}_2^t = \hat{\mathbf{c}}_2^t - \mathbf{c}$ . Then in the large-system limit ( $M, N \to \infty$ with $M/N \to \delta$ ):

$\frac{1}{N}\mathbf{e}_1^{t\,H}\,\mathbf{e}_2^{t-1} \xrightarrow{\text{a.s.}} 0.$

Moreover, the LMMSE output $\hat{\mathbf{c}}_1^t$ satisfies

$\hat{\mathbf{c}}_1^t \stackrel{d}{\approx} \mathbf{c} + \sqrt{v_1^t}\,\mathbf{z}, \qquad \mathbf{z} \sim \mathcal{CN}(\mathbf{0}, \mathbf{I}),$

so the denoiser at each iteration faces a scalar AWGN channel with known noise variance $v_1^t$ .

The LMMSE step is designed so that its output error is orthogonal to the input (the denoiser output from the previous iteration). This is the direct analogue of the Onsager decorrelation in AMP, but achieved through a matrix operation (the LMMSE filter) rather than a scalar correction. Because the orthogonalization uses the full SVD of $\mathbf{A}$ , it works for any singular value distribution — not just the Marchenko-Pastur distribution of i.i.d. Gaussian matrices.

Proof

Right-rotational invariance implies Gaussianity

When $\mathbf{A} = \mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^H$ with $\mathbf{V}$ Haar-distributed, the projection $\mathbf{V}^H\mathbf{c}$ has i.i.d. entries (by the rotational symmetry of the Gaussian distribution, or by the universality results of Bayati-Montanari). In this rotated basis, the problem decouples into scalar channels.

LMMSE produces uncorrelated output

The LMMSE estimator is the linear estimator that minimizes MSE. By the orthogonality principle of LMMSE estimation, the estimation error $\mathbf{e}_1^t$ is orthogonal to the observation. The key insight is that $\hat{\mathbf{c}}_2^{t-1}$ acts as a pseudo-observation, and the LMMSE construction ensures $\mathbf{e}_1^t \perp \mathbf{e}_2^{t-1}$ .

Scalar channel equivalence

The Gaussianity of the rotated signal and the LMMSE structure together imply that each component of $\hat{\mathbf{c}}_1^t$ is approximately $c_i + \sqrt{v_1^t}\,z_i$ with $z_i \sim \mathcal{CN}(0, 1)$ — a scalar AWGN channel. This enables the denoiser to be designed for a known noise level. $\blacksquare$

,

Theorem: State Evolution for OAMP

For right-rotationally invariant $\mathbf{A}$ with empirical singular value distribution converging to a deterministic limit, the MSE of OAMP is tracked by the two-step state evolution:

$v_1^t = \Bigl(\frac{1}{N}\sum_{i=1}^{M} \frac{s_i^2}{\sigma^2 + v_2^{t-1}\,s_i^2}\Bigr)^{-1} - v_2^{t-1} + \frac{N - M}{N}\,v_2^{t-1},$

$v_2^t = \text{mmse}(\eta_t, v_1^t),$

where $\text{mmse}(\eta_t, v_1^t) = \mathbb{E}[|\eta_t(C_0 + \sqrt{v_1^t}\,Z) - C_0|^2]$ is the MSE of the denoiser on a scalar AWGN channel with noise variance $v_1^t$ .

State evolution for OAMP involves two scalar quantities ( $v_1^t$ for the LMMSE step and $v_2^t$ for the denoiser step) rather than one. The first equation depends on the full singular value distribution of $\mathbf{A}$ (not just $\delta = M/N$ as in AMP). This is why OAMP can handle structured matrices.

Proof

From OAMP orthogonality to scalar recursion

The orthogonality theorem (TOrthogonality of OAMP Error Vectors) ensures that the denoiser input is approximately $\mathbf{c} + \sqrt{v_1^t}\,\mathbf{z}$ . Therefore the denoiser's MSE is exactly the MMSE of the scalar denoising problem: $v_2^t = \text{mmse}(\eta_t, v_1^t)$ .

LMMSE MSE from the singular values

The LMMSE estimator with prior variance $v_2^{t-1}$ and noise variance $\sigma^2$ has MSE given by the well-known formula:

$v_1^t = \frac{1}{N}\text{tr}\bigl[ (v_2^{t-1})^{-1}\mathbf{I} + (\sigma^2)^{-1}\mathbf{A}^{H}\mathbf{A}\bigr]^{-1}.$

Substituting the SVD and using the singular values directly gives the stated formula. $\blacksquare$

,

OAMP State Evolution vs Simulation

Compare the state-evolution prediction (dashed) with the empirical NMSE of OAMP (solid) for different matrix types and problem sizes. State evolution becomes exact as $N$ grows.

Parameters

Problem size

N

500

\delta = M/N

0.4

Sparsity

\rho

0.1

SNR (dB)25

Denoiser

AMP vs OAMP/VAMP

Property	AMP	OAMP/VAMP
Matrix requirement	I.i.d. Gaussian	Right-rotationally invariant
Decorrelation mechanism	Scalar Onsager correction	LMMSE orthogonalization (matrix-valued)
State evolution	One scalar: $\tau_{t+1} = f(\tau_t)$	Two scalars: $v_1^t, v_2^t$
SE depends on	$\delta = M/N$ only	Full singular value distribution of $\mathbf{A}$
Preprocessing	None	SVD of $\mathbf{A}$ (one-time)
Per-iteration cost	$O(MN)$	$O(MN)$
Denoiser requirement	Lipschitz, scalar divergence	Same — plus divergence estimation
Bayes-optimal?	Yes (for i.i.d. $\mathbf{A}$ )	Yes (for RRI $\mathbf{A}$ )
RF imaging matrices	Diverges	Converges

Example: OAMP on a 2D RF Imaging Problem

Consider a 2D RF imaging scene with $N_1 = N_2 = 32$ (so $N = 1024$ voxels), observed by $M_1 = M_2 = 20$ Tx-Rx pairs and frequencies ( $M = 400$ measurements). The sensing matrix is $\mathbf{A} = \mathbf{A}_{1} \otimes \mathbf{A}_{2}$ with partial DFT factors. The reflectivity is Bernoulli-Gaussian with $\rho = 0.08$ and $\text{SNR} = 30\,\text{dB}$ .

Run OAMP with BG-MMSE denoiser and compare the reconstruction with the backpropagation image $\hat{\mathbf{c}}^{\text{BP}} = \mathbf{A}^{H}\mathbf{D}^{-1}\mathbf{y}$ .

Solution

Backpropagation baseline

The backpropagation image has NMSE $= -5.2\,\text{dB}$ with significant sidelobes, as expected from the limited aperture and non-uniform k-space coverage.

OAMP reconstruction

OAMP converges in 15 iterations to NMSE $= -22.8\,\text{dB}$ , correctly identifying all scatterers and suppressing sidelobes. The state evolution prediction is NMSE $= -23.1\,\text{dB}$ , confirming the accuracy of the SE framework.

State evolution tracking

The SE prediction tracks the empirical NMSE within 0.3 dB at every iteration, demonstrating that the right-rotational invariance assumption is well-satisfied for the partial DFT Kronecker matrix.

Why This Matters: OAMP in ISAC Systems

In integrated sensing and communications (ISAC) systems, the base station uses the same OFDM waveform for both data transmission and scene reconstruction. The sensing matrix $\mathbf{A}$ inherits the Kronecker structure from the array geometry and OFDM subcarrier spacing. OAMP is the natural reconstruction algorithm because:

The Kronecker structure makes AMP inapplicable.
The LMMSE step exploits the known array/frequency structure.
State evolution enables offline optimization of the denoiser and system parameters.

Chapter 32 applies OAMP to a full ISAC scenario with simultaneous communication and imaging.

See full treatment in Chapter 32

Quick Check

Which of the following matrices is right-rotationally invariant?

$\mathbf{A}$ with i.i.d. $\mathcal{CN}(0, 1/M)$ entries

A partial DFT matrix (random rows of the DFT)

$\mathbf{B}\mathbf{V}$ where $\mathbf{B}$ is deterministic and $\mathbf{V}$ is Haar-distributed

Correction:

\mathbf{A}

with i.i.d.

\mathcal{CN}(0, 1/M)

entries,

\mathbf{B}\mathbf{V}

where

\mathbf{B}

is deterministic and

\mathbf{V}

is Haar-distributed

An i.i.d. Gaussian matrix has Haar-distributed right singular vectors and is right-rotationally invariant.

OAMP (Orthogonal Approximate Message Passing)

An iterative algorithm for linear inverse problems that alternates an LMMSE step (linear, exploiting the measurement matrix) with a denoiser step (nonlinear, exploiting the signal prior). The LMMSE step orthogonalizes the estimation errors, enabling state evolution for right-rotationally invariant matrices.

VAMP (Vector Approximate Message Passing)

An equivalent formulation of OAMP derived from the expectation consistency framework (Rangan, Schniter, Fletcher, 2019). VAMP uses a symmetric two-denoiser structure and is provably Bayes-optimal for right-rotationally invariant matrices.

Denoiser divergence

The normalized trace of the Jacobian of the denoiser: $\text{div}(\eta) = \frac{1}{N}\sum_{i=1}^N \frac{\partial \eta_i(\mathbf{r})}{\partial r_i}$ . Required for computing the MSE update in OAMP. Can be estimated via the Hutchinson trace estimator for black-box denoisers.

Related: OAMP Algorithm

OAMP/VAMP for the RF Imaging Operator