Skip to content Skip to navigation Skip to collection information

OpenStax_CNX

You are here: Home » Content » Concise Signal Models » Signal Dictionaries and Representations

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Endorsed by Endorsed (What does "Endorsed by" mean?)

This content has been endorsed by the organizations listed. Click each link for a list of all content endorsed by the organization.
  • IEEE-SPS display tagshide tags

    This collection is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing Society

    Comments:

    "A resource on sparse, compressible, and manifold signal models for signals processing and compressed sensing."

    Click the "IEEE-SPS" link to see all content they endorse.

    Click the tag icon tag icon to display tags associated with this content.

Also in these lenses

  • UniqU content

    This collection is included inLens: UniqU's lens
    By: UniqU, LLC

    Click the "UniqU content" link to see all content selected in this lens.

  • Evowl

    This collection is included inLens: Rice LMS's Lens
    By: Rice LMS

    Comments:

    "Language: en"

    Click the "Evowl" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.

Tags

(What is a tag?)

These tags come from the endorsement, affiliation, and other lenses that include this content.
 

Signal Dictionaries and Representations

Module by: Michael Wakin. E-mail the author

Summary: This collection reviews fundamental concepts underlying the use of concise models for signal processing. Topics are presented from a geometric perspective and include low-dimensional linear, sparse, and manifold-based signal models, approximation, compression, dimensionality reduction, and Compressed Sensing.

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 xRNxRN can be constructed as a linear combination of the elements (columns) of ΨΨ. We write

x = Ψ α x = Ψ α
(1)
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<AB<0<AB< 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=Ax22i=1Nx,ψi2=Ax22. The remainder of this section discusses several important dictionaries.

Figure 1: A simple, redundant frame ΨΨ containing three vectors that span R2R2.
Figure 1 (mbFrame.png)

The canonical basis

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.”

Fourier dictionaries

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.

Wavelets

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.

Scale

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 jNjN 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.

Figure 2: Dyadic partitioning of the unit square at scales j=0,1,2j=0,1,2. The partitioning induces a coarse-to-fine parent/child relationship that can be modeled using a tree structure.
Figure 2 (dyadic.png)

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, BNBN, 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.

Wavelet fundamentals

The wavelet transform offers a multiscale decomposition of a function into a nested sequence of scaling spaces V0V1VjV0V1Vj. 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.

Figure 3: Multiscale wavelet representations on the interval [0,1][0,1]. (a) Haar scaling functions spanning VjVj with j=2j=2. (b) Haar wavelet functions spanning the difference space between VjVj and Vj+1Vj+1. (c) Haar scaling functions spanning Vj+1Vj+1. (d) Two example functions belonging to the spaces (left) VjVj and (right) Vj+1Vj+1.
(a)
Figure 3(a) (wavelet spaces - 2.png)
(b)
Figure 3(b) (wavelet spaces - 2b.png)
(c)
Figure 3(c) (wavelet spaces - 2c.png)
(d)
Figure 3(d) (wavelet spaces - 2f.png)

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.

Figure 4: Cameraman test image (size 256×256256×256) for use in wavelet decomposition and approximation examples.
Figure 4 (cameraOrig.png)
Figure 5: Wavelet analysis of the Cameraman test image. (a) One-level wavelet transform, where the NN-pixel image is transformed into four sets of N/4N/4 coefficients each. The top left quadrant represents the scaling coefficients at the next coarser scale (relative to the scale of pixelization). The remaining quadrants represent the wavelet coefficients from the difference spaces, partitioned into the vertical, horizontal, and diagonal subbands. (b) Three-level wavelet transform, where the wavelet decomposition has been iterated twice more on the scaling coefficients. The multiple scales of wavelet coefficients exhibit a parent-child dependency. The largest coefficients tend to concentrate at the coarsest scales and around high-frequency features such as edges in the image.
(a)
Figure 5(a) (cameraCoeffs1.png)
(b)
Figure 5(b) (cameraCoeffs3.png)

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.

Other dictionaries

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 .

References

  1. 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.
  2. 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.
  3. 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
  4. Do, M. N. and Vetterli, M. (2005). The contourlet transform: An efficient directional multiresolution image representation. [To appear]. IEEE Trans. Image Processing.
  5. 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.
  6. 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
  7. Kovačević, J. and Chebira, A. (2006). Life Beyond Bases: The Advent of Frames. [Preprint].
  8. Kingsbury, N. (2001). Complex wavelets for shift invariant analysis and filtering of signals. Appl. Comp. Harm. Anal., 10, 234-253.
  9. Kingsbury, N. (1999, Sept.). Image processing with complex wavelets. Phil. Trans. R. Soc. Lond. A, 357,
  10. Mallat, S. (1999). A wavelet tour of signal processing. San Diego, CA, USA: Academic Press.
  11. Orchard, M. T. and Ates, H. (2003). Equiripple design of real and complex filter banks. Technical report. Rice University.
  12. Selesnick, I. W. (2002, May). The design of approximate Hilbert transform pairs of wavelet bases. IEEE Trans. Signal Processing, 50(5),
  13. 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).

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks