Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs
In this paper we improve the spectral convergence rates for graph-based approximations of Laplace-Beltrami operators constructed from random data. We utilize regularity of the continuum eigenfunctions and strong pointwise consistency results to prove that spectral convergence rates are the same as the pointwise consistency rates for graph Laplacians. In particular, for an optimal choice of the graph connectivity $\varepsilon$, our results show that the eigenvalues and eigenvectors of the graph Laplacian converge to those of the Laplace-Beltrami operator at a rate of $O(n^{-1/(m+4)})$, up to log factors, where $m$ is the manifold dimension and $n$ is the number of vertices in the graph. Our approach is general and allows us to analyze a large variety of graph constructions that include $\varepsilon$-graphs and $k$-NN graphs.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Convergence of graph Dirichlet energies and graph Laplacians on intersecting manifolds of varying dimensions
We study $Γ$-convergence of graph Dirichlet energies and spectral convergence of graph Laplacians on unions of intersecting manifolds of potentially different dimensions. Our investigation is motivated by problems of mac…
Spectral Convergence of the connection Laplacian from random samples
Spectral methods that are based on eigenvectors and eigenvalues of discrete graph Laplacians, such as Diffusion Maps and Laplacian Eigenmaps are often used for manifold learning and non-linear dimensionality reduction. I…
Dimensionality ReductionGroup Invariant Spectral Embedding
Spectral embedding methods are widely used for dimensionality reduction and clustering of high-dimensional datasets with intrinsic low-dimensional structures. Although many datasets of practical interest exhibit invarian…
Dimensionality ReductionHypergraphs with Edge-Dependent Vertex Weights: p-Laplacians and Spectral Clustering
We study p-Laplacians and spectral clustering for a recently proposed hypergraph model that incorporates edge-dependent vertex weights (EDVW). These weights can reflect different importance of vertices within a hyperedge…
ClusteringA variational approach to the consistency of spectral clustering
This paper establishes the consistency of spectral approaches to data clustering. We consider clustering of point clouds obtained as samples of a ground-truth measure. A graph representing the point cloud is obtained by …
Clustering