Convergence of the graph Laplacian application to dimensionality estimation and image segmentation

author:Jean Yves Audibert, Center for Education and Research in Computer Science of the École des ponts, École des Ponts ParisTech, MINES ParisTech
published: Sept. 7, 2007,   recorded: September 2007,   views: 287
Categories
You might be experiencing some problems with Your Video player.

Related content

Visitors who watched this lecture also watched...
55:52
Graph methods and geometry of data

463 views - Mikhail Belkin, 2007
01:17:40
Introduction, Basic Notions in Graph Theory

2282 views - Tomaž Pisanski, 2007
32:52
Graph complexity for structure and learning

367 views - John Shawe-Taylor, 2007
29:44
Random walk graph kernels and rational kernels

401 views - S.V.N. Vishwanathan, 2007
27:06
Prediction on a graph

484 views - Mark Herbster, 2007
56:18
A theory of similarity functions for learning and clustering

591 views - Avrim Blum, 2007
20:21
Strings, graphs, invariants

235 views - Tomaž Pisanski, 2007
03:24:20
Lectures on Clustering

5726 views - Ulrike von Luxburg, 2007
54:52
Semi-supervised Learning, Manifold Methods

500 views - Partha Niyogi, 2005
30:46
Probabilistic graph partitioning

360 views - David Barber, 2007

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.

Description

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. We will present 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 nonuniform measure on the submanifold only the so called random walk graph Laplacian converges to the weighted Laplace-Beltrami operator. We will give two applications of these theoretical results.

Link this page  

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: