Manifold clustering

Published 1 January 2005Open access

Richard Souvenir, Robert Pless

DOI10.1109/iccv.2005.149

Citations158

TL;DR

This work extends manifold learning to classify and parameterize unlabeled data which lie on multiple, intersecting manifolds, significantly increases the domain to which manifold learning methods can be applied, allowing parameterization of example manifolds such as figure eights and intersecting paths which are quite common in natural data sets.

Abstract

Manifold learning has become a vital tool in data driven methods for interpretation of video, motion capture, and handwritten character data when they lie on a low dimensional, nonlinear manifold. This work extends manifold learning to classify and parameterize unlabeled data which lie on multiple, intersecting manifolds. This approach significantly increases the domain to which manifold learning methods can be applied, allowing parameterization of example manifolds such as figure eights and intersecting paths which are quite common in natural data sets. This approach introduces several technical contributions which may be of broader interest, including node-weighted multidimensional scaling and a fast algorithm for weighted low-rank approximation for rank-one weight matrices. We show examples for intersecting manifolds of mixed topology and dimension and demonstrations on human motion capture data.

Keywords

Computer Science

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 statisticsPrincipal Component Analysis

8,213 Citations1986Ian T. Jolliffe

View PDF

PsychometrikaNonmetric Multidimensional Scaling: A Numerical Method

4,882 Citations1964Joseph B. Kruskal

The numerical methods required in the approach to multi-dimensional scaling are described and the rationale of this approach has appeared previously.

The MIT Press eBooksLaplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

4,535 Citations2002Mikhail Belkin, Partha Niyogi

The algorithm provides a computationally efficient approach to nonlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering.

Proceedings of the National Academy of SciencesHessian eigenmaps: Locally linear embedding techniques for high-dimensional data

1,696 Citations2003David L. Donoho, Carrie Grimes

The Hessian-based locally linear embedding method for recovering the underlying parametrization of scattered data (mi) lying on a manifold M embedded in high-dimensional Euclidean space is described, where the isometric coordinates can be recovered up to a linear isometry.

ScienceThe Isomap Algorithm and Topological Stability

844 Citations2002Mukund Balasubramanian, Eric L. Schwartz

An algorithm for computing a quasi-isometric, low-dimensional embedding of a set of high-dimensional data points and the basic approach presented is not new, having been presented previously.

Maximum Likelihood Estimation of Intrinsic Dimension

709 Citations2004Elizaveta Levina, Peter J. Bickel

A new method for estimating intrinsic dimension of a dataset derived by applying the principle of maximum likelihood to the distances between close neighbors is proposed, which has the best overall performance compared with two other intrinsic dimension estimators.

International Conference on Machine LearningWeighted low-rank approximations

702 Citations2003Nathan Srebro, Tommi Jaakkola

This work provides a simple and efficient algorithm for solving weighted low-rank approximation problems, which, unlike their unweighted version, do not admit a closed-form solution in general.

International Journal of Computer VisionUnsupervised Learning of Image Manifolds by Semidefinite Programming

700 Citations2006Kilian Q. Weinberger, Lawrence K. Saul

An algorithm for unsupervised learning of image manifolds by semidefinite programming that computes a low dimensional representation of each image with the property that distances between nearby images are preserved.

View PDF