We conduct an asymptotic risk analysis of the nonlocal means image denoising
algorithm for the Horizon class of images that are piecewise constant with a
sharp edge discontinuity. We prove that the mean square risk of an optimally
tuned nonlocal means algorithm decays according to $n^{-1}\log^{1/2+\epsilon}
n$, for an $n$-pixel image with $\epsilon>0$. This decay rate is an improvement
over some of the predecessors of this algorithm, including the linear
convolution filter, median filter, and the SUSAN filter, each of which provides
a rate of only $n^{-2/3}$.

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.