IEEE Signal Processing Magazine - January 2018 - 143

Compressed Sensing Recovery
Compressed sensing (CS) [41], [43] is a framework for the
simultaneous sensing and compression of finite-dimension-
al vectors, which relies on linear dimensionality reduction.
In particular, the field of CS focuses on the following
recovery problem:

where x is an N # 1 sparse vector, i.e., with few nonzero
entries, and z is a vector of the measurements of size
M 1 N. CS provides recovery conditions and algorithms
to reconstruct x from the low-dimensional vector z.
The different spectrum-sensing applications described in
this article primarily deal with analog signals and sam-
pling techniques, while CS inherently defines a digital
framework. We will discuss how the analog approaches
of low-rate sampling use CS as a tool for recovery and
adapt it to the analog setting. To that end, we describe
here two CS greedy recovery algorithms that solve the
optimization problem
0

s.t. z = Ax,

(S2)

where · 0 denotes the , 0 -norm. The first algorithm we
consider belongs to the family of matching pursuit (MP)
methods [44]. The orthogonal MP algorithm iteratively
proceeds by finding the column of A that is most correlat-
ed to the signal residual r,
i = arg max A H r ,

(S3)

To sample the signal f (t), it is first modulated by a highrate sequence p c (t) created by a pseudorandom number
generator. It is then integrated and sampled at a low rate, as
shown in Figure 3. The random sequence used for demodulation is a square wave, which alternates between the levels ! 1
with equal probability. The K tones present in f (t) are thus
aliased by the pseudorandom sequence. The resulting demodulated signal y (t) = f (t) p c (t) is then integrated over a period
1 R and sampled at the low rate R. This integrate-and-dump
approach results in the following samples:
ym = R #

(m +1)/R

m/R

y (t) dt, m = 0, 1, f, R - 1.

(2)

The samples y m acquired by the random demodulator can
be written as a linear combination of the W # 1 sparse amplitude vector b that contains the coefficients b ~ at the corresponding locations ~ [22], [23]. In matrix form, we write
y = Ub,

r = z - Axt , .

(S1)

z = Ax,

xt = argmin
x
x

where the absolute value is computed elementwise. The
residual is obtained by subtracting the contribution of a
partial estimate xt , of the signal at the ,th iteration, from
z, as follows:

(3)

(S4)

Once the support set is updated by adding the index i, the
coefficients of xt , over the support set are updated, so as
to minimize the residual error.
Other greedy techniques include thresholding algo-
rithms. Here, we focus on the iterative hard thresholding
method proposed in [45]. Starting from an initial estimate
xt 0 = 0, the algorithm iterates a gradient descent step with
step size μ followed by hard thresholding, i.e.,
xt , = T (xt , -1 + nA H (z - Axt , -1), k),

(S5)

until a convergence criterion is met. Here, T ( x, k) denotes
a thresholding operator on x that sets all but the k entries
of x with the largest magnitudes to zero, and k is the
sparsity level of x, assumed to be known.
These two greedy algorithms and other CS recovery
techniques can be adapted to further settings, such as mul-
tiple measurement vectors, where the measurements z
and sparse objective x become matrices, infinite measure-
ment vectors, block sparsity, and more, as we will partially
discuss in the article. Further details on CS recovery condi-
tions and techniques can be found in [41] and [43].

where y is the vector of size R that contains the samples y m
and U is the known sampling matrix that describes the overall
action of the system on the vector of amplitudes b, i.e.,
demodulation and filtering (see [23] for more details). Capitalizing on the sparsity of the vector b, the amplitudes b ~ and
their respective locations ~ can be recovered from the lowrate samples y using CS [41] techniques like those discussed
in "Compressed Sensing Recovery," in turn, allowing for the
recovery of f (t). The minimal required number of samples R
for perfect recovery of f (t) in a noiseless setting is 2K [41].
The random demodulator is one of the pioneering and
innovative attempts to extend the inherently discrete and
finite CS theory to analog signals. However, truly analog
signals, such as those we consider here, require a prohibitively large number of harmonics to approximate them well
within the discrete model. When attempting to approximate
signals like those from the multiband model, the number of
tones W is of the order of the Nyquist rate, and the number
of samples R is a multiple of KB. This, in turn, renders the
reconstruction computationally prohibitive and very sensitive

IEEE SIGNAL PROCESSING MAGAZINE

|

January 2018

|

143
Table of Contents for the Digital Edition of IEEE Signal Processing Magazine - January 2018
