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 d imensional manifold embedded in a higher dimensional space. The algorithm provides a computationally e cient approach t o n o nlinear 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 s c a l e n n images of a xed object taken with a m o ving camera yield data points in R n 2 . H o wever, the intrinsic dimensionality o f the space of all images of the same object is the number of degrees of freedom of the camera { in fact the space has the natural structure of a manifold embedded in R n 2 . While there is a large body of work on dimensionality reduction in general, most existing approaches do not explicitly take i n to account the structure of the manifold on which the data may possibly reside. Recently, there has been some interest (Tenenbaum et al, 2000 Roweis and Saul, 2000) in the problem of developing low dimensional representations of data in this particular context. In this paper, we present a new algorithm and an accompanying framework of analysis for geometrically motivated dimensionality reduction. The core algorithm is very simple, has a few local computations and one sparse eigenvalue problem. The solution re ects the intrinsic geometric structure of the manifold. The justi cation comes from the role of the Laplacian operator in providing an optimal embedding. The Laplacian of the graph obtained from the data points may be viewed as an approximation to the Laplace-Beltrami operator de ned on the manifold. The embedding maps for the data come from approximations to a natural map that is de ned on the entire manifold. The framework of analysis
The Laplacianface approach [16] REF used Locality Preserving Projections (LPP) to map the face images into a face subspace and were the optimal linear approximations to the eigenfunctions of the Laplace Beltrami operator on the face manifold.
Laplacian Eigenmaps and Spectral Techniques for Embedding and Clustering
NIPS
Computer Science