Approximate message passing (ECE 592 Module 50)

This module looks at approximate message passing (AMP), which converts a complicated signal recovery problem, y=A*x+z , to a simpler problem, v=x+noise, where the noise is Gaussian. A denoising function is applied iteratively to v, and typically during the first few iterations the variance of the Gaussian noise declines toward a noise floor. The denoiser can be a simple elementwise scalar denoiser, or it can denoise multiple correlated signal entries together. State evolution (SE) is a framework that evaluates how the error evolves between AMP iterations; some rigorous results for SE exist. A numerical example for a Markovian signal shows that the empirical performance of AMP matches the SE prediction. Moreover, denoising 3 correlated signal entries together yields markedly lower error than an elementwise denoiser. Finally, AMP's computation is dominated by 2 matrix vector products per iteration, and because we typically only need a modest number of iterations, it is fast.