Graph Laplacians and their convergence on random neighborhood graphs

Details Graph Laplacians and their convergence on random neighborhood graphs Graph Laplacians and their convergence on random neighborhood graphs

2006-08-21

arxiv.org/abs/math/0608522v2

Mathematics

Statistics Theory

Improved presentation, typos corrected, to appear in JMLR

Scientific paper

Given a sample from a probability measure with support on a submanifold in Euclidean space one can construct a neighborhood graph which can be seen as an approximation of the submanifold. The graph Laplacian of such a graph is used in several machine learning methods like semi-supervised learning, dimensionality reduction and clustering. In this paper we determine the pointwise limit of three different graph Laplacians used in the literature as the sample size increases and the neighborhood size approaches zero. We show that for a uniform measure on the submanifold all graph Laplacians have the same limit up to constants. However in the case of a non-uniform measure on the submanifold only the so called random walk graph Laplacian converges to the weighted Laplace-Beltrami operator.

Affiliated with

Also associated with

No associations

Rating

Graph Laplacians and their convergence on random neighborhood graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Graph Laplacians and their convergence on random neighborhood graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Graph Laplacians and their convergence on random neighborhood graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-666808