Prerequisites & Notation

Before You Begin

Approximate Message Passing (AMP) sits at the intersection of statistical physics, compressed sensing, and high-dimensional statistics. To follow the derivation and the state-evolution analysis comfortably, ensure the following background is fresh.

Compressed sensing: sparse recovery, RIP, basis pursuit, LASSO(Review ch17)
Self-check: Can you state the LASSO problem and its KKT conditions?
ISTA / proximal gradient methods and soft-thresholding(Review ch18)
Self-check: Can you derive the soft-threshold operator as the proximal map of $\lambda\|\cdot\|_1$ ?
Gaussian i.i.d. random matrices and their concentration properties
Self-check: Do you know why $\frac{1}{M}\mathbf{A}^H\mathbf{A} \to \mathbf{I}_N$ fails in the proportional asymptotic regime $N/M = \delta$ ?
MMSE estimation and scalar denoising in AWGN(Review ch06)
Self-check: Can you compute $\mathbb{E}[X|Y=y]$ for a Bernoulli--Gaussian prior observed in Gaussian noise?
Belief propagation on factor graphs and the Gaussian approximation
Self-check: Can you explain why sum-product messages on dense graphs converge to Gaussians?
Basic statistical physics: mean-field theory, Bethe free energy (helpful, not required)
Self-check: Are you familiar with the cavity method?

Notation for This Chapter

AMP operates on a linear observation model $\mathbf{y} = \mathbf{A}\mathbf{x} + \mathbf{w}$ with $\mathbf{A} \in \mathbb{R}^{M \times N}$ , $N$ and $M$ large. We track iterates indexed by $t = 0, 1, 2, \ldots$

Symbol	Meaning	Introduced
$\mathbf{A}$	Sensing / measurement matrix ( $M \times N$ , typically i.i.d. Gaussian with $\mathcal{N}(0, 1/M)$ entries)	s01
$\mathbf{x} \in \mathbb{R}^N$	Unknown signal to recover (assumed sparse or structured)	s01
$\mathbf{y} \in \mathbb{R}^M$	Observation vector	s01
$\mathbf{w}$	Additive Gaussian noise, $\mathbf{w} \sim \mathcal{N}(\mathbf{0}, \sigma^2\mathbf{I})$	s01
$\delta = M/N$	Undersampling ratio (measurements per unknown)	s01
$\rho$	Signal sparsity fraction ( $\\|\mathbf{x}\\|_0 / N$ )	s02
$\hat{\mathbf{x}}^t$	AMP estimate at iteration $t$	s01
$\mathbf{r}^t$	AMP residual at iteration $t$	s01
$\eta(\cdot;\theta)$	Denoiser function with parameter $\theta$ (e.g., threshold, noise variance)	s01
$\langle \eta'(\cdot) \rangle$	Empirical average of the denoiser's derivative (Onsager coefficient)	s01
$\tau_t^2$	State-evolution variance at iteration $t$	s02
$\mathrm{MSE}(\tau^2)$	Scalar MSE of the denoiser in effective noise of variance $\tau^2$	s02

← Ch 19 AMP from First Principles