Approximate Message Passing (AMP) Code for Compressive Sensing.

Jort Gemmeke sent me the following:

Hi Igor,

David Donoho had a nice plenary here at SPARS2011 about approximate message passing for CS. After a bit of googling the subject, I stumbled over a matlab solver. Although its a very simple algorithm, still nice that someone implemented it already...you can find it here:

http://people.epfl.ch/ulugbek.kamilov

Maybe something for your big picture pages? Unless I didn't look well enough, I didnt see it there.

Cheers,

Jort

Jort is right, it is not there. Ulugbek Kamilov did make available his code featuring the Approximate Message Passing (AMP) code and I will feature it soon in the big picture. Ulugbek Kamilov's master's Thesis is Optimal Quantization for Sparse Reconstruction with Relaxed Belief Propagation. The abstract of the thesis reads:

Compressive sensing theory has demonstrated that sparse signals can be recovered from a small number of random linear measurements. However, for practical purposes, like storage, transmission, or processing with modern digital equipment, continuous-valued compressive sensing measurements need to be quantized. In this thesis we examine the topic of optimal quantization of compressive sensing measurements under reconstruction with messagepassing algorithms by following the work on generalization of relaxed belief propagation (BP) for arbitrary measurement channels. Relaxed BP is an iterative reconstruction algorithm proposed for the task of estimation from random linear measurements. It was inspired by the traditional belief propagation algorithm widely used in decoding of low-density parity-check (LDPC) codes. One of the aspects that makes relaxed belief propagation so appealing is the state evolution framework, which predicts asymptotic error behavior of the algorithm. We utilize the predictive capability of the framework to design mean-square optimal scalar quantizers under relaxed BP signal reconstruction. We demonstrate that error performance of the reconstruction can be significantly improved by using state evolution optimized quantizers, compared to quantizers obtained via traditional design schemes. We finally propose relaxed BP as a practical algorithm for reconstruction from measurements digitized with binned quantizers, which further improve error performance of the reconstruction.

The attendant code for AMP and phase transition related computation is here. I just tried and compared it with SL0, a fast code on its own but relying on finding the SVD of a potentially large matrix and the results are indeed very impressive for a 1-d signal of size 100,000. The code I used:

clear
% Number of iterations of the algorithm
T = 1000;

% Stopping criterion (tolerance for successfull decoding)
tol = 1e-4;
m = 200;
k = 2;
N = 100000;

A = (1/sqrt(m)) .* randn(m, N);

% Sparse signal (with uniform distribution of non-zeros)
x = [sign(rand(k,1) - 0.5); zeros(N-k,1)];
x = x(randperm(N));

% Generate Measurements
y = A*x;
tstart = tic;
% Recover x using AMP
x1 = reconstructAmp(A, y, T, tol);
t_elapsed_AMP = toc(tstart)
sigma_min = 0.00004;
sdf=0.95;
tstart = tic;
x2= SL0(A, y, sigma_min,sdf);
t_elapsed_SL0 = toc(tstart)
figure(1)
plot(x1,'*')
figure(2)
plot(x2,'o')

The results read:

t_elapsed_AMP =

3.2762

t_elapsed_SL0 =

172.2139

Thanks Jort.