Raghavendra Venkatraman
These lecture notes introduce the Galerkin method to approximate solutions to partial differential and integral equations. We begin with some analysis background to introduce this method in a Hilbert Space setting, and subsequently illustrate some computational examples with the help of a sample matlab code. Finally, we use the Galerkin method to prove the existence of solutions of a nonlinear boundary value problem.
Nicolás García Trillos, Chenghui Li, Raghavendra Venkatraman
We study the problem of estimating eigenpairs of elliptic differential operators from samples of a distribution $ρ$ supported on a manifold $M$. The operators discussed in the paper are relevant in unsupervised learning and in particular are obtained by taking suitable scaling limits of widely used graph Laplacians over data clouds. We study the minimax risk for this eigenpair estimation problem and explore the rates of approximation that can be achieved by commonly used graph Laplacians built from random data. More concretely, assuming that $ρ$ belongs to a certain family of distributions with controlled second derivatives, and assuming that the $d$-dimensional manifold $M$ where $ρ$ is supported has bounded geometry, we prove that the statistical minimax rate for approximating eigenvalues and eigenvectors in the $H^1(M)$-sense is $n^{-2/(d+4)}$, a rate that matches the minimax rate for a closely related density estimation problem. We then revisit the literature studying Laplacians over proximity graphs in the large data limit and prove that, under slightly stronger regularity assumptions on the data generating model, eigenpairs of graph Laplacians induce manifold agnostic estimators with an error of approximation that, up to logarithmic corrections, matches our lower bounds. Our analysis allows us to expand the existing literature on graph-based learning in at least two significant ways: 1) we consider stronger norms to measure the error of approximation than the ones that had been analyzed in the past; 2) our rates of convergence are uniform over a family of smooth distributions and do not just apply to densities with special symmetries, and, as a consequence of our lower bounds, are essentially sharp when the connectivity of the graph is sufficiently high.