Signal Processing - September 2016 - 82

can perform image-sensing tasks with far less overhead in
processing, transmission, and data storage than the current
camera-based counterparts. While the examples in this article
focus on images and videos, the use of such CI systems for
depth and hyperspectral acquisition can further leverage such
benefits and are also being explored by many researchers.
Specifically, CI (and, more generally, CS) aims to sense a
signal x ! R N from an underdetermined linear system, i.e.,
measurements of the form
y = Ux + e,

(1)

where U ! R M # N with M < N, and e is the measurement
noise. For an arbitrary signal in R N , this is impossible since
the map U : R N 7 R M is many to one and noninvertible. CS
handles this by restricting the signal x to belong to a distinguished class, e.g., signals that are sparse. The main results of
CS state that when the measurement matrix U has a special
structure and x is K-sparse (or having K or fewer nonzero
entries), then we can robustly recover x, provided that M is
sufficiently large. These basic results have been extended
beyond real-space sparse imaging to include signals that are
sparse in a transform domain, have sparse gradients [26], lowrank matrices [10], and low-dimensional manifolds [5].
A classic example of CI in practice is the single pixel camera
(SPC), which consists of an optical modulator and a single photodetector that obtains coded linear or compressive measurements of the scene. A schematic and further description of the
SPC is highlighted in "Signal Pixel Camera Basics." The compressive measurements y t ! R taken by an SPC at the sample instants t = 1, f, T can be modeled as y t = z t, x t + e t,
where T is the total number of acquired samples, z t ! R N # 1
is the measurement vector, e t ! R represents measurement
noise, and x t ! R N # 1 is the scene (or frame) at sample instant
t. We assume that the two-dimensional (2-D) scene consists of
n # n spatial pixels that, when vectorized, results in the vector
x t of dimension N = n 2. We also use the notation y 1:W to represent the vector consisting of a window of W # T successive
compressive measurements (samples), i.e.,

y 1:W

y1
z 1, x 1 + e 1
=> h H=>
h
H.
zW, xW + eW
yW

(2)

If we further assume that the scene is static (as is the case
when we are sensing an image), then x 1 = x 2 = g = x W = x
and we obtain the imaging model in (1).
The theoretical results of CI rely heavily on the properties
of random matrices, i.e., matrices whose entries are sampled
from certain distributions. A central result states that, when a
matrix U ! R M # N satisfies the so-called restricted isometry
property (RIP) on all K-sparse signals, then it is possible to
stably recover all K-sparse signals from linear measurements
as in (1). Specifically, the measurement operator U is said to
satisfy the RIP with constant d 2 0 if, for every K-sparse signals x 1, x 2 , the following relations hold:
82

(1 - d) x 1 - x 2

# Ux 1 - Ux 2

# (1 + d) x 1 - x 2 2 .

(3)

The quantity d encapsulates the deviation from perfect isometry
and is called the isometry constant. Random matrices provide a
simple and elegant method to construct measurement operators
that satisfy the RIP. When the entries of U are sampled independent and identically distributed (i.i.d.) from sub-Gaussian
distributions, then U satisfies the RIP with overwhelming probability provided M = O (K log (N/K )) [4]. Similarly, measurement operators U obtained via randomly subsampling the rows
of certain orthonormal matrices satisfy the RIP with overwhelming probability [11]. Both designs for enabling measurement matrices with the RIP are universal, i.e., they are
independent of the application.
Many of the early CI systems used random constructions
for measurement matrices. However, despite their conceptual
simplicity, random projections suffer from certain shortcomings that make them impractical. Their theoretical guarantees are probabilistic, i.e., there is a nonzero chance that the
obtained embedding does not satisfy a (near) isometry, and
asymptotic, i.e., the guarantees hold only when the problem
dimensions are sufficiently high. Further, by virtue of universality, random matrices are independent of both the data
under consideration as well as the eventual inference task that
we seek to perform. As a consequence, the use of random
projections precludes us from leveraging special geometric
structure that might be present in the data or the inference
task. From a practical standpoint, large random matrices are
also extremely cumbersome, requiring storage and processing requirements that become prohibitive when sensing highdimensional signals.
In this article, we survey recent trends in the construction
of deterministic matrices for CI and highlight key areas where
the use of specifically designed measurement matrices provide
significant improvements over random constructions. We discuss the following three applications.
■ Structured CI using signature-preserving matrices:
Careful design of measurement operators can enable us to
sense certain structures effectively. We present a new interpretation/construction of Hadamard codes using signatureblocks that arranges patterns into groups that share a
certain local signature or sequency. The codes can aid in
analyzing the scene without having to computationally
reconstruct an image, e.g., assessing the signal-to-noise
ratio (SNR) of different blocks, and determining which signatures (i.e., features) are most prominent. This new
approach to constructing acquisition patterns benefits in
both faster recovery and enhanced image quality as well as
in object recognition and tracking tasks. Further, the block
structure also permits low-resolution previews of different
signature-filtered versions of the observed scene.
■ Motion predictive video CS using dual-scale sensing
(DSS) matrices: We show that measurement matrices
can be endowed to sense the scene at multiple spatial
scales, simultaneously. This enables real-time recovery of
the video, albeit at a lower spatial resolution, and can

IEEE SIgnal ProcESSIng MagazInE

September 2016

Table of Contents for the Digital Edition of Signal Processing - September 2016