Principal Manifolds and Nonlinear Dimension Reduction via Local Tangent Space Alignment

arXiv (Cornell University)Published 7 December 2002Open access

Zhenyue Zhang, Hongyuan Zha

DOI10.48550/arxiv.cs/0212008

Citations540

TL;DR

A new algorithm for manifold learning and nonlinear dimension reduction is presented based on a set of unorganized data points sampled with noise from the manifold that represents the local geometry of the manifold using tangent spaces learned by fitting an affine subspace in a neighborhood of each data point.

Abstract

Nonlinear manifold learning from unorganized data points is a very challenging unsupervised learning and data visualization problem with a great variety of applications. In this paper we present a new algorithm for manifold learning and nonlinear dimension reduction. Based on a set of unorganized data points sampled with noise from the manifold, we represent the local geometry of the manifold using tangent spaces learned by fitting an affine subspace in a neighborhood of each data point. Those tangent spaces are aligned to give the internal global coordinates of the data points with respect to the underlying manifold by way of a partial eigendecomposition of the neighborhood connection matrix. We present a careful error analysis of our algorithm and show that the reconstruction errors are of second-order accuracy. We illustrate our algorithm using curves and surfaces both in 2D/3D and higher dimensional Euclidean spaces, and 64-by-64 pixel face images with various pose and lighting conditions. We also address several theoretical and algorithmic issues for further research and improvements.

Keywords

Computer Science

Springer series in statisticsThe Elements of Statistical Learning

24,344 Citations2001Trevor Hastie, J. Friedman +1 more

View PDF

ScienceNonlinear Dimensionality Reduction by Locally Linear Embedding

15,035 Citations2000Sam T. Roweis, Lawrence K. Saul

Locally linear embedding (LLE) is introduced, an unsupervised learning algorithm that computes low-dimensional, neighborhood-preserving embeddings of high-dimensional inputs that learns the global structure of nonlinear manifolds.

ScienceA Global Geometric Framework for Nonlinear Dimensionality Reduction

13,740 Citations2000Joshua B. Tenenbaum, Vin de Silva +1 more

An approach to solving dimensionality reduction problems that uses easily measured local metric information to learn the underlying global geometry of a data set and efficiently computes a globally optimal solution, and is guaranteed to converge asymptotically to the true structure.

Springer series in information sciencesSelf-Organizing Maps

10,377 Citations1997Teuvo Kohonen

The mathematical preliminaries, background, basic ideas, and implications of the Self-Organising Map algorithm are expounded in a manner which is accessible without prior expert knowledge.

Neural ComputationLaplacian Eigenmaps for Dimensionality Reduction and Data Representation

7,709 Citations2003Mikhail Belkin, Partha Niyogi

This work proposes a geometrically motivated algorithm for representing the high-dimensional data that provides a computationally efficient approach to nonlinear dimensionality reduction that has locality-preserving properties and a natural connection to clustering.

Stochastic Neighbor Embedding

1,461 Citations2002Geoffrey E. Hinton, Sam T. Roweis

This probabilistic framework makes it easy to represent each object by a mixture of widely separated low-dimensional images, which allows ambiguous objects, like the document count vector for the word "bank", to have versions close to the images of both "river" and "finance" without forcing the image of outdoor concepts to be located close to those of corporate concepts.

Neural NetworksTopology representing networks

887 Citations1994Thomas Martinetz, Klaus Schulten

This competitive Hebbian rule provides a novel approach to the problem of constructing topology preserving feature maps and representing intricately structured manifolds and makes this novel approach particularly useful in all applications where neighborhood relations have to be exploited or the shape and topology of submanifolds have to been take into account.

ScholarlyCommons (University of Pennsylvania)Global Coordination of Local Linear Models

177 Citations2001Sam T. Roweis, Lawrence K. Saul +1 more

The regularizer takes the form of a Kullback-Leibler divergence and illustrates an unexpected application of variational methods: not to perform approximate inference in intractable probabilistic models, but to learn more useful internal representations in tractable ones.

View PDF

Deriving action and behavior primitives from human motion data

165 Citations2003Odest Chadwicke Jenkins, Maja J. Matarić

This work presents a data-driven method for deriving perceptual-motor action and behavior primitives from human motion capture data using a spatio-temporal non-linear dimension reduction technique on a set of motion segments.

CaltechAUTHORS (California Institute of Technology)Grouping and dimensionality reduction by locally linear embedding

147 Citations2001Marzia Polito, Pietro Perona

A variant of LLE that can simultaneously group the data and calculate local embedding of each group is studied, and an estimate for the upper bound on the intrinsic dimension of the data set is obtained automatically.

View PDF