The dynamics of message passing on dense graphs, with applications to compressed sensing

Mohsen Bayati, Andrea Montanari

Approximate message passing algorithms proved to be extremely effective in reconstructing sparse signals from a small number of incoherent linear measurements. Extensive numerical…