Compressive Imaging using Turbo AMP

About the Algorithm

The Turbo AMP is a fast iterative approximate message passing (AMP) algorithm that exploits the probabilistic structure in the sparsity pattern of a signal to reconstruct it from undersampled measurements. Natural images exhibit structured sparsity in the wavelet domain. The wavelet coefficients are not only sparse, but they also exhibit a structure in the support or sparsity pattern known as persistence across scales. This is modeled as hidden Markov tree (HMT). Messages on sparsity pattern are exchanged between two soft inference blocks – one exploiting the linear observation model and the other exploiting the HMT structure of the support. At every iteration the message passing within the observation block is done using the AMP framework. The message passing within the sparsity pattern block is done by a single pass of forward-backward algorithm which computes exact belief on this tree structured non-loopy sub-graph.

Download (Version 1.1, Feb 10, 2013)

Matlab® implementation (Wavelet toolbox is required):

• Unix/Mac users: click here to download tar.gz file.

• Windows users: click here to download zip file.

Publications

1. Turbo Reconstruction of Structured Sparse Signals", P. Schniter, Proc. Conf. on Information Sciences and Systems, Princeton, NJ, Mar. 2010. (slides)

2. “Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior”, S. Som, L.C. Potter and P. Schniter, Proc. Asilomar Conference on Signals, Systems, and Computers, pp. 243–247, Pacific Grove, CA, Nov 2010. (slides)

3. “Compressive Imaging using Approximate Message Passing and a Markov-Tree Prior”, S. Som and P. Schniter, IEEE Transactions on Signal Processing, vol. 60 , issue 7, pp. 3439–3448, July 2012 (arXiv).

Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant Number CCF-1018368.

Example Reconstruction

Following is an example of reconstruction of a 128 x 128 image (16384 pixels) from 5000 measurements.