Spectral Convergence Rate of Graph Laplacian

2015/10/27 by Xu Wang, Wang, Xu · 5 citations
Computer Science · Physics and Astronomy · #Topological and Geometric Data Analysis #Complex Network Analysis Techniques #Theoretical and Computational Physics

paper · pdf · doi:10.48550/arxiv.1510.08110

Abstract

Laplacian Eigenvectors of the graph constructed from a data set are used in many spectral manifold learning algorithms such as diffusion maps and spectral clustering. Given a graph constructed from a random sample of a d-dimensional compact submanifold M in ℝ^D, we establish the spectral convergence rate of the graph Laplacian. It implies the consistency of the spectral clustering algorithm via a standard perturbation argument. A simple numerical study indicates the necessity of a denoising step before applying spectral algorithms.

Cited by

• Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in L^∞ from Random Samples
• Higher-Order Regularization Learning on Hypergraphs
• Spectral convergence of graph Laplacian and heat kernel reconstruction in L∞ from random samples
• Think globally, fit locally under the Manifold Setup: Asymptotic Analysis of Locally Linear Embedding
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds

Related

• Spectral Convergence of the connection Laplacian from random samples
• Convergence of Laplacian Eigenmaps and its Rate for Submanifolds with Singularities
• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Error estimates for spectral convergence of the graph Laplacian on random geometric graphs towards the Laplace--Beltrami operator
• Improved spectral convergence rates for graph Laplacians on epsilon-graphs and k-NN graphs