0.6 Dimensionality reduction  (Page 2/3)

These algorithms can be useful for learning the dimension and parametrizations of manifolds, forsorting 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, theWhitney Reduction Network [link] , [link] , seeks a linear mapping to ${\mathbb{R}}^M$ that preserves ambient pairwise distances on the manifold and is particularly useful forprocessing 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 ${\mathbb{R}}^M$ . The Geodesic Minimal Spanning Tree (GMST)  [link] models the data as random samples from the manifold and estimates the corresponding entropy anddimensionality. Another technique  [link] 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.). PersistenceBarcodes  [link] are a related technique that involves constructing a type of signature for a manifold (orsimply 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 ${\mathbb{R}}^N$ . To solve a semi-supervised learning problem, a method calledLaplacian Eigenmaps  [link] has been proposed that involves forming an adjacency graph for the data in ${\mathbb{R}}^N$ , computing eigenfunctions of the Laplacian operator on the graph (which forma basis for $L_2$ on the graph), and using these functions to train a classifier on the data. The resulting classifiers havebeen used for handwritten digit recognition, document classification, and phoneme classification. (The $M$ smoothest eigenfunctions can also be used to embed the manifold in $M$ , similar to the approaches described above.) A related methodcalled Diffusion Wavelets  [link] uses powers of the diffusion operator to model scale on the manifold, then constructswavelets to capture local behavior at each scale. The result is a wavelet transform adapted not to geodesic distance but todiffusion distance, which measures (roughly) the number of paths connecting two points.