Sparse signal models can be viewed as a generalization of linear
models. The notion of sparsity comes from the fact that, by the
proper choice of dictionary ΨΨ, many realworld signals x=Ψαx=Ψα have coefficient vectors αα containing few
large entries, but across different signals the locations (indices
in αα) of the large entries may change. We say a signal is
strictly sparse (or “KKsparse”) if all but KK
entries of αα are zero.
Some examples of realworld signals for which sparse models have
been proposed include neural spike trains (in time), music and
other audio recordings (in time and frequency), natural images (in
the wavelet or curvelet
dictionaries [12], [8], [14], [11], [17], [10], [6], [5]),
video sequences (in a 3D wavelet
dictionary [13], [15]), and sonar or radar pulses
(in a chirplet dictionary [1]). In each of these
cases, the relevant information in a sparse representation of a
signal is encoded in both the locations (indices) of the
significant coefficients and the values to which they are
assigned. This type of uncertainty is an appropriate model for
many natural signals with punctuated phenomena.
Sparsity is a nonlinear model. In particular, let
ΣKΣK denote the set of all KKsparse
signals for a given dictionary. It is easy to see that the set
ΣKΣK is not closed under addition. (In fact,
ΣK+ΣK=Σ2KΣK+ΣK=Σ2K.) From
a geometric perspective, the set of all KKsparse signals
from the dictionary ΨΨ forms not a hyperplane but rather a
union of KKdimensional hyperplanes, each spanned by
KK vectors of ΨΨ (see
Figure 1(b)). For a dictionary ΨΨ with
ZZ entries, there are ZKZK such
hyperplanes. (The geometry of sparse signal collections has also
been described in terms of orthosymmetric sets;
see [9].)
Signals that are not strictly sparse but rather have a few
“large” and many “small” coefficients are known as compressible signals. The notion of compressibility can be made
more precise by considering the rate at which the sorted
magnitudes of the coefficients αα decay, and this decay rate
can in turn be related to the ℓpℓp norm of the coefficient
vector αα. Letting α˜α˜ denote a
rearrangement of the vector αα with the coefficients ordered
in terms of decreasing magnitude, then the reordered coefficients
satisfy [7]
α
˜
k
≤
∥
α
∥
ℓ
p
k

1
/
p
.
α
˜
k
≤
∥
α
∥
ℓ
p
k

1
/
p
.
(3)
As we discuss in
Nonlinear Approximation from Approximation, these decay rates play an
important role in
nonlinear approximation, where adaptive,
KKsparse representations from the dictionary are used to
approximate a signal.
We recall from Section 1 that for a smooth
signal ff, the largest Fourier and wavelet coefficients tend to
cluster at coarse scales (low frequencies). Suppose, however, that
the function ff is piecewise smooth; i.e., it is
CHCH at every point t∈Rt∈R except for one
point t0t0, at which it is discontinuous. Naturally, this
phenomenon will be reflected in the transform coefficients.
In the Fourier domain, this discontinuity will have a global
effect, as the overall smoothness of the function ff has been
reduced dramatically from HH to 0.
Wavelet coefficients, however, depend only on local signal
properties, and so the wavelet basis functions whose supports do
not include t0t0 will be unaffected by the discontinuity.
Coefficients surrounding the singularity will decay only as
2j/22j/2, but there are relatively few such coefficients.
Indeed, at each scale there are only O(1)O(1) wavelets that include
t0t0 in their supports, but these locations are highly
signaldependent. (For modeling purposes, these significant
coefficients will persist through scale down the parentchild tree
structure.) After reordering by magnitude, the wavelet
coefficients of piecewise smooth signals will have the same
general decay rate as those of smooth signals. In
Nonlinear Approximation from Approximation, we see that the quality of nonlinear
approximations offered by wavelets for smooth 1D signals is not
hampered by the addition of a finite number of discontinuities.
"A resource on sparse, compressible, and manifold signal models for signals processing and compressed sensing."