Convergence of Laplacian spectra from random samples

Abstract

Eigenvectors and eigenvalues of discrete graph Laplacians are often used for manifold learning and nonlinear dimensionality reduction. It was previously proved by Belkin and Niyogi that the eigenvectors and eigenvalues of the graph Laplacian converge to the eigenfunctions and eigenvalues of the Laplace-Beltrami operator of the manifold in the limit of infinitely many data points sampled independently from the uniform distribution over the manifold. Recently, we introduced Point Integral method (PIM) to solve elliptic equations and corresponding eigenvalue problem on point clouds. We have established a unified framework to approximate the elliptic differential operators on point clouds. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples independently from a distribution (not necessarily to be uniform distribution). Moreover, one estimate of the rate of the convergence is also given.

References in corpus (1)

• Convergence of Laplacian Spectra from Point Clouds

Cited by in corpus (7)

• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• On the Consistency of Graph-based Bayesian Learning and the Scalability of Sampling Algorithms
• Spectral convergence of diffusion maps: improved error bounds and an alternative normalisation
• A continuum limit for the PageRank algorithm
• Large sample spectral analysis of graph-based multi-manifold clustering
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs