Prerequisites & Notation

Prerequisites for This Chapter

This chapter develops OAMP/VAMP — the algorithm family that replaces AMP when the sensing matrix $\mathbf{A}$ is not i.i.d. Gaussian. We first recap AMP and explain its failure for RF imaging operators, then build OAMP from scratch, exploit Kronecker structure for efficiency, and design denoisers ranging from classical to learned.

Prerequisites:

Factor Graphs and Belief Propagation — Factor graphs, sum-product message passing, the Gaussian BP specialization. OAMP is derived from expectation propagation on the dense CS factor graph.
FSI Ch 20 — AMP in Depth — The derivation of AMP, the Onsager correction, and state evolution. We recap the essentials in Section 17.1, but readers who have studied AMP in FSI will find the material more natural.

Factor graphs and belief propagation(Review ch16)
Self-check: Can you write the BP messages for a Gaussian linear model?
AMP iteration and the Onsager correction
Self-check: Can you write one AMP iteration and explain why the Onsager term matters?
Singular value decomposition (SVD)
Self-check: Can you compute the SVD of a matrix and interpret the singular values?
Kronecker product and its properties
Self-check: Can you evaluate $(\mathbf{A} \otimes \mathbf{B})^{-1}$ in terms of $\mathbf{A}^{-1}$ and $\mathbf{B}^{-1}$ ?
LMMSE estimation
Self-check: Can you write the LMMSE estimator for a linear Gaussian model?

Notation and Conventions

Symbols introduced and used in this chapter. We follow the conventions of the RF imaging forward model from Chapter 8.

Symbol	Meaning	Introduced
$\mathbf{A} \in \mathbb{C}^{M \times N}$	Sensing (measurement) matrix	s01
$\mathbf{c} \in \mathbb{C}^N$	Reflectivity vector (true scene)	s01
$\mathbf{y} = \mathbf{A}\mathbf{c} + \mathbf{w}$	Linear imaging observation model	s01
$\sigma^2$	Noise variance	s01
$\delta = M/N$	Measurement ratio (undersampling ratio)	s01
$\hat{\mathbf{c}}^t$	Estimate of the reflectivity at iteration $t$	s01
$\mathbf{r}^t$	Residual at iteration $t$	s01
$\eta_t(\cdot)$	Denoiser at iteration $t$	s01
$\tau_t$	Effective noise variance (state evolution parameter) at iteration $t$	s01
$\mathbf{A}_{1}, \mathbf{A}_{2}$	Kronecker factors of the sensing matrix: $\mathbf{A} = \mathbf{A}_{1} \otimes \mathbf{A}_{2}$	s03
$\hat{\mathbf{c}}_1^t, \hat{\mathbf{c}}_2^t$	Outputs of the LMMSE step and denoiser step, respectively	s02
$v_1^t, v_2^t$	MSE of the LMMSE step and denoiser step	s02
$\text{div}(\eta)$	Divergence of the denoiser: $\frac{1}{N}\sum_i \frac{\partial \eta_i}{\partial r_i}$	s02

← Ch 16 AMP Recap and Its Failure for RF Imaging