Numerical integration on graphs: Where to sample and how to weigh
HTML articles powered by AMS MathViewer
- by George C. Linderman and Stefan Steinerberger HTML | PDF
- Math. Comp. 89 (2020), 1933-1952 Request permission
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 \begin{equation*} \frac {1}{|V|}\sum _{v \in V}^{}{f(v)} \sim \sum _{w \in W}{a_w f(w)} \end{equation*} 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
- Dmitriy Bilyk, Feng Dai, and Ryan Matzke, The Stolarsky principle and energy optimization on the sphere, Constr. Approx. 48 (2018), no. 1, 31–60. MR 3825946, DOI 10.1007/s00365-017-9412-4
- Xavier Blanc and Mathieu Lewin, The crystallization conjecture: a review, EMS Surv. Math. Sci. 2 (2015), no. 2, 225–306. MR 3429164, DOI 10.4171/EMSS/13
- Amit Bermanis, Amir Averbuch, and Ronald R. Coifman, Multiscale data sampling and function extension, Appl. Comput. Harmon. Anal. 34 (2013), no. 1, 15–29. MR 2981331, DOI 10.1016/j.acha.2012.03.002
- Johann S. Brauchart and Peter J. Grabner, Distributing many points on spheres: minimal energy and designs, J. Complexity 31 (2015), no. 3, 293–326. MR 3325677, DOI 10.1016/j.jco.2015.02.003
- Fan R. K. Chung, Spectral graph theory, CBMS Regional Conference Series in Mathematics, vol. 92, Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 1997. MR 1421568
- P. Delsarte, J. M. Goethals, and J. J. Seidel, Spherical codes and designs, Geometriae Dedicata 6 (1977), no. 3, 363–388. MR 485471, DOI 10.1007/bf03187604
- Josef Dick and Friedrich Pillichshammer, Digital nets and sequences, Cambridge University Press, Cambridge, 2010. Discrepancy theory and quasi-Monte Carlo integration. MR 2683394, DOI 10.1017/CBO9780511761188
- Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Mathematics, vol. 1651, Springer-Verlag, Berlin, 1997. MR 1470456, DOI 10.1007/BFb0093404
- T. Erber and G. M. Hockney, Complex systems: equilibrium configurations of $N$ equal charges on a sphere $(2\leq N\leq 112)$, Advances in chemical physics, Vol. XCVIII, Adv. Chem. Phys., XCVIII, Wiley, New York, 1997, pp. 495–594. MR 1238214
- M. Gjoka, M. Kurant, C. T. Butts, and A. Markopoulou, Walking in Facebook: A case study of unbiased sampling of osns, INFOCOM, 2010 Proceedings IEEE, pp. 1–9, IEEE, 2010.
- V. Borodin, H. Snoussi, F. Hnaien, and N. Labadie, Signal processing on graphs: Case of sampling in Paley–Wiener spaces, Signal Processing 152 (2018), 130–140.
- Koji Fujiwara, Eigenvalues of Laplacians on a closed Riemannian manifold and its nets, Proc. Amer. Math. Soc. 123 (1995), no. 8, 2585–2594. MR 1257106, DOI 10.1090/S0002-9939-1995-1257106-5
- P. Hu and W. C. Lau, A survey and taxonomy of graph sampling, arXiv:1308.5865, 2013.
- L. Jin, Y. Chen, P. Hui, C. Ding, T. Wang, A. V. Vasilakos, B. Deng, and X. Li, Albatross sampling: Robust and effective hybrid vertex sampling for social graphs, Proceedings of the 3rd ACM International Workshop on MobiArch, pp. 11–16, ACM, 2011.
- L. Kuipers and H. Niederreiter, Uniform distribution of sequences, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0419394
- George C. Linderman and Stefan Steinerberger, Clustering with t-SNE, provably, SIAM J. Math. Data Sci. 1 (2019), no. 2, 313–332. MR 3955236, DOI 10.1137/18M1216134
- J. Lu, Y. Lu, X. Wang, X. Li, G. Linderman, C. Wu, X. Cheng, L. Mu, H. Zhang, J. Liu, M. Su, H. Zhao, E. Spatz, J. Spertus, F. Masoudi, H. Krumholz and L. Jiang, Prevalence, awareness, treatment, and control of hypertension in China: Data from 1.7 million adults in a population-based screening study (China PEACE Million Persons Project), The Lancet 390, pp. 2549–2558, 2017.
- Jianfeng Lu, Matthias Sachs, and Stefan Steinerberger, Quadrature points via heat kernel repulsion, Constr. Approx. 51 (2020), no. 1, 27–48. MR 4045735, DOI 10.1007/s00365-019-09471-4
- Isaac Pesenson, Sampling of Paley-Wiener functions on stratified groups, J. Fourier Anal. Appl. 4 (1998), no. 3, 271–281. MR 1650917, DOI 10.1007/BF02476027
- Isaac Pesenson, A sampling theorem on homogeneous manifolds, Trans. Amer. Math. Soc. 352 (2000), no. 9, 4257–4269. MR 1707201, DOI 10.1090/S0002-9947-00-02592-7
- Isaac Pesenson, Sampling in Paley-Wiener spaces on combinatorial graphs, Trans. Amer. Math. Soc. 360 (2008), no. 10, 5603–5627. MR 2415088, DOI 10.1090/S0002-9947-08-04511-X
- Isaac Z. Pesenson, Shannon sampling and weak Weyl’s law on compact Riemannian manifolds, Analysis and partial differential equations: perspectives from developing countries, Springer Proc. Math. Stat., vol. 275, Springer, Cham, 2019, pp. 207–218. MR 3923340, DOI 10.1007/978-3-030-05657-5_{1}3
- I. Pesenson, Average sampling and average splines on combinatorial graphs, arXiv:1901.08726, 2019.
- I. Pesenson, Weighted sampling and weighted interpolation on combinatorial graphs, arXiv:1905.02603, 2019.
- Isaac Z. Pesenson and Daryl Geller, Cubature formulas and discrete Fourier transform on compact manifolds, From Fourier analysis and number theory to Radon transforms and geometry, Dev. Math., vol. 28, Springer, New York, 2013, pp. 431–453. MR 2986970, DOI 10.1007/978-1-4614-4075-8_{2}1
- I. Z. Pesenson, M. Z. Pesenson, and H. Führ, Cubature formulas on combinatorial graphs, arXiv:1104.0963, 2011.
- A. H. Rasti, M. Torkjazi, R. Rejaie, N. Duffield, W. Willinger, and D. Stutzbach, Respondent-driven sampling for characterizing unstructured overlays, INFOCOM 2009, IEEE, 2009, pp. 2701–2705.
- A. Singer, From graph to manifold Laplacian: the convergence rate, Appl. Comput. Harmon. Anal. 21 (2006), no. 1, 128–134. MR 2238670, DOI 10.1016/j.acha.2006.03.004
- S. L. Sobolev, Cubature formulas on the sphere which are invariant under transformations of finite rotation groups, Dokl. Akad. Nauk SSSR 146 (1962), 310–313 (Russian). MR 0141225
- S. Steinerberger, Spectral limitations of quadrature rules and generalized spherical designs, IMRN (to appear).
- S. Steinerberger, Designs on graphs: Sampling, spectra, symmetries, J. Graph Theory (to appear).
- Kenneth B. Stolarsky, Sums of distances between points on a sphere. II, Proc. Amer. Math. Soc. 41 (1973), 575–582. MR 333995, DOI 10.1090/S0002-9939-1973-0333995-9
- Robert S. Strichartz, Half sampling on bipartite graphs, J. Fourier Anal. Appl. 22 (2016), no. 5, 1157–1173. MR 3547716, DOI 10.1007/s00041-015-9452-8
- Xiaohan Wang, Pengfei Liu, and Yuantao Gu, Local-set-based graph signal reconstruction, IEEE Trans. Signal Process. 63 (2015), no. 9, 2432–2444. MR 3341774, DOI 10.1109/TSP.2015.2411217
- J. P. Ward, F. J. Narcowich, and J. D. Ward, Interpolating splines on graphs for data science applications, arXiv:1806.10695, 2018.
Additional Information
- George C. Linderman
- Affiliation: Program in Applied Mathematics, Yale University, New Haven, Connecticut 06511
- MR Author ID: 1203460
- Email: george.linderman@yale.edu
- Stefan Steinerberger
- Affiliation: Department of Mathematics, Yale University, New Haven, Connecticut 06511
- MR Author ID: 869041
- ORCID: 0000-0002-7745-4217
- Email: stefan.steinerberger@yale.edu
- 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. - © Copyright 2020 American Mathematical Society
- Journal: Math. Comp. 89 (2020), 1933-1952
- MSC (2010): Primary 05C50, 05C70, 35P05, 65D32
- DOI: https://doi.org/10.1090/mcom/3515
- MathSciNet review: 4081923