Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering

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…