Consider the noisy underdetermined system of linear equations: y=Ax0 + z0,
with n x N measurement matrix A, n < N, and Gaussian white noise z0 ~
N(0,\sigma^2 I). Both y and A are known, both x0 and z0 are unknown, and we
seek an approximation to x0. When x0 has few nonzeros, useful approximations
are obtained by l1-penalized l2 minimization, in which the reconstruction \hxl
solves min || y - Ax||^2/2 + \lambda ||x||_1.

In a recent paper, the authors proposed a new class of low-complexity
iterative thresholding algorithms for reconstructing sparse signals from a
small set of linear measurements \cite{DMM}. The new algorithms are broadly
referred to as AMP, for approximate message passing. This is the second of two
conference papers describing the derivation of these algorithms, connection
with related literature, extensions of original framework, and new empirical
evidence.