Header logo is

From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians

2005

Conference Paper

ei


In the machine learning community it is generally believed that graph Laplacians corresponding to a finite sample of data points converge to a continuous Laplace operator if the sample size increases. Even though this assertion serves as a justification for many Laplacian-based algorithms, so far only some aspects of this claim have been rigorously proved. In this paper we close this gap by establishing the strong pointwise consistency of a family of graph Laplacians with data-dependent weights to some weighted Laplace operator. Our investigation also includes the important case where the data lies on a submanifold of $R^d$.

Author(s): Hein, M. and Audibert, J. and von Luxburg, U.
Journal: Proceedings of the 18th Conference on Learning Theory (COLT)
Pages: 470-485
Year: 2005
Day: 0

Department(s): Empirical Inference
Bibtex Type: Conference Paper (inproceedings)

Event Name: Conference on Learning Theory

Digital: 0
Note: Student Paper Award
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF

BibTex

@inproceedings{3213,
  title = {From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians},
  author = {Hein, M. and Audibert, J. and von Luxburg, U.},
  journal = {Proceedings of the 18th Conference on Learning Theory (COLT)},
  pages = {470-485},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  year = {2005},
  note = {Student Paper Award}
}