Spectral Convergence Rate of Graph Laplacian

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 ${\mathbb{R}}^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.

References in corpus (2)

• Consistency of spectral clustering
• Nonparametric Bayesian Regression on Manifolds via Brownian Motion

Cited by in corpus (8)

• Eigen-convergence of Gaussian kernelized graph Laplacian by manifold heat interpolation
• Spectral Convergence of Graph Laplacian and Heat Kernel Reconstruction in $L^{\infty }$ from Random Samples
• The Mathematical Foundations of Manifold Learning
• Variational limits of k-NN graph based functionals on data clouds
• Convergence of Graph Laplacian with kNN Self-tuned Kernels
• Diffuse to fuse EEG spectra -- intrinsic geometry of sleep dynamics for classification
• Think globally, fit locally under the Manifold Setup: Asymptotic Analysis of Locally Linear Embedding
• PDE-Inspired Algorithms for Semi-Supervised Learning on Point Clouds