Skip to content Skip to navigation

Connexions

You are here: Home » Content » Dimensionality Reduction

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 module is included inLens: IEEE Signal Processing Society Lens
    By: IEEE Signal Processing SocietyAs a part of collection: "Concise Signal Models"

    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 module is included inLens: UniqU's lens
    By: UniqU, LLCAs a part of collection: "Concise Signal Models"

    Click the "UniqU content" 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.
 

Dimensionality Reduction

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.

Recent years have seen a proliferation of novel techniques for what can loosely be termed “dimensionality reduction.” Like the tasks of approximation and compression discussed above, these methods involve some aspect in which low-dimensional information is extracted about a signal or collection of signals in some high-dimensional ambient space. Unlike the tasks of approximation and compression, however, the goal of these methods is not always to maintain a faithful representation of each signal. Instead, the purpose may be to preserve some critical relationships among elements of a data set or to discover information about a manifold on which the data lives.

In this section, we review two general methods for dimensionality reduction. Section 1 begins with a brief overview of techniques for manifold learning. Section 2 then discusses the Johnson-Lindenstrauss (JL) lemma, which concerns the isometric embedding of a cloud points as it is projected to a lower-dimensional space. Though at first glance the JL lemma does not pertain to any of the low-dimensional signal models we have previously discussed, we later see in Connections with dimensionality reduction that the JL lemma plays a critical role in the core theory of CS, and we also employ the JL lemma in developing a theory for isometric embeddings of manifolds.

Manifold learning

Several techniques have been proposed for solving a problem known as manifold learning in which certain properties of a manifold are inferred from a discrete collection of points sampled from that manifold. A typical manifold learning setup is as follows: an algorithm is presented with a set of PP points sampled from a KK-dimensional submanifold of RNRN. The goal of the algorithm is to produce an mapping of these PP points into some lower dimension RMRM (ideally, M=KM=K) while preserving some characteristic property of the manifold. Example algorithms include ISOMAP [15], Hessian Eigenmaps (HLLE) [9], and Maximum Variance Unfolding (MVU) [16], which attempt to learn isometric embeddings of the manifold (thus preserving pairwise geodesic distances in RMRM); Locally Linear Embedding (LLE) [14], which attempts to preserve local linear neighborhood structures among the embedded points; Local Tangent Space Alignment (LTSA) [17], which attempts to preserve local coordinates in each tangent space; and a method for charting a manifold [5] that attempts to preserve local neighborhood structures.

The internal mechanics of these algorithms differs depending on the objective criterion to be preserved, but as an example, the ISOMAP algorithm operates by first estimating the geodesic distance between each pair of points on the manifold (by approximating geodesic distance as the sum of Euclidean distances between pairs of the available sample points). After the P×PP×P matrix of pairwise geodesic distances is constructed, a technique known as multidimensional scaling uses an eigendecomposition of the distance matrix to determine the proper MM-dimensional embedding space. An example of using ISOMAP to learn a 22-dimensional manifold is shown in Figure 1.

Figure 1: Manifold learning demonstration. (a) As input to the manifold learning algorithm, 10001000 images of size 64×6464×64 are created, where each image consists of a white disk translated to a random position (θ1, θ2)(θ1, θ2). It follows that the images represent a sampling of 10001000 points from a 22-dimensional submanifold of R4096R4096. (b) Scatter plot of the true values for the (θ1, θ2)(θ1, θ2) positions. For visibility in each plot, the color of each point indicates the true θ1θ1 value. (c) ISOMAP embedding learned from original data points in R4096R4096. From the low-dimensional embedding coordinates we can infer the relative positions of the original high-dimensional images. (d) ISOMAP embedding learned from a random projection of the data set to RMRM, where M=15M=15.
(a) (b) (c) (d)
Figure 1(a) (diskexample.png)Figure 1(b) (isomapCNXtrue1.png)Figure 1(c) (isomapCNXiso1.png)Figure 1(d) (isomapCNXiso1proj.png)

These algorithms can be useful for learning the dimension and parametrizations of manifolds, for sorting data, for visualization and navigation through the data, and as preprocessing to make further analysis more tractable; common demonstrations include analysis of face images and classification of and handwritten digits. A related technique, the Whitney Reduction Network [2], [3], seeks a linear mapping to RMRM that preserves ambient pairwise distances on the manifold and is particularly useful for processing the output of dynamical systems having low-dimensional attractors.

Other algorithms have been proposed for characterizing manifolds from sampled data without constructing an explicit embedding in RMRM. The Geodesic Minimal Spanning Tree (GMST) [6] models the data as random samples from the manifold and estimates the corresponding entropy and dimensionality. Another technique [13] has been proposed for using random samples of a manifold to estimate its homology (via the Betti numbers, which essentially characterize its dimension, number of connected components, etc.). Persistence Barcodes [8] are a related technique that involves constructing a type of signature for a manifold (or simply a shape) that uses tangent complexes to detect and characterize local edges and corners.

Additional algorithms have been proposed for constructing meaningful functions on the point samples in RNRN. To solve a semi-supervised learning problem, a method called Laplacian Eigenmaps [4] has been proposed that involves forming an adjacency graph for the data in RNRN, computing eigenfunctions of the Laplacian operator on the graph (which form a basis for L2L2 on the graph), and using these functions to train a classifier on the data. The resulting classifiers have been used for handwritten digit recognition, document classification, and phoneme classification. (The MM smoothest eigenfunctions can also be used to embed the manifold in MM, similar to the approaches described above.) A related method called Diffusion Wavelets [7] uses powers of the diffusion operator to model scale on the manifold, then constructs wavelets to capture local behavior at each scale. The result is a wavelet transform adapted not to geodesic distance but to diffusion distance, which measures (roughly) the number of paths connecting two points.

The Johnson-Lindenstrauss lemma

Fundamentals

As with the above techniques in manifold learning, the Johnson-Lindenstrauss (JL) lemma [12], [1], [10], [11] provides a method for dimensionality reduction of a set of data in RNRN. Unlike manifold-based methods, however, the JL lemma can be used for any arbitrary set QQ of points in RNRN; the data set is not assumed to have any a priori structure.

Despite the apparent lack of structure in an arbitrary point cloud data set, the JL lemma suggests that there does exist a method for dimensionality reduction of that data set that can preserve key information while mapping the data to a lower-dimensional space RMRM. In particular, the original formulation of the JL lemma [12] states that there exists a Lipschitz mapping Φ:RN↦RMΦ:RN↦RM with M=O(log(#Q))M=O(log(#Q)) such that all pairwise distances between points in QQ are approximately preserved. This fact is useful for solving problems such as Approximate Nearest Neighbor [11], in which one desires the nearest point in QQ to some query point y∈RNy∈RN (but a solution not much further than the optimal point is also acceptable). Such problems can be solved significantly more quickly in RMRM than in RNRN.

Recent reformulations of the JL lemma propose random linear operators that, with high probability, will ensure a near isometric embedding. These typically build on concentration of measure results such as the following.

Lemma 1

[1], [10] Let x∈RNx∈RN, fix 0<ϵ<10<ϵ<1, and let ΦΦ be a matrix constructed in one of the following two manners:

  1. ΦΦ is a random M×NM×N matrix with i.i.d. N(0,σ2)N(0,σ2) entries, where σ2=1/Nσ2=1/N, or
  2. ΦΦ is random orthoprojector from RNRN to RMRM.

Then with probability exceeding

1 - 2 exp - M ( ϵ 2 / 2 - ϵ 3 / 3 ) 2 , 1 - 2 exp - M ( ϵ 2 / 2 - ϵ 3 / 3 ) 2 ,
(1)

the following holds:

( 1 - ϵ ) M N ≤ Φ x 2 x 2 ≤ ( 1 + ϵ ) M N . ( 1 - ϵ ) M N ≤ Φ x 2 x 2 ≤ ( 1 + ϵ ) M N .
(2)

The random orthoprojector referred to above is clearly related to the first case (simple matrix multiplication by a Gaussian ΦΦ) but subtly different; one could think of constructing a random Gaussian ΦΦ, then using Gram-Schmidt to orthonormalize the rows before multiplying xx. We note also that simple rescaling of ΦΦ can be used to eliminate the MNMN in Equation 2; however we prefer this formulation for later reference.

By using the union bound over all #Q2#Q2 pairs of distinct points in QQ, Lemma "The Johnson-Lindenstrauss lemma" can be used to prove a randomized version of the Johnson-Lindenstrauss lemma.

Lemma 2: Johnson-Lindenstrauss

Let QQ be a finite collection of points in RNRN. Fix 0<ϵ<10<ϵ<1 and β>0β>0. Set

M ≥ 4 + 2 β ϵ 2 / 2 - ϵ 3 / 3 ln ( # Q ) . M ≥ 4 + 2 β ϵ 2 / 2 - ϵ 3 / 3 ln ( # Q ) .
(3)

Let ΦΦ be a matrix constructed in one of the following two manners:

  1. ΦΦ is a random M×NM×N matrix with i.i.d. N(0,σ2)N(0,σ2) entries, where σ2=1/Nσ2=1/N, or
  2. ΦΦ is random orthoprojector from RNRN to RMRM.

Then with probability exceeding 1-(#Q)-β1-(#Q)-β, the following statement holds: for every x,y∈Qx,y∈Q,

( 1 - ϵ ) M N ≤ Φ x - Φ y 2 x - y 2 ≤ ( 1 + ϵ ) M N . ( 1 - ϵ ) M N ≤ Φ x - Φ y 2 x - y 2 ≤ ( 1 + ϵ ) M N .
(4)

Indeed, [1] establishes that both Lemma 1 and Lemma 2 also hold when the elements of ΦΦ are chosen i.i.d. from a random Rademacher distribution (±σ±σ with equal probability 1/21/2) or from a similar ternary distribution (±3σ±3σ with equal probability 1/61/6; 0 with probability 2/32/3). These can further improve the computational benefits of the JL lemma.

Connections with compressed sensing

In the following module on Compressed Sensing we will discuss further topics in dimensionality reduction that relate to the JL lemma. In particular, as discussed in Connections with dimensionality reduction, the core mechanics of Compressed Sensing can be interpreted in terms of a stable embedding that arises for the family of KK-sparse signals when observed with random measurements, and this stable embedding can be proved using the JL lemma. Furthermore, as discussed in Stable embeddings of manifolds, one can ensure a stable embedding of families of signals obeying manifold models under a sufficient number of random projections, with the theory again following from the JL lemma.

References

  1. Achlioptas, D. (2001). Database-friendly random projections. In Proc. Symp. Principles of Database Systems.
  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. Brand, M. (2002). Charting a manifold. In Proc. Neural Inform. Processing Systems - NIPS.
  6. Costa, J. A. and Hero, A. O. (2004, August). Geodesic entropic graphs for dimension and entropy estimation in manifold learning. IEEE Trans. Signal Processing, 52(8),
  7. Coifman, R. R. and Maggioni, M. (2005). Diffusion Wavelets. [To appear]. Appl. Comput. Harmon. Anal..
  8. Carlsson, G. and Zomorodian, A. and Collins, A. and Guibas, L. Persistence Barcodes for Shapes. [To appear]. Int. J. of Shape Modeling.
  9. Donoho, D. L. and Grimes, C. E. (2003, May). Hessian Eigenmaps: Locally linear embedding techniques for high-dimensional data. Proc. Natl. Acad. Sci. USA, 100(10), 5591-5596.
  10. Dasgupta, S. and Gupta, A. (1999). An elementary proof of the Johnson-Lindenstrauss Lemma. (TR-99-006). Technical report. Berkeley, CA
  11. Indyk, P. and Motwani, R. (1998). Approximate nearest neighbors: Towards removing the curse of dimenstionality. In Proc. Symp. Theory of Computing. (pp. 604-613).
  12. Johnson, W. B and Lindenstrauss, J. (1984). Extensions of Lipschitz mappings into a Hilbert space. In Proc. Conf. Modern Analysis and Probability. (pp. 189-206).
  13. Niyogi, P. and Smale, S. and Weinberger, S. (2004). Finding the Homology of Submanifolds with Confidence from Random Samples. [Preprint].
  14. Roweis, S. T. and Saul, L. K. (2000, December). Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 290(5500), 2323-2326.
  15. Tenenbaum, J. B. and de Silva, V. and Langford, J. C. (2000, December). A Global Geometric Framework for Nonlinear Dimensionality Reduction. Science, 290(5500), 2319-2323.
  16. Weinberger, K. Q. and Saul, L. K. (2006). Unsupervised learning of image manifolds by semidefinite programming. Int. J. Computer Vision – Special Issue: Computer Vision and Pattern Recognition-CVPR 2004, 70(1), 77-90.
  17. Zhang, Z. and Zha, H. (2004). Principal Manifolds and Nonlinear Dimension Reduction via Tangent Space Alignment. SIAM J. Scientific Comput., 26(1),

Content actions

Download module as:

PDF | More downloads ...

Add 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