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)) << Nlinear 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
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.
and R. G. Baraniuk,
"Sudocodes - Fast Measurement and Reconstruction of Sparse Signals,"
2006 IEEE International Symposium on Information Theory
(ISIT2006), Seattle, WA, July 2006
A limitation of Sudocodes is that it requires noiseless measurements.
and I significantly extended the algorthm to the noisy measurement
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.)
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.
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
D. Baron, and
R. G. Baraniuk,
"Compressed Sensing Reconstruction via Belief Propagation,"
Technical Report ECE-0601,
Electrical and Computer Engineering Department,
Rice University, July 2006
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
Y. Ma, and
"Compressive Imaging via Approximate Message
Passing with Wavelet-Based Image Denoising,"
Proc. IEEE Global Conf. Signal Inf. Process.,
Atlanta, GA, December 2014
Y. Ma, and
"Compressive Imaging via Approximate
Message Passing with Image Denoising,"
IEEE Trans. Signal Proc., vol. 63, no. 8, pp. 2085-2092, April 2015
You may also want to view our tutorial video by
Jin Tan and
about this research work.
Back to my homepage.
Last updated June 2014.