Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction

Abstract

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.

5 pages, IEEE Information Theory Workshop, Cairo 2010

References in corpus (2)

• Message Passing Algorithms for Compressed Sensing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing

Cited by in corpus (4)

• Approximate message-passing with spatially coupled structured operators, with applications to compressed sensing and sparse superposition codes
• Divide and Conquer: An Incremental Sparsity Promoting Compressive Sampling Approach for Polynomial Chaos Expansions
• Distributed Ranging and Localization for Wireless Networks via Compressed Sensing
• Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation