We are also developing algorithms and hardware to support a new theory of Compressive Imaging.
Our approach is based on a new camera that directly acquires
random projections of a digital image/video without first collecting the set of pixels. Our camera architecture
employs a digital micromirror array to perform optical calculations of linear projections of an image onto
pseudorandom binary patterns. Its hallmarks include the ability to obtain an image with a single detection
element (photodiode) while sampling the image fewer times than the number of pixels. This camera also
inherits the compressive sensing benefits of universality, robustness, progressivity, and computational
asymmetry. Perhaps the most intriguing feature of the system is that, since it relies on a single photon
detector, it can be adapted to image at wavelengths that are currently impossible with conventional CCD
and CMOS imagers.
Publications: SPIE Electronic Imaging (2006),
ICIP Conference (2006).
We are currently developing new theory and mixed-signal hardware designs for
Analog-to-Information (A/I) Conversion. Such systems will significantly reduce
the burden on analog-to-digital conversion for sampling and compression of high-bandwidth
signals. The key ideas is that, rather than sampling an analog signal signal at its
Nyquist rate and then computing incoherent projections (effectively discarding most of
the samples), these systems will directly acquire and produce a low-rate stream of
incoherent measurements.
Rice / Michigan A/I Project
Publication: ICASSP Conference (2006).
Compressive Signal Processing
Most of the work in CS has focused on the issue of
reconstructing a signal. However, in practice we are often
only interested in detecting or estimating some
signal or quantity of interest. Luckily, the CS framework is
information scalable in that CS measurements are useful for
a wide range of statistical inference tasks. In particular, it is
possible to solve a variety of signal detection, classification, and
estimation problems given the measurements without ever
reconstructing the signals themselves. We consider a number of
different settings. The smashed filter is a
dimensionality-reduced generalization of the classical matched
filter that exploits manifold models for classification. This
setting places no assumption about the compressibility of the
underlying signals. In contrast, we also consider the challenge of
detecting an unknown sparse signal and propose the
incoherent detection and estimation algorithm (IDEA) as a
method for tackling this problem. Both the smashed filter and IDEA
are effective methods for signal classification using compressive
measurements that do not require a complete reconstruction
of the signal, and are capable of reliable performance even when the
number of measurements is significantly smaller than would be
required to reconstruct the signals.
Publications:
SPIE 2007,
ICASSP 2006,
Tech report.
Connections to Dimensionality Reduction
Random projections play a significant role in compressive sensing (CS). They also have played an
important role in the field of dimensionality reduction, for example in the proof of the
Johnson-Lindenstrauss (JL) lemma. In both cases, the key idea is that the relevant structure in a
signal can be preserved when that signal is projected onto a small number of random basis functions.
In fact, we have shown that the fundamental results on the recovery of sparse signals are intimately
related to the JL-lemma. Our elementary approach is based on the same concentration inequalities for
random inner products that have recently provided simple proofs of the JL-lemma. We also have shown
how these ideas lead to simple proofs of classic theorems on widths of finite balls in Euclidean
space as well as the existence of optimal CS measurement matrices.
Publication:
Journal Preprint (2007).
Furthermore, the CS connections with dimensionality reduction also provide insight into cases where
we have a more specific low-dimensional model for signals, such as when the signal class forms a
nonlinear manifold. The key theoretical motivation for this case comes from Whitney’s Embedding
Theorem, which allows us to consider the task of recovering a manifold-modeled signal from a
small number of random projections. We have provided preliminary theoretical and experimental
evidence that manifold-based signal structure can be preserved using small numbers of random
projections. Thanks to our more specific model, we can recover certain signals using far fewer
measurements than would be required using sparsity-driven CS techniques.
Publications:
Journal Preprint (2006),
ICASSP 2006 (2006).
Connections to Information Theory
Information theory has rich insights to offer
compressive sensing (CS) in terms of identifying
the fundamental performance limits and aid the design of low-complexity CS
algorithms. Our work on
Distributed Compressive Sensing
is an
example that is inspired by distributed
source coding. The current work is motivated by the observation that the
CS measurements serve to encode the original signal;
therefore information theory is the natural tool to study the performance
of CS. In particular, we investigate the minimum number of measurements
needed to reconstruct the signal within a specified distortion - a
problem related to the rate distortion theory. Our
investigation reveals that the unavoidable measurement noise in CS
measurements is the crucial factor that dictates the number of
measurements needed for reconstruction. To establish this result, we
model the noisy CS measurements as generated from an information theoretic
channel. Combining the capacity of this channel with the rate-distortion
function of the sparse signal, we obtain a lower bound on the number of CS
measurements needed. This result allows us to benchmark the performance
of specific reconstruction algorithms.
Publication:
Allerton Conference
(2006).
At a more practical level, we leverage the remarkable success of LDPC
codes to design low-complexity CS measurement
and reconstruction algorithms. In particular, we propose the use of low
density structure for the CS matrix and belief propagation for CS
reconstruction. This gives a new
perspective on CS reconstruction, namely as a Bayesian inference
problem.
Publication:
Journal Preprint
(2006).
For certain classes of signals, the use of sparse CS matrices facilitates
even simpler reconstruction algorithms with lower complexity than belief
propagation. Sudocodes are applicable to strictly sparse signals
that have been previously compressed by some algorithm. Potential
applications include distributed data storage systems
and content distribution networks.
Publication:
ISIT Conference
(2006).
Multi-Signal and Distributed Compressive Sensing
We have introduced a new theory for Distributed Compressive Sensing (DCS) that enables new
distributed coding algorithms for multi-signal ensembles that exploit both intra- and inter-signal
correlation structures. The DCS theory rests on a new concept that we term the joint sparsity of a
signal ensemble. We have studied in detail three simple models for jointly sparse signals, proposed
algorithms for joint recovery of multiple signals from incoherent projections, and characterized
theoretically and empirically the number of measurements per sensor required for accurate
reconstruction. We have also established a parallel with the Slepian-Wolf theorem from information
theory and established upper and lower bounds on the measurement rates required for encoding jointly
sparse signals. In two of our three models, the results are asymptotically best-possible, meaning
that both the upper and lower bounds match the performance of our practical algorithms. Moreover,
simulations indicate that the asymptotics take effect with just a moderate number of signals.
In some sense DCS is a framework for distributed compression of sources with memory, which has
remained a challenging problem for some time. DCS is immediately applicable to a range of problems
in sensor networks and arrays.
Publications:
Journal Preprint (2005),
Allerton Conference (2005),
Asilomar Conference (2005).
Tree Matching Pursuit
The compressive sensing framework aims to recover a sparse signal from a small set of
projections onto random vectors; the problem reduces to searching for a sparse approximation
of this measurement vector. Conventional solutions involve linear programming or greedy
algorithms and can be computationally expensive. These techniques are generic, however,
and assume no structure in the signal aside from sparsity. We have designed an algorithm
that enables fast recovery of piecewise smooth signals - sparse signals that have a
distinct "connected tree" structure in the wavelet domain. Our
Tree Matching Pursuit (TMP) algorithm significantly reduces the search space of
the traditional Matching Pursuit greedy algorithm, resulting in a substantial decrease
in computational complexity for recovering piecewise smooth signals. An additional
advantage of TMP is that it performs an implicit regularization to combat noise in
the reconstruction. TMP also applies to the more general case of "incoherent"
measurement vectors.
Publication: SPARS Workshop (2005).
