Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » An Introduction to Compressive Sensing » Compressive processing of manifold-modeled data

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

Compressive processing of manifold-modeled data

Module by: Marco F. Duarte. E-mail the author

Summary: This module outlines the connection between compressive sensing and random projections of manifolds.

A powerful data model for many applications is the geometric notion of a low-dimensional manifold. Data that possesses merely KK intrinsic degrees of freedom” can be assumed to lie on a KK-dimensional manifold in the high-dimensional ambient space. Once the manifold model is identified, any point on it can be represented using essentially KK pieces of information. For instance, suppose a stationary camera of resolution NN observes a truck moving down along a straight line on a highway. Then, the set of images captured by the camera forms a 1-dimensional manifold in the image space RNRN. Another example is the set of images captured by a static camera observing a cube that rotates in 3 dimensions. (Figure 1).

Figure 1: (a) A rotating cube has 3 degrees of freedom, thus giving rise to a 3-dimensional manifold in image space. (b) Illustration of a manifold FF parametrized by a K-K-dimensional vector θθ. 
(a) (b)
Figure 1(a) (squares.png)Figure 1(b) (manifold.png)

In many applications, it is beneficial to explicitly characterize the structure (alternately, identify the parameters) of the manifold formed by a set of observed signals. This is known as manifold learning and has been the subject of considerable study over the last several years; well-known manifold learning algorithms include Isomap [6], LLE [5], and Hessian eigenmaps [2]. An informal example is as follows: if a 2-dimensional manifold were to be imagined as the surface of a twisted sheet of rubber, manifold learning can be described as the process of “unraveling” the sheet and stretching it out on a 2D flat surface. Figure 2 indicates the performance of Isomap on a simple 2-dimensional dataset comprising of images of a translating disk.

Figure 2: (a) Input data consisting of 1000 images of a disk shifted in K=2K=2 dimensions, parametrized by an articulation vector (θ1,θ2)(θ1,θ2). (b) True θ1θ1 and θ2θ2 values of the sampled data. (c) Isomap embedding learned from original data in RNRN.
(a) (b) (c)
Figure 2(a) (diskexample.png)Figure 2(b) (isomapNIPStrue1.png)Figure 2(c) (isomapNIPSiso1.png)

A linear, nonadaptive manifold dimensionality reduction technique has recently been introduced that employs the technique of random projections [1]. Consider a KK-dimensional manifold MM in the ambient space RNRN and its projection onto a random subspace of dimension M=CKlog(N)M=CKlog(N); note that K<M<<NK<M<<N. The result of [1] is that the pairwise metric structure of sample points from MM is preserved with high accuracy under projection from RNRN to RMRM. This is analogous to the result for compressive sensing of sparse signals (see "The restricted isometry property"; however, the difference is that the number of projections required to preserve the ensemble structure does not depend on the sparsity of the individual images, but rather on the dimension of the underlying manifold.

This result has far reaching implications; it suggests that a wide variety of signal processing tasks can be performed directly on the random projections acquired by these devices, thus saving valuable sensing, storage and processing costs. In particular, this enables provably efficient manifold learning in the projected domain [4]. Figure 3 illustrates the performance of Isomap on the translating disk dataset under varying numbers of random projections.

Figure 3: Isomap embeddings learned from random projections of the 625 images of shifting squares. (a) 25 random projections; (b) 50 random projections; (c) 25 random projections; (d) full data.
(a) (b) (c) (d)
Figure 3(a) (isomap_tr_disk_25rp.png)Figure 3(b) (isomap_tr_disk_50rp.png)Figure 3(c) (isomap_tr_disk_100rp.png)Figure 3(d) (isomap_tr_disk_full.png)

The advantages of random projections extend even to cases where the original data is available in the ambient space RNRN. For example, consider a wireless network of cameras observing a static scene. The set of images captured by the cameras can be visualized as living on a low-dimensional manifold in the image space. To perform joint image analysis, the following steps might be executed:

  1. Collate: Each camera node transmits its respective captured image (of size NN) to a central processing unit.
  2. Preprocess: The central processor estimates the intrinsic dimensionKK of the underlying image manifold.
  3. Learn: The central processor performs a nonlinear embedding of the data points – for instance, using Isomap [6] – into a KK-dimensional Euclidean space, using the estimate of KK from the previous step.

In situations where NN is large and communication bandwidth is limited, the dominating costs will be in the first transmission/collation step. To reduce the communication expense, one may perform nonlinear image compression (such as JPEG) at each node before transmitting to the central processing. However, this requires a good deal of processing power at each sensor, and the compression would have to be undone during the learning step, thus adding to overall computational costs.

As an alternative, every camera could encode its image by computing (either directly or indirectly) a small number of random projections to communicate to the central processor [3]. These random projections are obtained by linear operations on the data, and thus are cheaply computed. Clearly, in many situations it will be less expensive to store, transmit, and process such randomly projected versions of the sensed images. The method of random projections is thus a powerful tool for ensuring the stable embedding of low-dimensional manifolds into an intermediate space of reasonable size. It is now possible to think of settings involving a huge number of low-power devices that inexpensively capture, store, and transmit a very small number of measurements of high-dimensional data.

References

  1. Baraniuk, R. and Wakin, M. (2009). Random Projections of Smooth Manifolds. Found. Comput. Math., 9(1), 51–77.
  2. Donoho, D. and Grimes, C. (2003). Hessian eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci., 100(10), 5591–5596.
  3. Davenport, M. and Hegde, C. and Duarte, M. and Baraniuk, R. (2010). Joint Manifolds for Data Fusion. IEEE Trans. Image Processing, 19(10), 2580–2594.
  4. Hegde, C. and Wakin, M. and Baraniuk, R. (2007, Dec.). Random Projections for Manifold Learning. In Proc. Adv. in Neural Processing Systems (NIPS). Vancouver, BC
  5. Roweis, S. and Saul, L. (2000). Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500), 2323–2326.
  6. Tenenbaum, J. and Silva, V.de and Landford, J. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290, 2319–2323.

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