Sampling of Graph Signals With Successive Local Aggregations

DOI10.1109/TSP.2015.2507546MaRDI QIDQ4618297zbMATH OpenOpenAlexFDO

Authors Antonio G. Marques, Santiago Segarra, Alejandro Ribeiro, G. Leus

Publication date 7 February 2019

Published in IEEE Transactions on Signal Processing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Abstract: A new scheme to sample signals defined in the nodes of a graph is proposed. The underlying assumption is that such signals admit a sparse representation in a frequency domain related to the structure of the graph, which is captured by the so-called graph-shift operator. Most of the works that have looked at this problem have focused on using the value of the signal observed at a subset of nodes to recover the signal in the entire graph. Differently, the sampling scheme proposed here uses as input observations taken at a single node. The observations correspond to sequential applications of the graph-shift operator, which are linear combinations of the information gathered by the neighbors of the node. When the graph corresponds to a directed cycle (which is the support of time-varying signals), our method is equivalent to the classical sampling in the time domain. When the graph is more general, we show that the Vandermonde structure of the sampling matrix, which is critical to guarantee recovery when sampling time-varying signals, is preserved. Sampling and interpolation are analyzed first in the absence of noise and then noise is considered. We then study the recovery of the sampled signal when the specific set of frequencies that is active is not known. Moreover, we present a more general sampling scheme, under which, either our aggregation approach or the alternative approach of sampling a graph signal by observing the value of the signal at a subset of nodes can be both viewed as particular cases. The last part of the paper presents numerical experiments that illustrate the results developed through both synthetic graph signals and a real-world graph of the economy of the United States.

Cited in

(14)

• Scalable Graph Coreset Selection via Greedy Sampling
• Graph signal sampling and interpolation based on clusters and averages
• Data Analytics on Graphs Part II: Signals on Graphs
• Sparse graphical designs via linear programming
• Sparse graph signals -- uncertainty principles and recovery
• Graphical designs and gale duality
• Approximation theorems on graphs
• Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
• The dual graph shift operator: identifying the support of the frequency domain
• Two subspace methods for frequency sparse graph signals
• scientific article; zbMATH DE number 7626710 (Why is no real title available?)
• Transferability of spectral graph convolutional neural networks
• Robust estimation of smooth graph signals from randomized space-time samples
• Local measurement and diffusion reconstruction for signals on a weighted graph

This page was built for publication: Sampling of Graph Signals With Successive Local Aggregations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4618297)