cicyt UNIZAR
Full-text links:

Download:

Current browse context:

math.ST

Change to browse by:

References & Citations

Bookmark

(what is this?)
CiteULike logo BibSonomy logo Mendeley logo del.icio.us logo Digg logo Reddit logo ScienceWISE logo

Mathematics > Statistics Theory

Title: Numerical Integration on Graphs: where to sample and how to weigh

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 $$ \frac{1}{|V|}\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. The main application are problems where $f$ is known to somehow depend on 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.
Subjects: Statistics Theory (math.ST); Learning (cs.LG); Numerical Analysis (math.NA); Machine Learning (stat.ML)
Cite as: arXiv:1803.06989 [math.ST]
  (or arXiv:1803.06989v1 [math.ST] for this version)

Submission history

From: Stefan Steinerberger [view email]
[v1] Mon, 19 Mar 2018 15:27:59 GMT (118kb,D)