39
$\begingroup$

Here's the sort of thing I have in mind. Let $M$ be a Riemannian manifold, compact if it helps, and let $\Delta_M$ be the Laplace-Beltrami operator. Choose a sequence of triangulations of $M$ so that the triangles in the $n$th triangulation all have diameter smaller than $1/n$, and let $\Delta_n$ denote the corresponding graph Laplacian - that is, the operator which sends a function $f$ on the vertices of a graph to the function whose value at a vertex is the average of $f$ on all neighboring vertices.

Is there a precise sense in which $\Delta_n$ converges to $\Delta_M$? If not, can we at least calculate spectral invariants for $\Delta_M$ using spectral invariants for $\Delta_n$?

The question is a little strange since the graph Laplacian acts on a finite dimensional space (for a finite graph) while the ordinary Laplacian is an unbounded operator on infinite dimensional Hilbert space. It is also not clear that the two operators capture the same kind of geometric information; for example, the dimension of $M$ can be recovered from $\Delta_M$, but it is not obvious to me how to calculate the dimension of $M$ from the $\Delta_n$'s. Nevertheless, my intuition tells me that there's something out there.

Added: Thanks everyone for all the links / references - I'll need a few more days to chase them down. I'm glad there is so much literature on this question!

Improve this question
$\endgroup$
4
  • $\begingroup$ The space on which the graph Laplacian acts ought to be embeddable into the space on which the ordinary Laplacian acts, say by using smooth bump functions around each vertex. Also, I assume you have to do some kind of rescaling by the lengths of the edges based on the motivating example of $\mathbb{R}$. $\endgroup$
    – Qiaochu Yuan
    Commented Jun 4, 2011 at 14:03
  • $\begingroup$ Does this paper help? arxiv.org/pdf/math/0609599 $\endgroup$
    – Alain Valette
    Commented Jun 4, 2011 at 14:07
  • $\begingroup$ And the abstract of the paper Alain linked to: arxiv.org/abs/math/0609599 $\endgroup$
    – Did
    Commented Jun 5, 2011 at 10:06
  • 1
    $\begingroup$ you should basically look at the 1-skelaton of the CW structure of the manifold. In any reasonable situation, you can define the homology using Hodge decomposition by harmonic forms, and the discrete laplacian on the 1-skeleton would be "compatible" with the usual laplacian. if you take more refined skelatons. See this draft of book by Lubotzky - citeseerx.ist.psu.edu/viewdoc/… , around page 34. $\endgroup$
    – Asaf
    Commented Jun 6, 2011 at 11:57

6 Answers 6

Reset to default
24
$\begingroup$

If laplacian $\Delta_n$ is defined just as $\[\Delta_n f\](u)=\sum_v (f(v)-f(u))$, where the sum is over all neighbors v of the vertex u, then the answer is NO. Informal reason is that such $\Delta_n$ does not feel the embedding of the graph into the manifold $M$ at all.

More promising approach is to define $\Delta_n$ as $\[\Delta_n f\](u)=\sum_v c(uv)(f(v)-f(u))/m(u)$ with some edge weights $c(uv)$ and vertex weights $m(u)$ depending on the embedding of the graph into $M$. For right choice of weights the answer is positive in some particular cases: e.g., square lattice in the plane, isoradial triangulation of the plane, regular triangulation of the plane. In general there is no ``natural'' laplacian $\Delta_n$ such that convergence holds.

Here are some references, see also references therein:

[1] M. Wardetzky, S. Mathur, F. Kaberer, E. Grinspun, Discrete Laplace operators: no free lunch, Eurographics Symp. Geom. Processing, A.~Belyaev, M.~Garland (eds.), 2007.

[2] D. Chelkak and S. Smirnov, Discrete complex analysis on isoradial graphs, Adv. Math., to appear, https://arxiv.org/abs/0810.2188v2.

[3] R. Courant, K. Friedrichs, H. Lewy, Uber die partiellen Differenzengleichungen der mathematischen Physik, Math. Ann. 100, (1928), 32--74. English transl.: IBM Journal (1967), 215--234. Russian transl.: Russ. Math. Surveys 8 (1941), 125--160. https://web.stanford.edu/class/cme324/classics/courant-friedrichs-lewy.pdf

Improve this answer
$\endgroup$
8
$\begingroup$

A paper that seems to give a high-level overview and useful references is Singer, A. "From graph to manifold Laplacian: The convergence rate". Appl. Comput. Harmon. Anal. 21, 128 (2006). (link)

Improve this answer
$\endgroup$
3
$\begingroup$

The idea is quite old. The finite element method was designed exactly to approximate eigenfunctions with finite dimensional operator defined via triangulations (see papers of Babushka and Osborn). There is a recent paper by Burago and Ivanov https://arxiv.org/abs/1301.2222. The references of this paper include some earlier work, for example, the work of Fujiwara.

Improve this answer
$\endgroup$
3
$\begingroup$

Koltchinskii an Gine study how discrete Laplacians constructed for randomly sampled points on a manifold approximate the true Laplacian:

Link

Improve this answer
$\endgroup$
3
$\begingroup$

Yves Colin de Verdière's work non the $\mu-$invariant of graphs was motivated by discretizing Schrödinger operators on surfaces (endowed with Riemannian metrics). His papers (mainly in French but probably largely readable by somebody speaking English) on the subject might therefore be interesting to you, see for example his book "Spectres de graphe", Cours Spécialisés, 4. Société Mathématique de France, Paris, 1998. viii+114 pp.

Improve this answer
$\endgroup$
2
$\begingroup$

For some reasons, this is a question much studied in the community of theoretical computer scientists. Some relevant (and rather interesting) papers have been written by Belkin and Niyogi; and by Audibert, Hein and von Luxburg.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .