Compressed Sensing - Sparse Image and Signal Processing - page 278

analysis, and optimization. It also has implications in statistics, signal processing, in-
formation theory, and learning theory. Nonetheless, although sparsity is an essential
ingredient of the CS theory, in this chapter, we emphasize the role of CS as a sam-
pling paradigm (as testified by its name) and avoid confusion with the more general
field of sparsity-regularized inverse problems.

11.2 INCOHERENCE AND SPARSITY

CS theory asserts that one can recover certain signals and images from far fewer
measurements m than data samples N . Toward this goal, CS relies on two tenets:

1. Sparsity (compressibility; see Section 1.1.2): This reflects the fact that the infor-
mation contained in a signal can be much smaller that its effective bandwidth.
CS exploits explicitly the fact that the data are economically represented in
some dictionary (assumed to be an orthobasis for the moment).

2. Incoherence between the sensing modality and

: This extends the uncertainty
principle between time and frequency in the sense that signals that are sparse
in must be spread out in the domain in which they are acquired; that is, the

sensing vectors are as different as possible from the sparsity atoms (and vice
versa), and unlike the signal, the sensing vectors must have a dense represen-
tation in .

As explained in Chapter 1 (see, e.g., Section 1.1.2), transform coders exploit the
fact that many signals have a sparse representation on a fixed basis, meaning that
one can store only a small number of adaptively chosen transform coefficients with-
out much loss. Typically, in data acquisition systems, the full N -sample signal x is
acquired; the complete set of transform coefficients ∗ x is computed, the largest co-

efficients are encoded, and all others are discarded. The legitimate question is, then,
why spend so much effort in acquiring the whole signal if we know that most of it
will end up being thrown away?
CS is a protocol that shows that it is possible to sense and compress data si-
multaneously without going through the intermediate stage of acquiring N samples.
CS operates by directly acquiring just the important information about the signal
x without knowing it in advance. This is a distinctive property of CS entailing that
the measurement process is not adaptive, in the sense that it will not depend on the
explicit knowledge of the signal x .

11.3 THE SENSING PROTOCOL

Consider a general linear measurement process that records m < N inner products

between x and a collection of vectors ( h i ) 1 ≤ i ≤ m :

y [ i ] = h i , x , (11.1)

or, in matrix form,

y = H x = H α = F α, (11.2)