Digital Signal Processing Reference
In-Depth Information
Olshausen 2001). In that setting, overcomplete
sparse coding
may lead to more ef-
fective (sparser) codes.
The interest in sparsity has arisen owing to the new sampling theory,
compressed
sensing
(also called
compressive sensing
or
compressive sampling
), which provides
an alternative to the well-known Shannon sampling theory (Cand es and Tao 2006;
Donoho 2006a; Cand es et al. 2006b). Compressed sensing uses the prior knowledge
that signals are sparse, whereas Shannon theory was designed for frequency band-
limited signals. By establishing a direct link between sampling and sparsity, com-
pressed sensing has had a huge impact in many scientific fields such as coding and
information theory, signal and image acquisition and processing, medical imaging,
and geophysical and astronomical data analysis. Compressed sensing acts today as
wavelets did two decades ago, linking researchers from different fields. Further con-
tributing to the success of compressed sensing is that some traditional inverse prob-
lems, such as tomographic image reconstruction, can be understood as compressed
sensing problems (Candes et al. 2006b; Lustig et al. 2007). Such ill-posed problems
need to be regularized, and many different approaches to regularization have been
proposed in the last 30 years (Tikhonov regularization, Markov random fields, to-
tal variation, wavelets, etc.). But compressed sensing gives strong theoretical sup-
port for methods that seek a sparse solution because such a solution may be (under
certain conditions) the exact one. Similar results have not been demonstrated with
any other regularization method. These reasons explain why, just a few years after
seminal compressed sensing papers were published, many hundreds of papers have
already appeared in this field (see, e.g., the compressed sensing resources Web site
http://www.compressedsensing.com).
By emphasizing so rigorously the importance of sparsity, compressed sensing has
also cast light on all work related to sparse data representation (wavelet transform,
curvelet transform, etc.). Indeed, a signal is generally not sparse in direct space (i.e.,
pixel space), but it can be very sparse after being decomposed on a specific set of
functions.
1.1.2 What Is Sparsity?
1.1.2.1 Strictly Sparse Signals/Images
A signal
x
, considered as a vector in a finite-dimensional subspace of
N
,
x
R
=
[
x
[1]
x
[
N
]], is strictly or exactly sparse if most of its entries are equal to
zero, that is, if its support
,...,
={
≤
≤
|
=
}
(
x
)
1
i
N
x
[
i
]
0
is of cardinality
k
N
.
A
k
-sparse signal is a signal for which exactly
k
samples have a nonzero value.
If a signal is not sparse, it may be
sparsified
in an appropriate transform domain.
For instance, if
x
is a sine, it is clearly not sparse, but its Fourier transform is ex-
tremely sparse (actually, 1-sparse). Another example is a piecewise constant image
away from edges of finite length that has a sparse gradient.
More generally, we can model a signal
x
as the linear combination of
T
elemen-
tary waveforms, also called
signal atoms
, such that
T
x
=
α
=
1
α
[
i
]
ϕ
i
,
(1.1)
i
=
