2018/03/19 by Linderman, George C., Steinerberger, Stefan · 1 citation
#FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Numerical Analysis (math.NA) #Statistics Theory (math.ST)
paper · doi:10.48550/arxiv.1803.06989
Let G=(V,E,w) be a finite, connected graph with weighted edges. We are interested in the problem of finding a subset W ⊂ V of vertices and weights aw such that (1)/(|V|)∑v ∈ Vf(v) ∼ ∑w ∈ Waw f(w) for functions f:V → ℝ 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.