IEEE Signal Processing - May 2018 - 43

holds for all of the K-sparse signal f, where d K is the
restricted isometry constant of a matrix U.
■ Incoherence property: This requires that the rows of mea-
surement matrix U cannot sparsely represent the columns
of the sparsifying matrix W and vice versa. More specifi-
cally, a good measurement will pick up a little bit of infor-
mation from each component in s based on the condition
that U is incoherent with W. As a result, the extracted
information can be maximized by using the minimal num-
ber of measurements.
Research has pointed out [71] that verifying both the RIP con-
dition and the incoherence property is computationally compli-
cated but could be achieved with a high probability simply by
selecting U as a random matrix. The common random matri-
ces include the Gaussian matrix, Bernoulli matrix, and almost
all other matrices with independent and identically distributed
(i.i.d.) entries. Besides, with the properties of the matrix with
i.i.d. entries U, the matrix H = UW is also randomly i.i.d.,
regardless of the choice of W. Therefore, the random matrices
are universal, as they are random enough to be incoherent with
any fixed basis. Previous work has demonstrated [72] that ran-
dom measurements can universally capture the information rel-
evant for many compressive signal processing applications
without any prior knowledge of either the signal class and its
sparse domain or the ultimate signal processing task.
Moreover, for Gaussian matrices, the number of measure-
ments required to guarantee exact signal recovery is minimal.
However, random matrices inherently have two major draw-
backs in practical applications: huge memory buffering for stor-
age of matrix elements and high computational complexity due
to their completely unstructured nature [16]. In contrast to the
standard CS that limits its scope to standard discrete-to-discrete

measurement architectures using random measurement matrices
and signal models based on standard sparsity, researchers have
proposed more structured sensing architectures, i.e., structured
CS, to implement CS on feasible acquisition hardware. So far,
many efforts have focused on designing structured CS matrices,
e.g., the random demodulator [17], to make CS implementable
at the expense of performance degradation. In particular, the
main principle of the random demodulator is to multiply the
input signal with a high-rate pseudonoise sequence, which
spreads the signal across the entire spectrum. Then, a low-pass
antialiasing filter is applied, and the signal is captured by sam-
pling it at a relatively low rate. With additional digital process-
ing to reduce the burden on the analog hardware, the random
demodulator bypasses the need for a high-rate analog-to-digital
converter (ADC) [17]. A comparison of the Gaussian sampling
matrix and the random demodulator is provided in Figure 2 in
terms of detection probability, with different compression P/N
ratios. As shown in Figure 2, the Gaussian sampling matrix per-
forms better than the random demodulator.

Signal reconstruction
After the compressed measurements are collected, the orig-
inal signal should be reconstructed. Since most of the basis
coefficients in s are negligible, the original signal can be
reconstructed by finding out the minimal set of coefficients
that matches the set of compressed measurements x, i.e.,
by solving
st = arg min
s
s

S2
s
S= s
0

s
S= s
0
S1

S3
1 -1 0
0 0 1
(a)

Θ2 =

(4)

to Hs = x,

where $ , p is the , p-norm and p = 0 corresponds to count-
ing the number of nonzero elements in s. However, the

s
S= s
0

Θ1 =

, p subject

S3
1
0

0
0

0
1

Θ3 =

(b)

1
0

0
1
(c)

FIGURE 1. The projection of a sparse signal with one nonzero component with different sensing matrices: (a) worst projection, (b) bad projection, and
(c) good projection.
IEEE Signal Processing Magazine

May 2018

Table of Contents for the Digital Edition of IEEE Signal Processing - May 2018