Pesenson, Isaac Z. and Pesenson, Meyer Z. (2021) Graph Signal Sampling and Interpolation Based on Clusters and Averages. Journal of Fourier Analysis and Applications, 27 (3). Art. No. 39. ISSN 1069-5869. doi:10.1007/s00041-021-09828-z. https://resolver.caltech.edu/CaltechAUTHORS:20210429-144553526
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20210429-144553526
Abstract
We consider a disjoint cover (partition) of an undirected weighted finite or infinite graph G by J connected subgraphs (clusters) {S_j}_(j∈J) and select functions ψ_j on each of the clusters. For a given signal f on G the set of its weighted average values samples is defined via inner products {⟨f,ψj⟩}_(j∈J). The main results of the paper are based on Poincare-type inequalities that we introduce and prove. These inequalities provide an estimate of the norm of the signal f on the entire graph G from sets of samples of f and its local gradient on each of the subgraphs. This allows us to establish discrete Plancherel-Polya-type inequalities (or Marcinkiewicz-Zigmund-type or frame inequalities) for signals whose gradients satisfy a Bernstein-type inequality. These results enable the development of a sampling theory for signals on undirected weighted finite or infinite graphs. For reconstruction of the signals from their samples an interpolation theory by weighted average variational splines is developed. Here by a weighted average variational spline we understand a minimizer of a discrete Sobolev norm which takes on the prescribed weighted average values on a set of clusters (in particular, just values on a subset of vertices). Although our approach is applicable to general graphs it’s especially well suited for finite and infinite graphs with multiple clusters. Such graphs are known as community graphs and they find many important applications in materials science, engineering, computer science, economics, biology, and social studies.
Item Type: | Article | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
Additional Information: | © 2021 Springer Nature. Received 01 December 2020. Revised 12 February 2021. Accepted 14 February 2021. Published 21 April 2021. MZP was supported by the U.S. Department of Energy, Office of Science, Office of Basic Energy Sciences, under Award DE-SC0020383. | |||||||||
Funders: |
| |||||||||
Subject Keywords: | Combinatorial graph; combinatorial Laplace operator; Poincaré-type inequality; Paley-Wiener spaces; Plancherel-Polya-type inequality; splines; interpolation | |||||||||
Issue or Number: | 3 | |||||||||
Classification Code: | Mathematics Subject Classification: 42C99; 05C99; 94A20; 41A15; Secondary 94A12 | |||||||||
DOI: | 10.1007/s00041-021-09828-z | |||||||||
Record Number: | CaltechAUTHORS:20210429-144553526 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20210429-144553526 | |||||||||
Official Citation: | Pesenson, I.Z., Pesenson, M.Z. Graph Signal Sampling and Interpolation Based on Clusters and Averages . J Fourier Anal Appl 27, 39 (2021). https://doi.org/10.1007/s00041-021-09828-z | |||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | |||||||||
ID Code: | 108883 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | George Porter | |||||||||
Deposited On: | 30 Apr 2021 15:12 | |||||||||
Last Modified: | 16 Nov 2021 19:33 |
Repository Staff Only: item control page