From graph to manifold Laplacian: The convergence rate

By Amit Singer. 2006

396 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/d0c7de463bfaaacaecc39c13644041c011f4beac

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 Computer Vision and Pattern Recognition

Citations in the corpus

Wavelet transform on manifolds: Old and new approaches (2010, background): “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.”
A class of Laplacian multiwavelets bases for high-dimensional data (2015, background): “[41] Singer, A.”
Graph Laplacians and their Convergence on Random Neighborhood Graphs (2006, background): “In Singer (2006), see also Gin´e and Koltchinskii (2006), the rate of convergence given by Hein et al. (2005) has been improved in the setting of the uniform measure.”
On Learning with Integral Operators (2010, background): “Convergence of the normalized graph Laplacian applied to a fixed smooth function on the manifold is discussed in Hein et al. (2005), Singer (2006) and Lafon (2004).”
Metric Learning and Manifolds: Preserving the Intrinsic Geometry (2017, positive): “Methods for choosing (cid:15) have been studied by (Singer, 2006), and we rely on them in our implementation.”
Recent Trends, Applications, and Perspectives in 3D Shape Similarity Assessment (2016, neutral): “Unlesssomespecialcases (see,e.g.,[BSW08,BS07,Sin06,HAvL05]),thediscreteLaplace-Beltramioperatorwouldnotconvergetothecontinuousone.”
Local Kernels and the Geometric Structure of Data (2014, neutral): “To begin, we briefly summarize the relevant results of [6, 19].”
Diffusion polynomial frames on metric measure spaces (2008, background): “If f is any compactly supported, infinitely differentiable function on X, Singer [38] has shown that for every x ∈ X 1 ∆ (X,W ) (f )(x) = 1 2 ∆ B (f )(x) + O 1 |X| 1 2 1 2 + n 4 + .”
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,”
Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, background): “We believe that our new framework can benefit numerous emerging real world applications, such as the analysis of transportation, biomedical, and social networks, where it is critical to infer hidden relationships between data entities.”
LanczosNet: Multi-Scale Deep Graph Convolutional Networks (2019, neutral): “ptotically. For example, even for isotropic Gaussian kernels, the graph Laplacian can converge pointwise to the Laplace-Beltrami, Fokker-Planck operator and heat kernel under different normalizations [17, 18]. In practice, we notice that choosing = P (p;q)2E k(f (x p) 2f (x q))k=jEjhelps normalizing”
Convergence of Laplacian Eigenmaps (2006, background): “A faster convergence rate was obtained in [30].”
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.”
Diffusion maps (2006, background): “This bound can be further refined [24] by noticing that the numerator and denominator of the expression defining P̄ε,αf (xi) are correlated random variables.”
Diffusion Maps, Reduction Coordinates, and Low Dimensional Representation of Stochastic Systems (2008, background): “The work [48] presents a possible criterion for the choice of ε.”
Towards a theoretical foundation for Laplacian-based manifold methods (2005, background): “Further generalization and an empirical convergence result was presented in [16] and an improved rate in [29].”
Angular Synchronization by Eigenvectors and Semidefinite Programming (2009, neutral): “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”