For a wide variety of signal processing applications (including
analysis, compression, noise removal, and so on) it is useful to
consider the representation of a signal in terms of some
dictionary [10]. In general, a dictionary
ΨΨ
is
simply a collection of elements drawn from the signal space whose
linear combinations can be used to represent or approximate
signals.
Considering, for example, signals in RNRN, we may collect
and represent the elements of the dictionary ΨΨ as an N×ZN×Z matrix, which we also denote as ΨΨ. From
this dictionary, a signal x∈RNx∈RN can be constructed as
a linear combination of the elements (columns) of ΨΨ. We write
for some
α∈RZα∈RZ. (For much of our notation
in this section, we concentrate on signals in
RNRN, though
the basic concepts translate to other vector spaces.)
Dictionaries appear in a variety of settings. The most common may
be the basis, in which case ΨΨ has exactly NN linearly
independent columns, and each signal xx has a unique set of
expansion coefficients α=Ψ-1xα=Ψ-1x. The orthonormal
basis (where the columns are normalized and orthogonal) is also of
particular interest, as the unique set of expansion coefficients
α=Ψ-1x=ΨTxα=Ψ-1x=ΨTx can be obtained as the
inner products of xx against the columns of ΨΨ. That is,
α(i)=x,ψi,i=1,2,⋯,Nα(i)=x,ψi,i=1,2,⋯,N, which gives us
the expansion
x
=
∑
i
=
1
N
x
,
ψ
i
ψ
i
.
x
=
∑
i
=
1
N
x
,
ψ
i
ψ
i
.
(2)We also have that x22=∑i=1Nx,ψi2x22=∑i=1Nx,ψi2.
Frames are another special type of dictionary [7]. A
dictionary ΨΨ is a frame if there exist numbers AA and BB,
0<A≤B<∞0<A≤B<∞ such that, for any signal xx
A
x
2
2
≤
∑
z
x
,
ψ
z
2
≤
B
x
2
2
.
A
x
2
2
≤
∑
z
x
,
ψ
z
2
≤
B
x
2
2
.
(3)
The elements of a frame may be linearly dependent in general (see
Figure 1), and so there may exist many ways to
express a particular signal among the dictionary elements.
However, frames do have a useful analysis/synthesis duality: for
any frame
ΨΨ there exists a dual frame
Ψ˜Ψ˜ such
that
x
=
∑
z
x
,
ψ
z
ψ
˜
z
=
∑
z
x
,
ψ
˜
z
ψ
z
.
x
=
∑
z
x
,
ψ
z
ψ
˜
z
=
∑
z
x
,
ψ
˜
z
ψ
z
.
(4)
In the case where the frame vectors are represented as columns of the
NN x
ZZ matrix
ΨΨ, the matrix
Ψ˜Ψ˜ containing the dual frame elements is simply the transpose of the pseudoinverse of
ΨΨ.
A frame is called
tight if the frame bounds
AA and
BB are
equal. Tight frames have the special properties of (i) being their
own dual frames (after a rescaling by
1/A1/A) and (ii) preserving
norms, i.e.,
∑i=1Nx,ψi2=Ax22∑i=1Nx,ψi2=Ax22.
The remainder of this section discusses several important
dictionaries.
The standard basis for representing a signal is the canonical (or
“spike”) basis. In RNRN, this corresponds to a
dictionary Ψ=INΨ=IN (the N×NN×N identity matrix).
When expressed in the canonical basis, signals are often said to
be in the “time domain.”
The frequency domain provides one alternative representation to
the time domain. The Fourier series and discrete Fourier transform
are obtained by letting ΨΨ contain complex exponentials and
allowing the expansion coefficients αα to be complex as
well. (Such a dictionary can be used to represent real or complex
signals.) A related “harmonic” transform to express signals in
RNRN is the discrete cosine transform (DCT), in which
ΨΨ contains real-valued, approximately sinusoidal functions
and the coefficients αα are real-valued as well.
Closely related to the Fourier transform, wavelets provide a
framework for localized harmonic analysis of a
signal [10]. Elements of the discrete wavelet dictionary
are local, oscillatory functions concentrated approximately on
dyadic supports and appear at a discrete collection of scales,
locations, and (if the signal dimension D>1D>1)
orientations.
In wavelet analysis and other settings, we will frequently refer to a particular scale of analysis
for a signal. Consider, for example, continuous-time functions ff defined over
the domain D=[0,1]DD=[0,1]D. A dyadic
hypercube Xj⊆[0,1]DXj⊆[0,1]D at scale j∈Nj∈N is a domain that satisfies
X
j
=
[
β
1
2
-
j
,
(
β
1
+
1
)
2
-
j
]
×
⋯
×
[
β
D
2
-
j
,
(
β
D
+
1
)
2
-
j
]
X
j
=
[
β
1
2
-
j
,
(
β
1
+
1
)
2
-
j
]
×
⋯
×
[
β
D
2
-
j
,
(
β
D
+
1
)
2
-
j
]
(5)
with
β1,β2,⋯,βD∈{0,1,⋯,2j-1}β1,β2,⋯,βD∈{0,1,⋯,2j-1}. We call
XjXj a
dyadic interval when
D=1D=1 or a
dyadic square when
D=2D=2 (see
Figure 2). Note that
XjXj has sidelength
2-j2-j.
For discrete-time functions the notion of scale is similar. We can
imagine, for example, a “voxelization” of the domain
[0,1]D[0,1]D (“pixelization” when D=2D=2), where each
voxel has sidelength 2-B2-B, B∈NB∈N, and it takes
2BD2BD voxels to fill [0,1]D[0,1]D. The relevant scales
of analysis for such a signal would simply be j=0,1,⋯,Bj=0,1,⋯,B,
and each dyadic hypercube XjXj would refer to a collection of
voxels.
The wavelet transform offers a multiscale decomposition of a
function into a nested sequence of scaling spaces V0⊂V1⊂⋯⊂Vj⊂⋯V0⊂V1⊂⋯⊂Vj⊂⋯. Each scaling space VjVj is
spanned by a discrete collection of dyadic translations of a
lowpass scaling function ϕjϕj, and the difference between adjacent
scaling spaces VjVj and Vj+1Vj+1 is spanned by a discrete collection of dyadic translations of a
bandpass wavelet function ψjψj. Figure 3 shows an example of this multiscale organization in the case of the Haar wavelet dictionary. Each wavelet function at
scale jj is concentrated approximately on some dyadic hypercube
XjXj, and between scales, both the wavelets and scaling functions
are “self-similar,” differing only by rescaling and dyadic
dilation. When D>1D>1, the difference spaces are
partitioned into 2D-12D-1 distinct orientations (when
D=2D=2 these correspond to vertical, horizontal, and
diagonal directions). The wavelet transform can be truncated at
any scale jj. We then let the basis ΨΨ consist of all scaling
functions at scale jj plus all wavelets at scales jj and finer.
Wavelets are essentially bandpass functions that detect abrupt
changes in a signal. The scale of a wavelet, which controls its
support both in time and in frequency, also controls its
sensitivity to changes in the signal. This is made more precise by
considering the wavelet analysis of smooth signals. Wavelet are
often characterized by their number of vanishing moments; a
wavelet basis function is said to have HH vanishing
moments if it is orthogonal to (its inner product is zero against)
any HH-degree polynomial. Sparse (Nonlinear) models
discusses further the wavelet analysis of smooth and piecewise
smooth signals.
The dyadic organization of the wavelet transform lends itself to a
multiscale, tree-structured organization of the wavelet
coefficients. Each “parent” function, concentrated on a dyadic
hypercube XjXj of sidelength 2-j2-j, has 2D2D
“children” whose supports are concentrated on the dyadic
subdivisions of XjXj. This relationship can be represented in a
top-down tree structure, as demonstrated in Figure 2. Because the parent and children share a
location, they will presumably measure related phenomena about the
signal, and so in general, any patterns in their wavelet
coefficients tend to be reflected in the connectivity of the tree
structure. Figure 4 and Figure 5 show an example of the wavelet transform applied to the Cameraman test image; since the dimension D=2D=2, each scale is partitioned into vertical, horizontal, and diagonal wavelet analysis, and each parent coefficient has 2D=42D=4 children.
In addition to their ease of modeling, wavelets are
computationally attractive for signal processing; using a filter
bank, the wavelet transform of an NN-voxel signal can be
computed in just O(N)O(N) operations.
A wide variety of other dictionaries have been proposed in signal
processing and harmonic analysis. As one example, complex-valued
wavelet transforms have proven useful for image analysis and
modeling [9], [8], [12], [5], [13], [11], [6],
thanks to a phase component that captures location information at
each scale. Just a few of the other harmonic dictionaries popular
in image processing include wavelet packets [10], Gabor
atoms [10], curvelets [2], [1], and
contourlets [3], [4], all of which involve various
space-frequency partitions. We mention additional dictionaries in
Compression .
-
Candès, E. and Donoho, D. L. (2004). New tight frames of curvelets and optimal representations of objects with piecewise singularities. Comm. on Pure and Applied Math., 57, 219–266.
-
Candès, E. J. and Donoho, D. L. (1999). Curvelets — A suprisingly effective nonadaptive representation for objects with edges. In Cohen, A. and Rabut, C. and Schumaker, L. L. (Eds.), Curve and Surface Fitting. Vanderbilt University Press.
-
Do, M. N. and Vetterli, M. (2002, Oct.). Contourlets: A directional multiresolution image representation. In Proc. IEEE Int. Conf. Image Proc. (ICIP). Rochester, New York
-
Do, M. N. and Vetterli, M. (2005). The contourlet transform: An efficient directional multiresolution image representation. [To appear]. IEEE Trans. Image Processing.
-
Fernandes, F. C. A. and van Spaendonck, R. L. C. and Burrus, C. S. (2003, July). A New Framework for Complex Wavelet Transforms. IEEE Trans. Signal Processing.
-
Fernandes, F. C. A. and Wakin, M. B. and Baraniuk, R. G. (2004, May). Non-Redundant, Linear-Phase, Semi-Orthogonal, Directional Complex Wavelets. In Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP). Montreal, Quebec, Canada
-
Kovačević, J. and Chebira, A. (2006). Life Beyond Bases: The Advent of Frames. [Preprint].
-
Kingsbury, N. (2001). Complex wavelets for shift invariant analysis and filtering of signals. Appl. Comp. Harm. Anal., 10, 234-253.
-
Kingsbury, N. (1999, Sept.). Image processing with complex wavelets. Phil. Trans. R. Soc. Lond. A, 357,
-
Mallat, S. (1999). A wavelet tour of signal processing. San Diego, CA, USA: Academic Press.
-
Orchard, M. T. and Ates, H. (2003). Equiripple design of real and complex filter banks. Technical report. Rice University.
-
Selesnick, I. W. (2002, May). The design of approximate Hilbert transform pairs of wavelet bases. IEEE Trans. Signal Processing, 50(5),
-
van Spaendonck, R. and Blu, T. and Baraniuk, R. and Vetterli, M. (2003). Orthogonal Hilbert Transform Filter Banks and Wavelets. In Proc. Int. Conf. Acoustics, Speech, Signal Processing (ICASSP).
(What does "Endorsed by" mean?)
"A resource on sparse, compressible, and manifold signal models for signals processing and compressed sensing."