Empirical Inference
Conference Paper
2005
From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians
PDF
Empirical Inference
Empirical Inference
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. |
| Links: | |
| Journal: | Proceedings of the 18th Conference on Learning Theory (COLT) |
| Pages: | 470-485 |
| Year: | 2005 |
| Day: | 0 |
| BibTeX Type: | Conference Paper (inproceedings) |
| Event Name: | Conference on Learning Theory |
| Digital: | 0 |
| Electronic Archiving: | grant_archive |
| Note: | Student Paper Award |
| Organization: | Max-Planck-Gesellschaft |
| School: | Biologische Kybernetik |
BibTeX
@inproceedings{3213,
title = {From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians},
journal = {Proceedings of the 18th Conference on Learning Theory (COLT)},
abstract = {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$.},
pages = {470-485},
organization = {Max-Planck-Gesellschaft},
school = {Biologische Kybernetik},
year = {2005},
note = {Student Paper Award},
author = {Hein, M. and Audibert, J. and von Luxburg, U.}
}