Dror Baron - Compressed Sensing Reconstruction Algorithms

Compressed sensing: Compressed sensing (CS) is a new framework for integrated sensing and compression. The fundamental revelation is that, if an N-sample signal x is sparse and has a good K-term approximation in some basis, then it can be reconstructed using M =O(K log(N/K)) << N linear projections of x onto another basis. Furthermore, x can be reconstructed using linear programming, which has polynomial complexity. Some of the CS projects I have worked on are described here, and links to numerous other papers appear on the Nuit Blanche blog and the compressed sensing resource page.

Sudocodes (fast CS decoding algorithms): Linear programming CS decoding received much initial attention, yet requires at least quadratic (or even cubic) computation, which is excessive for decoding large signals such as million-pixel images. Decoding is computationally challenging, because we need to (i) take products of the measurement matrix with the signal vector, and (ii) many algorithms iterate over the data numerous times. To reduce computation, we have proposed to use sparse CS encoding matrices that offer fast matrix-vector multiplication. We first used these matrices along with a graph-reduction technique intended for the somewhat narrow application of decoding noiseless measurements of exactly sparse data. Our Sudocodes technique, which resembles the Sudoku game, requires O(K polylog(N)) computation for this problem. This Sudocodes algorithm was also studied by Ilya Poltorak in an excellent undergraduate project jointly supervised by Deanna Needell. Our work appeared at the Workshop on Linear Programming and Message-Passing Approaches to High-Density Parity-Check Codes and High-Density Graphical Models, March 2010, Tel Aviv University, Israel (ppt).

A limitation of Sudocodes is that it requires noiseless measurements. Yanting Ma, Deanna Needell, and I significantly extended the algorthm to the noisy measurement setting. This Noisy-Sudocodes algorithm partitions the signal reconstruction process into two parts. Part 1 applies a fast algorithm to identify zero coefficients of the input signal, whereas various CS algorithms can be applied to Part 2 to process the coefficients left over from Part 1. With approximate message passing (AMP) in Part 2, we provide a theoretical analysis that characterizes the trade-off between the measurement rate R, runtime, and reconstruction quality. (The plot below illustrates the relationship between R, runtime, and the signal to distortion ratio.)

Compressive Imaging
With the 1-bit CS algorithm binary iterative hard Thresholding (BIHT) in Part 2, numerical results show that Noisy-Sudocodes offers a better speed-quality trade-off than the original BIHT algorithm in a 1-bit CS setting. Our work appears in the following works.
Belief propagation: To approach CS decoding problems where the data is not exactly sparse and measurements may be noisy, we proposed a Bayesian setting. We focused on a two-state mixture Gaussian signal model, but more sophisticated models can also be incorporated, including support for measurement noise. Our decoder relies on belief propagation (BP), a technique that is commonly used for signal estimation in various DSP applications and for channel decoding of turbo and LDPC codes. The CS-BP decoder represents the CS encoding matrix by a bipartite graph. In each iteration, nodes that correspond to signal coefficients and measurements estimate their corresponding conditional probabilities and then convey this information to neighboring nodes. Because the encoding matrix is sparse, the bipartite graph is also sparse, and so each CS-BP iteration runs in O(N log(N)) time. The number of iterations is logarithmic in N. Feel free to download the Matlab code.

A potentially important feature of CS-BP is that it relies on a Bayesian approach that exploits knowledge of the statistics in order to estimate the input better, thus enabling a reduction in the number of measurements. A discussion of CS-BP appears on Igor Carron's blog.

Image reconstruction from compressive measurements: Compressive imaging algorithms recover images from a reduced number of linear measurements, which have potential applications in medical imaging, seismic imaging, and hyperspectral imaging. We propose compressive imaging algorithms that apply image denoisers within the approximate message passing framework. Numerical results show that with an adaptive Wiener filter as the image denoiser, our algorithm offers lower mean square error as well as substantially less runtime than the state of the art. The plot below shows that our AMP-Wiener achieves lower (better) normalized mean square error (NMSE) than the prior-art Turbo-GM algorithm over a range of measurement rates R.
Compressive Imaging
  • J. Tan, Y. Ma, and D. Baron, "Compressive Imaging via Approximate Message Passing with Wavelet-Based Image Denoising," Proc. IEEE Global Conf. Signal Inf. Process., Atlanta, GA, December 2014 (pdf, talk).
  • J. Tan, Y. Ma, and D. Baron, "Compressive Imaging via Approximate Message Passing with Image Denoising," IEEE Trans. Signal Proc., vol. 63, no. 8, pp. 2085-2092, April 2015 (pdf, arxiv). You may also want to view our tutorial video by Jin Tan and Yanting Ma about this research work.
    Back to my homepage.
    Last updated June 2014.