Signal Processing - September 2016 - 92

Can We Learn good Measurement Matrices?

Domain-specific design of measurement operators
Can we learn measurement operators that can be tuned to
the specifics of an application or data domain and, fur-

ther, incorporate task-specific constraints? Specifically,
given a collection of data {x 1, x 2, f, x Q ! R N}, we pose the
problem of learning a measurement matrix U ! R M # N that
satisfies the RIP on this data set, i.e., we seek a matrix
U ! R M # N that satisfies
6i, j, (1 - d) #

0.05
0
-0.05
-0.1
-0.15
-0.2
Measurement
Patterns Learned by PCA

(S1)

Unfortunately, solving for a matrix U with the fewest rows
that satisfy (S1) is a nonconvex problem. In particular,
while this is a hard optimization problem over U, by using
a lifting operation, we can pose this as an optimization
problem over the gram matrix P = U T U. Note that the RIP
constraints that are nonlinear in U can be written as

0.2
0.15
0.1

Two-Class
Data Set

(x i - x j ) T U T U (x i - x j )
# (1 + d).
xi - xj 2

Measurement
Patterns Learned by NuMax

Misclassification Rate

The criterion of near isometry is geared toward enabling
reconstruction that is not necessarily conducive to inference. As an example, consider classification of two classes
using a nearest-neighbor (NN) classifier. The near-isometry
property underlying RIP ensures that distances are approximately preserved, and, therefore, NNs are approximately
preserved. Yet, the preservation of distance is not necessary for NN classification. Indeed it is sufficient if the measurement operator does not perturb the class membership
of the NN of a point. Intuitively, this is a significantly simpler constraint to satisfy, and we can hope to achieve it
with far fewer measurements.

0.35

Random
PCA
NuMax

0.3
0.25
0.2
0.15
0.1
0.05

5
10 15 20 25 30
Number of Measurements
Reconstruction Performance

Figure S2. Learning measurement operators using NuMax. We compare the performance of NuMax, principal component analysis (PCA) and
random projection on a two-class problem. NuMax outperforms the other methods due to is reliance on both the domain (i.e., the data set) and
its preservation of neighborhoods via the RIP. (Images used courtesy of [23].)

several criterion, from preservation of the fidelity of
extracted features or promotion of class separability.
Exploring these ideas could form the basis for impactful
future work in this area.

Open problems
The earliest results in CS were broad in their scope and universal in their applicability to all sparse signals. Yet, this
implicit simplicity created a significant mismatch to realworld signals that are often enriched with structures that are
more complex than sparsity. Efficient sensing and inference
with such signals requires a fundamental rethinking of all
aspects of CS, including the prime role played by measurement
matrices. While this article highlights this important aspect
using three case studies, there are many important open problems that need to be addressed to truly harness the potential of
nonrandom matrix constructions.
92

The need for deterministic matrix constructions
that rival the performance of random matrices
There has been some limited work on matrix constructions that
satisfy the RIP [12] (see "Can We Learn Good Measurement
Matrices?"). However, these require M~K 2 measurements that
are significantly worse than random constructions, and they further involve polynomials functions that are not amenable to imaging where there are physical constraints that allow only matrices
where entries need to be nonnegative and satisfy energy-preservation constraints. Further, SLMs that are typically used in CI often
constrain the measurement matrix to be binary valued. A theory of
measurement design that is deterministic while respecting the
physical laws of imaging would spur many novel applications.

Going beyond the RIP as the metric of choice
As noted in many earlier works including [12], the RIP is only a
sufficient condition for signal recovery and it is well known as a

IEEE SIgnal ProcESSIng MagazInE

September 2016

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