Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Concise Signal Models » Low-Dimensional Signal Models

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.
 

Low-Dimensional Signal Models

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.

We now survey some common and important models in signal processing, each of which involves some notion of conciseness to the signal structure. We see in each case that this conciseness gives rise to a low-dimensional geometry within the ambient signal space.

Linear models

Some of the simplest models in signal processing correspond to linear subspaces of the ambient signal space. Bandlimited signals are one such example. Supposing, for example, that a 2π2π-periodic signal ff has Fourier transform F(ω)=0F(ω)=0 for |ω|>B|ω|>B, the Shannon/Nyquist sampling theorem [12] states that such signals can be reconstructed from 2B2B samples. Because the space of BB-bandlimited signals is closed under addition and scalar multiplication, it follows that the set of such signals forms a 2B2B-dimensional linear subspace of L2([0,2π))L2([0,2π)).

Linear signal models also appear in cases where a model dictates a linear constraint on a signal. Considering a discrete length-NN signal xx, for example, such a constraint can be written in matrix form as

A x = 0 A x = 0
(1)
for some M×NM×N matrix AA. Signals obeying such a model are constrained to live in N(A)N(A) (again, obviously, a linear subspace of RNRN).

A very similar class of models concerns signals living in an affine space, which can be represented for a discrete signal using

A x = y . A x = y .
(2)
The class of such xx lives in a shifted nullspace x^+N(A)x^+N(A), where x^x^ is any solution to the equation Ax^=yAx^=y.

Revisiting the dictionary setting (see Signal Dictionaries and Representations), one last important linear model arises in cases where we select KK specific elements from the dictionary ΨΨ and then construct signals using linear combinations of only these KK elements; in this case the set of possible signals forms a KK-dimensional hyperplane in the ambient signal space (see Figure 1(a)).

Figure 1: Simple models for signals in R2R2. (a) The linear space spanned by one element of the dictionary ΨΨ. The bold vectors denote the elements of the dictionary, while the dashed line (plus the corresponding dictionary element) denotes the subspace spanned by that dictionary element. (b) The nonlinear set of 1-sparse signals that can be built using ΨΨ. (c) A manifold MM.
(a)
Figure 1(a) (mbFrameLA.png)
(b)
Figure 1(b) (mbFrameNLA.png)
(c)
Figure 1(c) (mbFrameManifold.png)

For example, we may construct low-frequency signals using combinations of only the lowest frequency sinusoids from the Fourier dictionary. Similar subsets may be chosen from the wavelet dictionary; in particular, one may choose only elements that span a particular scaling space VjVj. As we have mentioned previously, harmonic dictionaries such as sinusoids and wavelets are well-suited to representing smooth1 signals. This can be seen in the decay of their transform coefficients. For example, we can relate the smoothness of a continuous 1-D function ff to the decay of its Fourier coefficients F(ω)F(ω); in particular, if |F(ω)|(1+|ω|H)dω<|F(ω)|(1+|ω|H)dω<, then fCHfCH [12]. In order to satisfy |F(ω)|(1+|ω|H)dω<|F(ω)|(1+|ω|H)dω<, a signal must have a sufficiently fast decay of the Fourier transform coefficients |F(ω)||F(ω)| as ωω grows. Wavelet coefficients exhibit a similar decay for smooth signals: supposing fCHfCH and the wavelet basis function has at least HH vanishing moments, then as the scale jj, the magnitudes of the wavelet coefficients decay as 2-j(H+1/2)2-j(H+1/2) [12]. (Recall that fCHfCH implies ff is well-approximated by a polynomial, and so due the vanishing moments this polynomial will have zero contribution to the wavelet coefficients.)

Indeed, these results suggest that the largest Fourier or wavelet coefficients of smooth signals tend to concentrate at the coarsest scales (lowest-frequencies). In Linear Approximation from Approximation , we see that linear approximations formed from just the lowest frequency elements of the Fourier or wavelet dictionaries (i.e., the truncation of the Fourier or wavelet representation to only the lowest frequency terms) provide very accurate approximations to smooth signals. Put differently, smooth signals live near the subspace spanned by just the lowest frequency Fourier or wavelet basis functions.

Sparse (nonlinear) models

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 real-world 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 “KK-sparse”) if all but KK entries of αα are zero.

Some examples of real-world 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 3-D 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 KK-sparse 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 KK-sparse signals from the dictionary ΨΨ forms not a hyperplane but rather a union of KK-dimensional 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 pp 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, KK-sparse 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 tRtR 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 2-j/22-j/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 signal-dependent. (For modeling purposes, these significant coefficients will persist through scale down the parent-child 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 1-D signals is not hampered by the addition of a finite number of discontinuities.

Manifold models

Manifold models generalize the conciseness of sparsity-based signal models. In particular, in many situations where a signal is believed to have a concise description or “few degrees of freedom,” the result is that the signal will live on or near a particular submanifold of the ambient signal space.

Parametric models

We begin with an abstract motivation for the manifold perspective. Consider a signal ff (such as a natural image), and suppose that we can identify some single 1-D piece of information about that signal that could be variable; that is, other signals might rightly be called “similar” to ff if they differ only in this piece of information. (For example, this 1-D parameter could denote the distance from some object in an image to the camera.) We let θθ denote the variable parameter and write the signal as fθfθ to denote its dependence on θθ. In a sense, θθ is a single “degree of freedom” driving the generation of the signal fθfθ under this simple model. We let ΘΘ denote the set of possible values of the parameter θθ. If the mapping between θθ and fθfθ is well-behaved, then the collection of signals {fθ:θΘ}{fθ:θΘ} forms a 1-D path in the ambient signal space.

More generally, when a signal has KK degrees of freedom, we may model it as depending on some parameter θθ that is chosen from a KK-dimensional manifold ΘΘ. (The parameter space ΘΘ could be, for example, a subset of RKRK, or it could be a more general manifold such as SO(3).) We again let fθfθ denote the signal corresponding to a particular choice of θθ, and we let F={fθ:θΘ}F={fθ:θΘ}. Assuming the mapping ff is continuous and injective over ΘΘ (and its inverse is continuous), then by virtue of the manifold structure of ΘΘ, its image FF will correspond to a KK-dimensional manifold embedded in the ambient signal space (see Figure 1(c)).

These types of parametric models arise in a number of scenarios in signal processing. Examples include: signals of unknown translation, sinusoids of unknown frequency (across a continuum of possibilities), linear radar chirps described by a starting and ending time and frequency, tomographic or light field images with articulated camera positions, robotic systems with few physical degrees of freedom, dynamical systems with low-dimensional attractors [2], [3], and so on.

In general, parametric signals manifolds are nonlinear (by which we mean non-affine as well); this can again be seen by considering the sum of two signals fθ0+fθ1fθ0+fθ1. In many interesting situations, signal manifolds are non-differentiable as well.

Nonparametric models

Manifolds have also been used to model signals for which there is no known parametric model. Examples include images of faces and handwritten digits [16], [4], which have been found empirically to cluster near low-dimensional manifolds. Intuitively, because of the configurations of human joints and muscles, it may be conceivable that there are relatively “few” degrees of freedom driving the appearance of a human face or the style of handwriting; however, this inclination is difficult or impossible to make precise. Nonetheless, certain applications in face and handwriting recognition have benefitted from algorithms designed to discover and exploit the nonlinear manifold-like structure of signal collections. Manifold Learning from Dimensionality Reduction discusses such methods for learning parametrizations and other information from data living along manifolds.

Much more generally, one may consider, for example, the set of all natural images. Clearly, this set has small volume with respect to the ambient signal space — generating an image randomly pixel-by-pixel will almost certainly produce an unnatural noise-like image. Again, it is conceivable that, at least locally, this set may have a low-dimensional manifold-like structure: from a given image, one may be able to identify only a limited number of meaningful changes that could be performed while still preserving the natural look to the image. Arguably, most work in signal modeling could be interpreted in some way as a search for this overall structure.

Footnotes

  1. Lipschitz smoothness We say a continuous-time function of DD variables has smoothness of order H>0H>0, where H=r+νH=r+ν, rr is an integer, and ν(0,1]ν(0,1], if the following criteria are met [12], [8]:
    • All iterated partial derivatives with respect to the DD directions up to order rr exist and are continuous.
    • All such partial derivatives of order rr satisfy a Lipschitz condition of order νν (also known as a Hölder condition).(A function dLip(ν)dLip(ν) if |d(t1+t2)-d(t1)|Ct2ν|d(t1+t2)-d(t1)|Ct2ν for all DD-dimensional vectors t1,t2t1,t2.)
    We will sometimes consider the space of smooth functions whose partial derivatives up to order rr are bounded by some constant ΩΩ. With somewhat nonstandard notation, we denote the space of such bounded functions with bounded partial derivatives by CHCH, where this notation carries an implicit dependence on ΩΩ. Observe that r=H-1r=H-1, where ·· denotes rounding up. Also, when HH is an integer CHCH includes as a subset the space traditionally denoted by the notation “CHCH” (the class of functions that have H=r+1H=r+1 continuous partial derivatives).

References

  1. Baraniuk, R. G. and Jones, D. L. (1993). Shear Madness: New Orthogonal Bases and Frames Using Chirp Functions. IEEE Trans. Signal Proc., 41(12), 3543-3549.
  2. Broomhead, D. S. and Kirby, M. (2000). A New Approach for Dimensionality Reduction: Theory and Algorithms. SIAM J. of Applied Mathematics, 60(6),
  3. Broomhead, D. S. and Kirby, M. J. (2001). The Whitney Reduction Network: A method for computing autoassociative graphs. Neural Computation, 13, 2595-2616.
  4. Belkin, M. and Niyogi, P. (2003, June). Laplacian Eigenmaps for Dimensionality Reduction and Data Representation. Neural Computation, 15(6),
  5. 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.
  6. 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.
  7. DeVore, R. A. (Spring 2006). Lecture notes on Compressed Sensing. Rice University ELEC 631 Course Notes.
  8. DeVore, R. A. and Jawerth, B. and Lucier, B. J. (1992, Mar.). Image Compression Through Wavelet Transform Coding. IEEE Trans. Inform. Theory, 38(2), 719-746.
  9. Donoho, D. L. (1993, Dec.). Unconditional bases are optimal bases for data compression and for statistical estimation. Appl. Comput. Harmon. Anal., 1(1), 100-115.
  10. Donoho, D. L. (1995, May). Denoising by soft-thresholding. IEEE Trans. Inform. Theory, 41(3), 613-627.
  11. LoPresto, S. and Ramchandran, K. and Orchard, M. T. (1997, March). Image coding based on mixture modeling of wavelet coefficients and a fast estimation-quantization framework. In Proc. Data Compression Conf. (pp. 221-230). Snowbird, Utah
  12. Mallat, S. (1999). A wavelet tour of signal processing. San Diego, CA, USA: Academic Press.
  13. Mehrseresht, N. and Taubman, D. (2004). An efficient content-adaptive motion compensated 3D-DWT with enhanced spatial and temporal scalability. [Preprint].
  14. Shapiro, J. (1993, Dec.). Embedded image coding using zerotrees of wavelet coefficients. IEEE Trans. Signal Processing, 41(12), 3445-3462.
  15. Selesnick, I. W. and Li, K. L. (2003). Video denoising using 2D and 3D dual-tree complex wavelet transforms. In Proc. SPIE Wavelet Applications Signal Image Processing X.
  16. Turk, M. and Pentland, A. (1991). Eigenfaces for Recognition. J. Cognitive Neuroscience, 3(1),
  17. Xiong, Z. and Ramchandran, K. and Orchard, M. T. (1997). Space-frequency Quantization for Wavelet Image Coding. IEEE Trans. Image Processing, 6(5), 677-693.

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