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

By Matthias Hein, Jean-Yves Audibert, Ulrike von Luxburg. Annual Conference Computational Learning Theory, 2005

369 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/7edde67273c2ad09458d73328628f3385d0df837

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Convergence of Laplacian Eigenmaps (2006, background): “Those results were further generalized and presented with an empirical pointwise convergence theorem for the manifold case in [9].”
Wavelet transform on manifolds: Old and new approaches (2010, methodology): “Then it has been shown in [ 17 , 31] that the Laplacian matrix converges to the matrix representing the Laplace-Beltrami operator on the manifold as one increases the sampling density.”
Manifold Denoising (2006, methodology): “Our qualitative theoretical analysis of the denoising algo rithm is based on recent results on the limit of graph Laplacians [7, 8] as the neighborhood size decrease s and the sample size increases.”
Diffusion Maps, Spectral Clustering and Eigenfunctions of Fokker-Planck Operators (2005, result): “The connection between the discrete matrix M and the (weighted) Laplace-Beltrami or Fokker-Planck operator, as well as rigorous convergence proofs of the eigenvalues and eigenvectors of M t those of the integral operatorTb or infinitesimal generator Hb were considered in many recent works [4, 23, 17”
Graph Laplacians and their Convergence on Random Neighborhood Graphs (2006, background): “…in high-density regions whereas changes of the classiﬁer are allowed in low-density regions, see Bousquet et al. (2004) for some discussion of this point and Hein (2005, 2006) for a proof of convergence of the regularizer induced by the graph Laplacian towards the smoothness functional S ( f ).”
Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, background): “Third, the graph Laplacian, under some conditions, converges to the intrinsic Laplace-Beltrami operator on a Riemannian manifold [25]–[27], therefore it may well capture the underlying manifold structure of the observed”
A tutorial on spectral clustering (2007, result): “At the same time, Hein et al. (2005) prove more general results, taking into account all different graph Laplacians L, Lrw, and Lsym, more general similarity functions, and manifolds with arbitrary distributions.”
Randomized Near Neighbor Graphs, Giant Components, and Applications in Data Science (2017, background): “Taking the k − nearest neighbors is a standard practice in the ﬁeld (see e.g. [ 2, 11, 23]) and will undoubtedly preserve locality.”
Local Kernels and the Geometric Structure of Data (2014, neutral): “In Section 2 we summarize the relevant developments and techniques related to diffusion maps as found in [2, 6, 19, 12, 21, 4].”
Diffusion maps, spectral clustering and reaction coordinates of dynamical systems (2005, background): “to the eigenvalues and eigenfunctions of these continuum operators. Rigorous mathematical proofs of this convergence as N→ ∞ under 7 various assumptions have been recently obtained by several authors [22, 23]. Therefore, for a better understanding of the ﬁnite sample case, we are interested in the p”
Towards a theoretical foundation for Laplacian-based manifold methods (2005, background): “Those results are further generalized and presented with an empirical convergence theorem in the parallel COLT paper [13].”
Discrete Signal Processing on Graphs (2012, background): “ples uniformly randomly a low-dimensional manifold then the (empirical) graph Laplacian acting on a smooth function on this manifold is a good discrete approximation that converges pointwise and uniformly to the elliptic Laplace-Beltrami operator applied to this function as the number of points goes”