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

DOI10.1090/MCOM/3515zbMATH Open1437.05143arXiv1803.06989OpenAlexW2996020520WikidataQ111858760 ScholiaQ111858760MaRDI QIDQ4960080FDOQ4960080

Stefan Steinerberger, George C. Linderman

Publication date: 8 April 2020

Published in: Mathematics of Computation (Search for Journal in Brave)

Abstract: Let $G=(V,E,w)$ be a finite, connected graph with weighted edges. We are interested in the problem of finding a subset $WsubsetV$ of vertices and weights $a_w$ such that ${\displaystyle }$ frac{1}{|V|}sum_{v in V}^{}{f(v)} sim sum_{w in W}{a_w f(w)}${\displaystyle }$ for functions $f:VightarrowmathbbR$ 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.

Full work available at URL: https://arxiv.org/abs/1803.06989

Recommendations

• scientific article
• On numerical integration methods with \(T\)-distribution weight function
• Random Weyl sampling for robust numerical integration of complicated functions
• scientific article; zbMATH DE number 464820
• Weighted discrepancy and high-dimensional numerical integration
• Numerical integration of harmonic functions with restricted sampling data
• A Generalization of the Method of Correlated Sampling for Numerical Integration
• Some refinements in methods of graphical integration

zbMATH Keywords

samplingheat kernelpackinggraph Laplacian

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Numerical quadrature and cubature formulas (65D32) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) General topics in linear spectral theory for PDEs (35P05)

Cites Work

• Title not available (Why is that?)
• The Stolarsky principle and energy optimization on the sphere
• Sums of Distances Between Points on a Sphere. II
• Sequences, discrepancies and applications
• From graph to manifold Laplacian: the convergence rate
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiscale data sampling and function extension
• Spherical codes and designs
• Distributing many points on spheres: minimal energy and designs
• Half sampling on bipartite graphs
• Sampling in Paley-Wiener spaces on combinatorial graphs
• A sampling theorem on homogeneous manifolds
• Sampling of Paley-Wiener functions on stratified groups
• Eigenvalues of Laplacians on a Closed Riemannian Manifold and Its Nets
• Cubature Formulas and Discrete Fourier Transform on Compact Manifolds
• Poincaré and Plancherel--Polya Inequalities in Harmonic Analysis on Weighted Combinatorial Graphs
• Title not available (Why is that?)
• The crystallization conjecture: a review
• Interpolating splines on graphs for data science applications
• Shannon sampling and weak Weyl's law on compact Riemannian manifolds
• Local-Set-Based Graph Signal Reconstruction
• Quadrature points via heat kernel repulsion
• Generalized designs on graphs: Sampling, spectra, symmetries
• Clustering with t-SNE, Provably
• Spectral Limitations of Quadrature Rules and Generalized Spherical Designs

Cited In (11)

• A low discrepancy sequence on graphs
• Codes, cubes, and graphical designs
• Graph signal sampling and interpolation based on clusters and averages
• Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport
• Quadrature points via heat kernel repulsion
• Graph signal interpolation with positive definite graph basis functions
• Graphical designs and gale duality
• Quadrature formulas on combinatorial graphs
• Sums of distances on graphs and embeddings into Euclidean space
• Overview of the topical collection: harmonic analysis on combinatorial graphs
• Quadratures over graphs via the Frank-Wolfe method and its variant

This page was built for publication: Numerical integration on graphs: Where to sample and how to weigh

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4960080)