×

Partition of unity methods for signal processing on graphs. (English) Zbl 1473.65054

Summary: Partition of unity methods (PUMs) on graphs are simple and highly adaptive auxiliary tools for graph signal processing. Based on a greedy-type metric clustering and augmentation scheme, we show how a partition of unity can be generated in an efficient way on graphs. We investigate how PUMs can be combined with a local graph basis function (GBF) approximation method in order to obtain low-cost global interpolation or classification schemes. From a theoretical point of view, we study necessary prerequisites for the partition of unity such that global error estimates of the PUM follow from corresponding local ones. Finally, properties of the PUM as cost-efficiency and approximation accuracy are investigated numerically.

MSC:

65F99 Numerical linear algebra
05C90 Applications of graph theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)

Software:

Matlab; GBFlearn; GUPPY
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aronszajn, N., Theory of reproducing kernels, Trans. Am. Math. Soc., 68, 337-404 (1950) · Zbl 0037.20701
[2] Cavoretto, R.; De Rossi, A., Adaptive meshless refinement schemes for RBF-PUM collocation, Appl. Math. Lett., 90, 131-138 (2019) · Zbl 1419.65132
[3] Cavoretto, R.; De Rossi, A., Error indicators and refinement strategies for solving Poisson problems through a RBF partition of unity collocation scheme, Appl. Math. Comput., 369, 124824 (2020) · Zbl 1433.65020
[4] Cavoretto, R.; De Rossi, A.; Perracchione, E., Optimal selection of local approximants in RBF-PU interpolation, J. Sci. Comput., 74, 1-27 (2018) · Zbl 1383.65010
[5] Cavoretto, R.; De Rossi, A.; Mukhametzhanov, MS; Sergeyev, YD, On the search of the shape parameter in radial basis functions using univariate global optimization methods, J. Global Optim., 79, 305-327 (2021) · Zbl 1470.65012
[6] Cheng, C.; Jiang, Y.; Sun, Q., Spatially distributed sampling and reconstruction, Appl. Comput. Harm. Anal., 47, 1, 109-148 (2019) · Zbl 1435.94164
[7] Chung, FRK, Spectral Graph Theory (1997), Providence: American Mathematical Society, Providence · Zbl 0867.05046
[8] Erb, W.: Graph Signal Interpolation with Positive Definite Graph Basis Functions. arXiv:1912.02069 (2019)
[9] Erb, W.: Semi-Supervised Learning on Graphs with Feature-Augmented Graph Basis Functions. arXiv:2003.07646 (2020)
[10] Erb, W., Shapes of uncertainty in spectral graph theory, IEEE Trans. Inf. Theory, 67, 2, 1291-1307 (2021) · Zbl 1465.05101
[11] Fang, Q., Shin, C.E., Sun Q.: Polynomial control on weighted stability bounds and inversion norms of localized matrices on simple graph. To appear in J. Fourier Anal. Appl. (2021), doi:10.1007/s00041-021-09864-9.
[12] Fasshauer, GE, Meshfree Approximation Methods with Matlab (2007), Singapore: World Scientific, Singapore · Zbl 1123.65001
[13] Godsil, C.; Royle, G., Algebraic Graph Theory (2001), New York: Springer, New York · Zbl 0968.05002
[14] Gonzalez, TF, Clustering to minimize the maximum intercluster distance, Theor. Comput. Sci., 38, 293-306 (1985) · Zbl 0567.62048
[15] Griebel, M.; Schweitzer, MA, A particle-partition of unity method for the solution of elliptic, parabolic and hyperbolic PDE, SIAM J. Sci. Comp., 22, 3, 853-890 (2000) · Zbl 0974.65090
[16] Har-Peled, S., Geometric Approximation Algorithms (2011), Boston: American Mathematical Society, Boston · Zbl 1230.68215
[17] Hochbaum, DS; Shmoys, DB, A best possible heuristic for the \(k\)-center problem, Math. Oper. Res., 10, 2, 180-184 (1985) · Zbl 0565.90015
[18] Horn, RA; Johnson, CR, Matrix Analysis (1985), Cambridge: Cambridge University Press, Cambridge · Zbl 0576.15001
[19] Kondor, R.I., Lafferty, J.: Diffusion kernels on graphs and other discrete input spaces. in Proc. of the 19th. Intern. Conf. on Machine Learning ICML02, pp. 315-322 (2002)
[20] Larsson, E.; Shcherbakov, V.; Heryudono, A., A least squares radial basis function partition of unity method for solving PDEs, SIAM J. Sci. Comput., 39, 6, A2538-A2563 (2017) · Zbl 1377.65156
[21] Melenk, J.M., Babu \(\check{s}\) ka, I.: The partition of unity finite element method: Basic theory and applications. Comput. Methods Appl. Mech. Eng. 139(1-4), 289-314 (1996) · Zbl 0881.65099
[22] Ortega, A., Frossard, P., Kova \(\check{c}\) evi \(\acute{c} \), J., Moura, J.M.F., Vandergheynst, P.: Graph signal processing: overview, challenges, and applications. Proce. IEEE 106(5), 808-828 (2018)
[23] Pesenson, I.Z.: Sampling by averages and average splines on Dirichlet spaces and on combinatorial graphs. To appear in: Hirn M., et al. editors: Excursions in Harmonic Analysis, Volume 6, book series Applied and Numerical Harmonic Analysis, Birkhäuser-Springer (2021) · Zbl 1481.94074
[24] Pesenson, IZ, Sampling in Paley-Wiener spaces on combinatorial graphs, Trans. Am. Math. Soc., 360, 10, 5603-5627 (2008) · Zbl 1165.42010
[25] Pesenson, IZ, Variational splines and Paley-Wiener spaces on combinatorial graphs, Constr. Approx., 29, 1, 1-21 (2009) · Zbl 1180.42026
[26] Pesenson, IZ; Pesenson, MZ, Graph signal sampling and interpolation based on clusters and averages, J. Fourier Anal. Appl., 27, 39 (2021) · Zbl 1462.42057
[27] Rifkin, R.; Yeo, G.; Poggio, T., Regularized least-squares classification. Nato Science Series Sub Series III, Comput. Syst. Sci., 190, 131-154 (2003)
[28] Romero, D.; Ma, M.; Giannakis, GB, Kernel-based reconstruction of graph signals, IEEE Trans. Signal Process., 65, 3, 764-778 (2017) · Zbl 1414.94514
[29] Rossi, R.A., Ahmed, N.K.: The Network Data Repository with Interactive Graph Analytics and Visualization. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (2015), http://networkrepository.com
[30] Schaback, R., Wendland, H.: Approximation by Positive Definite Kernels. In Advanced Problems in Constructive Approximation, Birkhäuser Verlag, Basel (2003), 203-222 · Zbl 1046.41011
[31] Schölkopf, B.; Smola, A., Learning with Kernels (2002), Cambridge: MIT Press, Cambridge · Zbl 1019.68094
[32] Shepard, D.: A two-dimensional interpolation function for irregularly-spaced data. in Proceedings of the 1968 23rd ACM National Conference, ACM’68, New York, NY, USA (1968), 517-524
[33] Shuman, DI; Ricaud, B.; Vandergheynst, P., Vertex-frequency analysis on graphs, Appl. Comput. Harm. Anal., 40, 2, 260-291 (2016) · Zbl 1403.94031
[34] Smola, A., Kondor. R.: Kernels and regularization on graphs. In Learning Theory and Kernel Machines. Springer, Berlin Heidelberg, pp. 144-158 (2003) · Zbl 1274.68351
[35] Stanković, L., Daković, L., Sejdić, E.: Introduction to Graph Signal Processing, pp. 3-108. Springer, In Vertex-Frequency Analysis of Graph Signals (2019) · Zbl 1435.94062
[36] von Luxburg, U., A tutorial on spectral clustering, Stat. Comput., 17, 395-416 (2007)
[37] Wahba, G.: Spline Models for Observational Data. CBMS-NSF Regional Conference Series in Applied Mathematics, volume 59, SIAM, Philadelphia (1990) · Zbl 0813.62001
[38] Ward, JP; Narcowich, FJ; Ward, JD, Interpolating splines on graphs for data science applications, Appl. Comput. Harm. Anal., 49, 2, 540-557 (2020) · Zbl 1442.41001
[39] Wendland, H.: Fast evaluation of radial basis functions: Methods based on partition of unity. In: C.K. Chui et al. (Eds.), Approximation Theory X: Wavelets, Splines, and Applications (2002), 473-483 · Zbl 1031.65022
[40] Wendland, H., Scattered Data Approximation (2005), Cambridge: Cambridge University Press, Cambridge · Zbl 1075.65021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.