A kernel-based analysis of Laplacian Eigenmaps

Given i.i.d. observations uniformly distributed on a closed manifold Msubseteq ℝp, we study the spectral properties of the associated empirical graph Laplacian based on a Gaussian kernel. Our main results are non-asymptotic error bounds, showing that the eigenvalues and eigenspaces of the empirical graph Laplacian are close to the eigenvalues and eigenspaces of the Laplace-Beltrami operator of M. In our analysis, we connect the empirical graph Laplacian to kernel principal component analysis, and consider the heat kernel of M as reproducing kernel feature map. This leads to novel points of view and allows to leverage results for empirical covariance operators in infinite dimensions.