Jeff Calder, Nicolas Garcia Trillos, Marta Lewicka

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


In this paper we study Lipschitz regularity of elliptic PDEs on geometric graphs, constructed from random data points. The data points are sampled from a distribution supported on a smooth manifold. The family of equations that we study arises in data analysis in the context of graph-based learning and contains, as important examples, the equations satisfied by graph Laplacian eigenvectors. In particular, we prove high probability interior and global Lipschitz estimates for solutions of graph Poisson equations. Our results can be used to show that graph Laplacian eigenvectors are, with high probability, essentially Lipschitz regular with constants depending explicitly on their corresponding eigenvalues. Our analysis relies on a probabilistic coupling argument of suitable random walks at the continuum level, and an interpolation method for extending functions on random point clouds to the continuum manifold. As a byproduct of our general regularity results, we obtain high probability L and approximate C 0,1 convergence rates for the convergence of graph Laplacian eigenvectors toward eigenfunctions of the corresponding weighted Laplace-Beltrami operators. The convergence rates we obtain scale like the L2 convergence rates established in J. Calder and N. Garcia Trillos, arXiv:1910.13476, 2019.

Original languageEnglish (US)
Pages (from-to)1169-1222
Number of pages54
JournalSIAM Journal on Mathematical Analysis
Issue number1
StatePublished - 2022

Bibliographical note

Funding Information:
\ast Received by the editors July 30, 2020; accepted for publication (in revised form) September 13, 2021; published electronically February 22, 2022. Funding: The first author was supported by NSF-DMS grant 1713691. The second author was supported by NSF-DMS grant 1912802. The third author was supported by NSF-DMS grant 1613153. \dagger School of Mathematics, University of Minnesota, Minneapolis, MN 55455 USA (jcalder@ \ddagger Department of Statistics, University of Wisconsin--Madison, Madison, WI 53706 USA ( \S Department of Mathematics, University of Pittsburgh, Pittsburgh, PA 15260 USA (lewicka@

Publisher Copyright:
© 2022 Society for Industrial and Applied Mathematics.


  • graph Laplacian
  • graph-based learning
  • random data cloud


Dive into the research topics of 'LIPSCHITZ REGULARITY OF GRAPH LAPLACIANS ON RANDOM DATA CLOUDS'. Together they form a unique fingerprint.

Cite this