  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 first of two
conference papers describing the derivation of these algorithms, connection
with the related literature, extensions of the original framework, and new
empirical evidence.
  In particular, the present paper outlines the derivation of AMP from standard
sum-product belief propagation, and its extension in several directions. We
also discuss relations with formal calculations based on statistical mechanics
methods.
