Signal Processing - September 2016 - 84

on the columns. Extending this to higher dimensions is
Reconstruction-free inference: The eventual goal in
straightforward. Recently, Kronecker product-based CS has
many applications is often not just reconstruction of an
been explored in the context of multidimensional signals [13].
image but an inference problem pertaining to detection,
Arguably though, the Kronecker product's most crucial role is
tracking, recognition, and/or classification. While inferin enabling fast implementations of important mathematical
ence can be performed postreconstruction on the output of
functions, such as the discrete Fourier transform, the Haar
a reconstruction procedure, there are important benefits to
wavelet, and the Hadamard transform. We are particularly
be gained by performing them directly on the compressive
interested in the Kronecker product-based constructions of
domain. First, many inference tasks are inherently simpler
Hadamard matrices, which have had a long history in imaging
than reconstruction; hence, there is hope that we can perand optics [16].
form them with fewer measurements. Second, CS reconA Hadamard matrix is an orthogonal matrix with entries
struction is intrinsically tied to the signal models used for
restricted to just {!1} . Power-of-two Hadamard matrices are
the unknown signal and these signal models prioritize features that deal with visual perception,
often thought of as a square-wave version
which often is not the most relevant for
of the discrete cosine transform (DCT) and
The Kronecker product
the subsequent processing tasks. Third,
are attractive since they have an associated
is used throughout
reconstruction algorithms associated
fast transform. However, Hadamard matrimathematical sciences
with CS have high computational comces of sizes other than powers of two exist
plexity; hence, avoiding a reconstruction
as well, and they can also have fast transin countless applications
step in the overall processing pipeline
forms. The rows of Hadamard matrices are
such as signal/image
can be beneficial. To highlight these benusually described in terms of their sequenprocessing, control
eficial aspects of compressive inference
cy, which is similar to the notion of the fretheory, quantum
and the critical role that measurement
quency of a sinusoid. Sequency is simply
computing, etc.
operator design plays in it, we will
the number of !1 transitions contained in a
review techniques that let us solve highHadamard waveform.
level computer vision problems (e.g., object, face, and
The local signature-based measurement matrix design preactivity recognition) by foregoing reconstruction in favor
sented here is a simple generalization of the standard Kroneckof inference.
er product. The typical Kronecker product of matrices A and
In many ways, the examples that we discuss fall under the
B is defined [33] as A 7 B: = [a ij B], where aij is the (i, j)th elebroad category of model-based CS [3], where signal models
ment of matrix A. From the definition, we see that commuting
beyond simple sparsity are used to obtain recovery guarantees
the factors A and B in general yields A 7 B ! B 7 A. Note
with fewer measurements. A key distinction is that the results
that the elements of the left-hand factor provide the weights for
of model-based CS rely on random matrix constructions, while
the copies of the right-hand factor. Qualitatively, we can think
we seek alternative methods that are domain- and task-specific.
of the left-hand factor A as the modulator and the right-hand
factor B as that which is modulated. In this sense, the rows of
B provide the local patterns that ultimately generate the global
Structured compressive imaging
patterns
in the rows of A 7 B. These shorter, local patterns can
In this section, we present a method of generating measurebe thought of as signatures.
ment matrices that are endowed with unique local signatures.
These waveforms can be used to make measurements of a
scene of interest with applications in imaging and detection/
The signature row-block Kronecker product
classification. We introduce a generalized Kronecker product
Suppose matrices A and B, respectively, have K and L rows,
that generates a matrix with blocks of rows where, within
i.e., A = [a i] Ki =-01, B = [b i] iL=-01 . The signature row-block (SRB)
each block, the rows all share the same local signature (i.e., a
Kronecker product is defined as
specific spatial pattern). The individual rows can be used as
a0 7 b j
B0
patterns, e.g., on a spatial light modulator (SLM) in an optical
A 7 SRB {B} : = > h H, B j : = A 7 b j = >
h
system that observes a scene.
H. (4)
BL - 1
aK - 1 7 b j

■

The Kronecker product

The Kronecker product is used throughout mathematical sciences in countless applications such as signal/image processing, control theory, quantum computing, etc. Part of its
utility comes from the ability to tensor together low-dimensional ideas into larger systems [33]. The Kronecker product
has long been used whenever operators are separable. A classical example is when an image is represented as a matrix
and the transformed image can be separated into two functions, one that operates on the rows and another that operates
84

Here, B j is the jth SRB, which consists of the K rows of A
that modulate just signature b j . The signature rows of matrix
B analyze/synthesize the local patches of pixels in the image,
and the rows of matrix A simply multiplex these into the larger, global measurement patterns. Hence, it is matrix B that is
directly tied to the model-based acquisition strategy. For
example, in CS applications, matrix B could be a dictionary
previously trained by a principal component analysis to have
maximal incoherence with respect to the sparsity basis of an

IEEE SIgnal ProcESSIng MagazInE

September 2016

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