Continuous nonlinear dimensionality reduction by kernel eigenmaps

Published 9 August 2003

Matthew Brand

Citations60

TL;DR

This work equate nonlinear dimensionality reduction (NLDR) to graph embedding with side information about the vertices, and derive a solution to either problem in the form of a kernel-based mixture of affine maps from the ambient space to the target space.

Abstract

We equate nonlinear dimensionality reduction (NLDR) to graph embedding with side information about the vertices, and derive a solution to either problem in the form of a kernel-based mixture of affine maps from the ambient space to the target space. Unlike most spectral NLDR methods, the central eigenproblem can be made relatively small, and the result is a continuous mapping defined over the entire space, not just the datapoints. A demonstration is made to visualizing the distribution of word usages (as a proxy to word meanings) in a sample of the machine learning literature. 1 Background: Graph embcddings Consider a connected graph with weighted undirected edges specified by edge matrix W. Let be the positive edge weight between connected vertices i and j zero otherwise. Let D = diag(Wl) be a diagonal matrix where the cumulative edge weights into vertex /. The following points are well known or easily derived in spectral

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.

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.

Regional conference series in mathematicsSpectral Graph Theory

5,722 Citations1996Fan Chung

Locality Preserving Projections

3,955 Citations2003Xiaofei He, Partha Niyogi

These are linear projective maps that arise by solving a variational problem that optimally preserves the neighborhood structure of the data set by finding the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator on the manifold.

THE LAPLACIAN SPECTRUM OF GRAPHS y

1,118 Citations1991Bojan Mohar

Neural ComputationDimension Reduction by Local Principal Component Analysis

723 Citations1997Nandakishore Kambhatla, Todd K. Leen

A local linear approach to dimension reduction that provides accurate representations and is fast to compute is developed and it is shown that the local linear techniques outperform neural network implementations.

Charting a Manifold

374 Citations2002Matthew Brand

A nonlinear mapping from a high-dimensional sample space to a low-dimensional vector space is constructed, effectively recovering a Cartesian coordinate system for the manifold from which the data is sampled, and is pseudo-invertible.