Compressive sensing via belief propagation
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,
- D. Baron, S. Sarvotham, and R. G. Baraniuk, "Bayesian Compressive Sensing via Belief Propagation," submitted for publication (pdf).
The code was rewritten by Danny Bickson in March 2009; 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 standard 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.
Authors: Dror Baron, Shriram SarvothamPublication: Bayesian Compressive Sensing via Belief Propagation
Related Research at Rice: Compressive sensing DNA microarrays
Copyright ©2009, DSP Group, Rice University