Towards a theoretical foundation for Laplacian-based manifold methods

被引:211
作者
Belkin, Mikhail [3 ]
Niyogi, Partha [1 ,2 ]
机构
[1] Univ Chicago, Dept Comp Sci, Chicago, IL 60637 USA
[2] Univ Chicago, Dept Stat, Chicago, IL 60637 USA
[3] Ohio State Univ, Dept Comp Sci & Engn, Columbus, OH 43210 USA
关键词
Laplace-Beltrami operator; Graph Laplacian; Manifold methods;
D O I
10.1016/j.jcss.2007.08.006
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In recent years manifold methods have attracted a considerable amount of attention in machine learning. However most algorithms in that class may be termed "manifold-motivated" as they lack any explicit theoretical guarantees. In this paper we take a step towards closing the gap between theory and practice for a class of Laplacian-based manifold methods. These methods utilize the graph Laplacian associated to a data set for a variety of applications in semi-supervised learning, clustering, data representation. We show that under certain conditions the graph Laplacian of a point cloud of data samples converges to the Laplace-Beltrami operator on the underlying manifold. Theorem 3.1 contains the first result showing convergence of a random graph Laplacian to the manifold Laplacian in the context of machine learning. (C) 2007 Published by Elsevier Inc.
引用
收藏
页码:1289 / 1308
页数:20
相关论文
共 38 条
[1]  
[Anonymous], CLUSTERINGS GOOD BAD
[2]  
[Anonymous], 1997, REG C SER MATH
[3]   Laplacian eigenmaps for dimensionality reduction and data representation [J].
Belkin, M ;
Niyogi, P .
NEURAL COMPUTATION, 2003, 15 (06) :1373-1396
[4]  
Belkin M., 2003, THESIS U CHICAGO
[5]  
BELKIN M, NIPS 2002
[6]  
BELKIN M, AI STATS 2005
[7]  
BELKIN M, COLT 2005
[8]  
BENGIO Y, NIPS 2003
[9]  
BERNSTEIN M, GRAPH APPROXIMATIONS
[10]  
BOUSQUET O, NIPS 2003