Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

Abstract

Drawing on the correspondence between the graph Laplacian, the Laplace-Beltrami operator on a manifold, and the connections to the heat equation, we propose a geometrically motivated algorithm for constructing a representation for data sampled from a low dimensional manifold embedded in a higher dimensional space. The algorithm provides a computationally e cient approach tononlinear dimensionality reduction that has locality preserving properties and a natural connection to clustering. Several applications are considered. In many areas of arti cial intelligence, information retrieval and data mining, one is often confronted with intrinsically low dimensional data lying in a very high dimensional space. For example, gray scalen n images of a xed object taken with amoving camera yield data points in Rn2.However, the intrinsic dimensionalityof the space of all images of the same object is the number of degrees of freedom of