Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Numerical integration on graphs: Where to sample and how to weigh

Authors: George C. Linderman and Stefan Steinerberger
Journal: Math. Comp. 89 (2020), 1933-1952
MSC (2010): Primary 05C50, 05C70, 35P05, 65D32
Published electronically: January 29, 2020
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: Let $ G=(V,E,w)$ be a finite, connected graph with weighted edges. We are interested in the problem of finding a subset $ W \subset V$ of vertices and weights $ a_w$ such that

$\displaystyle \frac {1}{\vert V\vert}\sum _{v \in V}^{}{f(v)} \sim \sum _{w \in W}{a_w f(w)}$    

for functions $ f:V \rightarrow \mathbb{R}$ that are ``smooth'' with respect to the geometry of the graph; here $ \sim $ indicates that we want the right-hand side to be as close to the left-hand side as possible. The main application comprises problems where $ f$ is known to vary smoothly over the underlying graph but is expensive to evaluate on even a single vertex. We prove an inequality showing that the integration problem can be rewritten as a geometric problem (``the optimal packing of heat balls''). We discuss how one would construct approximate solutions of the heat ball packing problem; numerical examples demonstrate the efficiency of the method.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 05C50, 05C70, 35P05, 65D32

Retrieve articles in all journals with MSC (2010): 05C50, 05C70, 35P05, 65D32

Additional Information

George C. Linderman
Affiliation: Program in Applied Mathematics, Yale University, New Haven, Connecticut 06511

Stefan Steinerberger
Affiliation: Department of Mathematics, Yale University, New Haven, Connecticut 06511

Keywords: Graph, sampling, graph Laplacian, sampling, heat kernel, packing
Received by editor(s): March 20, 2018
Received by editor(s) in revised form: January 2, 2019, and September 1, 2019
Published electronically: January 29, 2020
Additional Notes: The first author was supported by NIH grant #1R01HG008383-01A1 (PI: Yuval Kluger) and U.S. NIH MSTP Training Grant T32GM007205.
The second author was supported by the NSF (DMS-1763179) and the Alfred P. Sloan Foundation.
Article copyright: © Copyright 2020 American Mathematical Society