Volume 38, Issue 6
Convergence of Laplacian Spectra from Random Samples

Wenqi Tao & Zuoqiang Shi

J. Comp. Math., 38 (2020), pp. 952-984.

Published online: 2020-11

Preview Full PDF 73 1135
Export citation
  • Abstract

Eigenvectors and eigenvalues of discrete Laplacians are often used for manifold learning and nonlinear dimensionality reduction. Graph Laplacian is one widely used discrete laplacian on point cloud. It was previously proved by Belkin and Niyogithat 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. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples. Moreover, estimation of the convergence rate is also given.

  • Keywords

Graph Laplacian, Laplacian spectra, Random samples, Spectral convergence.

  • AMS Subject Headings

62G20, 65N25, 60D05

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

twq17@mails.tsinghua.edu.cn (Wenqi Tao)

zqshi@tsinghua.edu.cn (Zuoqiang Shi)

  • BibTex
  • RIS
  • TXT
@Article{JCM-38-952, author = {Tao , Wenqi and Shi , Zuoqiang }, title = {Convergence of Laplacian Spectra from Random Samples}, journal = {Journal of Computational Mathematics}, year = {2020}, volume = {38}, number = {6}, pages = {952--984}, abstract = {

Eigenvectors and eigenvalues of discrete Laplacians are often used for manifold learning and nonlinear dimensionality reduction. Graph Laplacian is one widely used discrete laplacian on point cloud. It was previously proved by Belkin and Niyogithat 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. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples. Moreover, estimation of the convergence rate is also given.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.2008-m2018-0232}, url = {http://global-sci.org/intro/article_detail/jcm/18415.html} }
TY - JOUR T1 - Convergence of Laplacian Spectra from Random Samples AU - Tao , Wenqi AU - Shi , Zuoqiang JO - Journal of Computational Mathematics VL - 6 SP - 952 EP - 984 PY - 2020 DA - 2020/11 SN - 38 DO - http://doi.org/10.4208/jcm.2008-m2018-0232 UR - https://global-sci.org/intro/article_detail/jcm/18415.html KW - Graph Laplacian, Laplacian spectra, Random samples, Spectral convergence. AB -

Eigenvectors and eigenvalues of discrete Laplacians are often used for manifold learning and nonlinear dimensionality reduction. Graph Laplacian is one widely used discrete laplacian on point cloud. It was previously proved by Belkin and Niyogithat 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. In this paper, we prove that the eigenvectors and eigenvalues obtained by PIM converge in the limit of infinitely many random samples. Moreover, estimation of the convergence rate is also given.

Wenqi Tao & Zuoqiang Shi. (2020). Convergence of Laplacian Spectra from Random Samples. Journal of Computational Mathematics. 38 (6). 952-984. doi:10.4208/jcm.2008-m2018-0232
Copy to clipboard
The citation has been copied to your clipboard