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

DOI10.1090/MCOM/3515MaRDI QIDQ4960080zbMATH OpenOpenAlexWikidataFDO

Authors George C. Linderman, Stefan Steinerberger

Publication date 8 April 2020

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

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

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)

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.

Recommendations

• scientific article; zbMATH DE number 5509066
• 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

Cites work

• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• scientific article; zbMATH DE number 3194652 (Why is no real title available?)
• A sampling theorem on homogeneous manifolds
• Clustering with t-SNE, provably
• Cubature formulas and discrete Fourier transform on compact manifolds
• Distributing many points on spheres: minimal energy and designs
• Eigenvalues of Laplacians on a Closed Riemannian Manifold and Its Nets
• From graph to manifold Laplacian: the convergence rate
• Generalized designs on graphs: Sampling, spectra, symmetries
• Half sampling on bipartite graphs
• Interpolating splines on graphs for data science applications
• Local-Set-Based Graph Signal Reconstruction
• Multiscale data sampling and function extension
• Poincaré and Plancherel--Polya Inequalities in Harmonic Analysis on Weighted Combinatorial Graphs
• Quadrature points via heat kernel repulsion
• Sampling in Paley-Wiener spaces on combinatorial graphs
• Sampling of Paley-Wiener functions on stratified groups
• Sequences, discrepancies and applications
• Shannon sampling and weak Weyl's law on compact Riemannian manifolds
• Spectral limitations of quadrature rules and generalized spherical designs
• Spherical codes and designs
• Sums of Distances Between Points on a Sphere. II
• The Stolarsky principle and energy optimization on the sphere
• The crystallization conjecture: a review

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)