A Caltech Library Service

Graph Signal Sampling and Interpolation Based on Clusters and Averages

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.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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:
URLURL TypeDescription ReadCube access
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.
Funding AgencyGrant Number
Department of Energy (DOE)DE-SC0020383
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
Record Number:CaltechAUTHORS:20210429-144553526
Persistent URL:
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).
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:108883
Deposited By: George Porter
Deposited On:30 Apr 2021 15:12
Last Modified:16 Nov 2021 19:33

Repository Staff Only: item control page