nach oben

Foundations of Computational Mathematics

Erschienen in:

24.09.2019

Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace–Beltrami Operator

verfasst von: Nicolás García Trillos, Moritz Gerlach, Matthias Hein, Dejan Slepčev

Erschienen in: Foundations of Computational Mathematics | Ausgabe 4/2020

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the convergence of the graph Laplacian of a random geometric graph generated by an i.i.d. sample from a m-dimensional submanifold \({\mathcal {M}}\) in \(\mathbb {R}^d\) as the sample size n increases and the neighborhood size h tends to zero. We show that eigenvalues and eigenvectors of the graph Laplacian converge with a rate of \(O\Big (\big (\frac{\log n}{n}\big )^\frac{1}{2m}\Big )\) to the eigenvalues and eigenfunctions of the weighted Laplace–Beltrami operator of \({\mathcal {M}}\). No information on the submanifold \({\mathcal {M}}\) is needed in the construction of the graph or the “out-of-sample extension” of the eigenvectors. Of independent interest is a generalization of the rate of convergence of empirical measures on submanifolds in \(\mathbb {R}^d\) in infinity transportation distance.

Vorheriger Artikel Mathematics of Smoothed Particle Hydrodynamics: A Study via Nonlocal Stokes Equations

Nächster Artikel Lie–Poisson Methods for Isospectral Flows

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

Note that as stated, our theorems give \(C_{m,\alpha ,r }\) , but in this case \(C_{m,\alpha ,r }= C_{m,\alpha } r\) because we can always rescale to the unit ball.

Note that as stated, Theorem 1.1 in [11] gives \(C_{m,\alpha ,\beta ,r }\), but in this case \(C_{m,\alpha ,\beta ,r }= C_{m,\alpha ,\beta }\, r\) as one can simply rescale to the unit ball.

W. Arendt and A. F. M. ter Elst, Sectorial forms and degenerate differential operators, J. Operator Theory, 67 (2012), pp. 33–72.MathSciNetMATH

M. Belkin and P. Niyogi, Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation, 15 (2002), pp. 1373–1396.MATH

M. Belkin and P. Niyogi, Convergence of Laplacian eigenmaps, Advances in Neural Information Processing Systems (NIPS), 19 (2007), p. 129.

M. Belkin and P. Niyogi, Towards a theoretical foundation for Laplacian-based manifold methods, J. Comput. System Sci., 74 (2008), pp. 1289–1308.MathSciNetMATH

A. L. Besse, Manifolds all of whose geodesics are closed, vol. 93 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], Springer-Verlag, Berlin-New York, 1978. With appendices by D. B. A. Epstein, J.-P. Bourguignon, L. Bérard-Bergery, M. Berger and J. L. Kazdan.

D. Burago, S. Ivanov, and Y. Kurylev, A graph discretization of the Laplace-Beltrami operator, J. Spectr. Theory, 4 (2014), pp. 675–714.MathSciNetMATH

I. Chavel, Eigenvalues in Riemannian geometry, Academic Press, New York, 1984.MATH

R. R. Coifman and S. Lafon, Diffusion maps, Appl. Comput. Harmon. Anal., 21 (2006), pp. 5–30.MathSciNetMATH

M. P. do Carmo, Riemannian geometry, Mathematics: Theory & Applications, Birkhäuser Boston, Inc., Boston, MA, 1992. Translated from the second Portuguese edition by Francis Flaherty.

10.

K. Fujiwara, Eigenvalues of Laplacians on a closed riemannian manifold and its nets, Proc. Amer. Math. Soc., 123 (1995), pp. 2585–2594.MathSciNetMATH

11.

N. García Trillos and D. Slepčev, On the rate of convergence of empirical measures in \(\infty \)-transportation distance, Canad. J. Math., 67 (2015), pp. 1358–1383.MathSciNetMATH

12.

N. García Trillos and D. Slepčev, A variational approach to the consistency of spectral clustering, Appl. Comput. Harmon. Anal., 45 (2018), pp. 239–281.MathSciNetMATH

13.

E. Giné and V. Koltchinskii, Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results, in High dimensional probability, vol. 51 of IMS Lecture Notes Monogr. Ser., Inst. Math. Statist., Beachwood, OH, 2006, pp. 238–259.

14.

M. Hein, Uniform convergence of adaptive graph-based regularization, in Proc. of the 19th Annual Conference on Learning Theory (COLT), G. Lugosi and H. U. Simon, eds., Springer, 2006, pp. 50–64.

15.

M. Hein, J.-Y. Audibert, and U. v. Luxburg, Graph Laplacians and their convergence on random neighborhood graphs, Journal of Machine Learning Research, 8 (2007), pp. 1325–1368.MathSciNetMATH

16.

T. Leighton and P. Shor, Tight bounds for minimax grid matching with applications to the average case analysis of algorithms, Combinatorica, 9 (1989), pp. 161–187.MathSciNetMATH

17.

B. Mohar, Some applications of Laplace eigenvalues of graphs, in Graph Theory, Combinatoris and Applications, Y. Alavi, G. Chartrand, O. R. Oellermann, and A. J. Schwenk, eds., Wiley, 1991, pp. 871–898.

18.

D. Mugnolo and R. Nittka, Convergence of operator semigroups associated with generalised elliptic forms, J. Evol. Equ., 12 (2012), pp. 593–619.MathSciNetMATH

19.

P. Niyogi, S. Smale, and S. Weinberger, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39 (2008), pp. 419–441.MathSciNetMATH

20.

M. Penrose, Random geometric graphs, vol. 5 of Oxford Studies in Probability, Oxford University Press, Oxford, 2003.

21.

L. Rosasco, M. Belkin, and E. D. Vito, On learning with integral operators, Journal of Machine Learning Research, 11 (2010), pp. 905–934.MathSciNetMATH

22.

Y. Shi and B. Xu, Gradient estimate of an eigenfunction on a compact Riemannian manifold without boundary, Ann. Global Anal. Geom., 38 (2010), pp. 21–26.MathSciNetMATH

23.

Z. Shi, Convergence of Laplacian spectra from random samples. preprint, arXiv:1507.00151, 2015.

24.

P. W. Shor and J. E. Yukich, Minimax grid matching and empirical measures, Ann. Probab., 19 (1991), pp. 1338–1348.MathSciNetMATH

25.

A. Singer, From graph to manifold Laplacian: The convergence rate, Applied and Computational Harmonic Analysis, 21 (2006), pp. 128–134.MathSciNetMATH

26.

A. Singer and H.-T. Wu, Spectral convergence of the connection Laplacian from random samples, Information and Inference: A Journal of the IMA, 6 (2017), pp. 58–123.MathSciNetMATH

27.

M. Talagrand, The generic chaining, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2005. Upper and lower bounds of stochastic processes.

28.

D. Ting, L. Huang, and M. I. Jordan, An analysis of the convergence of graph Laplacians, in Proc. of the 27th Int. Conference on Machine Learning (ICML), 2010.

29.

U. von Luxburg, A tutorial on spectral clustering, Statistics and computing, 17 (2007), pp. 395–416.MathSciNet

30.

U. von Luxburg, M. Belkin, and O. Bousquet, Consistency of spectral clustering, Ann. Statist., 36 (2008), pp. 555–586.MathSciNetMATH

Titel: Error Estimates for Spectral Convergence of the Graph Laplacian on Random Geometric Graphs Toward the Laplace–Beltrami Operator
verfasst von: Nicolás García Trillos
Moritz Gerlach
Matthias Hein
Dejan Slepčev
Publikationsdatum: 24.09.2019
Verlag: Springer US
Erschienen in: Foundations of Computational Mathematics / Ausgabe 4/2020
Print ISSN: 1615-3375
Elektronische ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-019-09436-w

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 4/2020

Mathematics of Smoothed Particle Hydrodynamics: A Study via Nonlocal Stokes Equations

Computing Tropical Varieties Over Fields with Valuation

Convergence of Finite Volume Schemes for the Euler Equations via Dissipative Measure-Valued Solutions

On the Sample Complexity of the Linear Quadratic Regulator

Symbolic Computations of First Integrals for Polynomial Vector Fields

Tropical Combinatorial Nullstellensatz and Sparse Polynomials

Premium Partner