Towards a theoretical foundation for Laplacian-based manifold methods

By Mikhail Belkin, Partha Niyogi. 2005

703 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Vision and Pattern Recognition, Representation & Self-Supervised Learning, Statistical Learning Theory

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

In Computer Vision and Pattern Recognition

In Representation & Self-Supervised Learning

In Statistical Learning Theory

Citations in the corpus

A tutorial on spectral clustering (2007, methodology): “ R n, which satises hg;Lgi= Z jrgj2dx: This intuition has been made precise in the works of Belkin (2003), Lafon (2004), Hein, Audibert, and von Luxburg (2005); M., Audibert, and von Luxburg (2007), Belkin and Niyogi (2005), Hein (2006), Gine and Koltchinskii (2005). In general, it is proved that gr”
The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains (2012, background): “For example, [31] - [34] examine the convergence of discrete graph Laplacians (normalized and non-normalized) to continuous manifold Laplacians.”
Wavelets on Graphs via Spectral Graph Theory (2009, neutral): “The situation is diﬀerent from the analogous reconstruction formula (4) for the CWT, which shows the somewhat counterintuitive result that it is possible to recover a non zero-mean function by summing zero-mean wavelets.”
Laplacian Support Vector Machines Trained in the Primal (2009, positive): “In particular, choosing exponential weights for the adjacency matrix leads to convergence of the graph Laplacian to the Laplace–Beltrami operator on the manifold (Belkin and Niyogi, 2008).”
Angular Synchronization by Eigenvectors and Semidefinite Programming (2009, positive): “in the limit of a large number of vertices/projection images n→ ∞, the discrete normalized Laplacian matrix Lconverges to the continuous Laplacian over the two dimensional manifold RP2, denoted ∆ RP2 [27, 28, 29, 30]. In particular, the eigenvectors and eigenvalues of the graph Laplacian matrix Lcon”
Nonlocal Linear Image Regularization and Supervised Segmentation (2007, methodology): “A more general machine learning approach with kernel methods is presented in [37] and [6].”
Graph Laplacians and their Convergence on Random Neighborhood Graphs (2006, methodology): “The first work on the large sample limit of graph Laplacians has been done in Bousquet et al. (2004). There they studied the convergence of the regularization functional induced by the graph Laplacian using the law of large numbers for U -statistics. In a second step taking the limit of the neighbor”
Laplacian Auto-Encoders: An explicit learning of nonlinear data manifold (2015, background): “Based on this analogous relation, Belkin and Niyogi [5] show that minimizing R M J∇f̂ ðxÞJ22 corresponds to minimizing 12 P i;jWði; jÞ f̂ ðxiÞ f̂ ðxjÞ 2 on the graph G.”
A Tour of Modern Image Filtering: New Insights and Methods, Both Practical and Theoretical (2013, background): “Specifically, if we consider the data ( , x y i i) to be nodes on a (finite, undirected, weighted) graph with weights between nodes i and j given by the kernel values ( , , , ), K x x y y i j i j the matrix L I L = -is precisely the " graph Laplacian " [38], [5], [39].”
Spectral clustering and the high-dimensional stochastic blockmodel (2010, background): “Belkin (2003), Lafon (2004), Bousquet, Chapelle and Hein (2004), Hein, Audibert and von Luxburg (2005), Hein (2006), Gin´e and Koltchinskii (2006), Belkin and Niyogi (2008), von Luxburg, Belkin and Bousquet (2008) have all shown various forms of asymptotic convergence for this graph Laplacian.”
Non-linear independent component analysis with diffusion maps (2008, background): “The continuous limit of the discrete graph Laplacian corresponding to data points lying on a low-dimensional Riemannian manifold also gives rise to a similar scalar potential E, which is due to the fact that Euclidean distances in the ambient space are second-order approximations of geodesic distanc”
$\Gamma$-convergence of graph Ginzburg-Landau functionals (2012, neutral): “spired by [5] specically. We like to point out that there is also a substantial literature on the convergence of graph Laplacians and their eigenvalues and eigenvectors to continuum limits. See e.g. [40, 36, 12, 41, 13, 57, 43] and references therein. The techniques used and the kind of results obta”
From graph to manifold Laplacian: The convergence rate (2006, background): “First, if f : M → R is a smooth function, then the following result concerning the bias term has been established by various authors [1] [5] [6] established a uniform estimate of the error in both N and ε (the variance term), that decreases as 1/ √ N as N → ∞, but increases as In practice, one…”
Convergence of Laplacian Eigenmaps (2006, background): “This paper relies on results obtained in [3, 1] for functional convergence of operators.”
Vector Diffusion Maps and the Connection Laplacian (2011, background): “In the case where the data points {xi}ni=1 are independently sampled from a probability density function p(x) whose support is a d-dimensional manifoldM and satisfies some mild conditions, the graph Laplacian converges pointwise to the FokkerPlanck operator as stated in following proposition [26, 3,”