Recently, Donoho, Maleki and Montanari introduced approximate message passing (AMP) as an extremely effective algorithm for reconstructing high dimensional sparse signals from a small number of observations. They also showed (through extensive numerical experiments) that dynamics of AMP is accurately tracked by a simple one-dimensional iteration termed "state evolution". In this talk we prove...