Compressive sensing via belief propagation software
A more stable software implementation of belief propagation can be found on our fault identification software page. We recommend that people download code from there. Feel free to also browse through other software packages developed by our group.

Dror, October 2011

This webpage describes the Matlab files used to simulate our CS-BP algorithm: compressive sensing decoding via belief propagation. Technical details appear in our paper, This code was written by Danny Bickson, his implementation appears here.

This project presents an O(N log^2(N)) decoder using two contributions. First, we use CS-LDPC encoding matrices, which consist mostly of zeros, where nonzero entries are {-1,+1}. Second, we incorporate a prior on the signal model (and possible measurement noise model) via belief propagation (BP), a well-known technique for performing approximate Bayesian inference. Our specific example mostly use a two-state mixture Gaussian signal model, but other models can be incorporated in the code.

Our implementation uses samples of probability density functions (pdf's) as messages. To compute convolution of messages, the fast Fourier transform (FFT) is used. A significant percentage of CPU time is spent on FFT's, and the code can be accelerated using a message length that factors well.

Some commentary must be provided on choice of message lengths. In the paper, we recommend that spacing of samples be at least as fine as sigma_0, the stadard deviation of the narrow Gaussian mixture component. Some of the messages reflect distributions of measurements, which may combine several large coefficients. For example, some of our simulations used L=20 and S=K/N=0.1, which implies that on average L*S=2 larger coefficients are captured per message, but some messages may contain 5 or 6 larger coefficients. Consequently, some messages have amplitudes exceeding 5*sigma_1; limiting the absolute magnitude of messages to 5*sigma_1 degrades reconstruction quality somewhat. Instead, the range (-10*sigma_1,+10*sigma_1) offers better quality. Because our simulations use sigma_1=10*sigma_0, choosing approximately 200 samples makes sense. As noted before, the message length should factor well for fast FFT computation. Also, message length must be odd (an artifact of the implementation), and so we chose 243.

Several files below illustrate how to use our package. The recommended usage is illustrated by main.m. First, the sparse signal must be generated; generatex_noisy.m can be used to do so, but any vector signal will do. Second, the LDPC-CS encoding matrix must be generated using gen_phi.M. The matrix is not an actual matrix but uses a special format. Third, driver_function.m is called. Another way to use our package is shown by sims1c.m, sims2d.m, sims3b.m, and sims4b,m; these files run driver.m, which is a script file.

Any comments will be appreciated.

Dror Baron, December 2008

Significant routines The following routines were written by Shriram Sarvotham, Dror added some comments.
Simulations that appear in paper

In order to help other researchers reproduce our numerical results, we include the files used to generate our figures.

Other reconstruction techniques used

Our simulations compared CS-BP to CoSaMP and ell_1 decoding. The files used were sent to us by Justin Romberg and Volkan Cevher.

Minor functions

We now list various minor functions. Many of these can be easily implemented using standard Matlab routines. However, some of the standard Matlab routines contain code for protecting against incorrect usage, which is immaterial here and slows things down. It might be possible to accelerate the code by inlining some of the function calls.

Back to my homepage.