Digital Signal Processing Reference
In-Depth Information
hence ensuring identifiability of the unique sparsest solution by
1
minimization. In
a nutshell, this result tells us that the more incoherent the dictionary, the higher
level of sparsity that can be recovered exactly by
1
minimization. Note, however,
that despite its simplicity and stability to compressibility and noise (Donoho et al.
2006a), the identifiabilit
y t
est of equation (8.4) leads to pessimistic sparsity bounds,
which are, at best,
O
(
√
N
) (e.g., for a Sines
Diracs dictionary). The coherence-
based sufficient recovery conditions can be refined using the Spark
1
of
+
(Donoho
et al. 2006a) or by considering not only the sparsity, but also the support and the sign
pattern of the nonzero entries of
α
(Fuchs 2004; T. Tropp 2006; Wainwright 2009). A
sufficient
1
identifiability condition based on the restricted isometry property will
be discussed in more detail in the context of compressed sensing in Chapter 11. On
the basis of topological properties of random projection of the unit
1
ball under
, Donoho (2006b) and Donoho and Tanner (2005) determine a very sh
ar
p sparsity
upper bound that is (almost) linear in
N
, which is much better than
O
(
√
N
)dictated
by equation (8.4). However, this identifiability condition does not ensure stability to
noise. The interested reader may refer to the work of Bruckstein et al. (2009) for a
comprehensive review of sparse recovery conditions by
1
minimization and greedy
algorithms.
8.1.2 The Concept of Morphological Diversity
The morphological diversity concept introduces a new data modeling framework
that allows us to have both a sparse representation and fast algorithms that exploit
the structure of the dictionary. Morphological diversity assumes that the data
x
can
be modeled as the sum of
K
components
x
k
that look
morphologically
different:
K
x
=
x
k
,
(8.5)
k
=
1
where each component
x
k
is sparse in a given dictionary
k
, which is associated with
implicit fast analysis/synthesis operators. Each
x
k
is called a
morphological compo-
nent
. For instance, by combining the Fourier and the wavelet dictionaries, we can
well represent signals that contain both stationary and localized features.
The core idea of this chapter is, then, to encode a priori knowledge on the salient
features of the sought after signal or image in a large dictionary, built by combining
several subdictionaries, each specialized in sparsifying a certain type of structure.
Owing to advances in modern computational harmonic analysis, many transforms,
such as those described in Chapters 2-5, were shown to be very effective in sparsely
representing certain kinds of signals and images. Each subdictionary can then be
chosen appropriately from these transforms.
Further reasoning behind this is borrowed from an old idea in signal processing:
the matched filter. The matched filter theorem asserts that to optimally detect the
presence of a known template in an observed noisy signal, the latter must be cor-
related with the template, and the SNR will be maximal if the template is present.
The lesson taught by this result is that to analyze effectively a signal or image, we
just have to pick up a dictionary with atoms that are morphologically similar to the
features in the signal or image.
1
The Spark of a matrix is defined as its minimal number of linearly dependent columns, not to be
confused with the rank.
