Signals on Graphs: Uncertainty Principle and Sampling

By Mikhail Tsitsvero, Sergio Barbarossa, P. Lorenzo. IEEE Transactions on Signal Processing, 2015

347 citations recorded by the source corpus.

In many applications, the observations can be represented as a signal defined over the vertices of a graph. The analysis of such signals requires the extension of standard signal processing tools. In this paper, first, we provide a class of graph signals that are maximally concentrated on the graph domain and on its dual. Then, building on this framework, we derive an uncertainty principle for graph signals and illustrate the conditions for the recovery of band-limited signals from a subset of samples. We show an interesting link between uncertainty principle and sampling and propose alternative signal recovery algorithms, including a generalization to frame-based reconstruction methods. After showing that the performance of signal recovery algorithms is significantly affected by the location of samples, we suggest and compare a few alternative sampling strategies. Finally, we provide the conditions for perfect recovery of a useful signal corrupted by sparse noise, showing that this problem is also intrinsically related to vertex-frequency localization properties.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/880068376c5f0535778b669b170622924fcd70a1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Statistical and Nonlinear Physics

Citations in the corpus

Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies (2015, background): “Sampling theory of graph signals similarly deals with the problem of recovering a signal from its samples on a subset of nodes of the graph.”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “More recently, [134] has shown that for graph signals it is in fact possible to have compact support in both spectral and vertex domain (something that can never occur in conventional signal processing).”
Global and Local Uncertainty Principles for Signals on Graphs (2016, background): “An example of a recent work from the graph signal processing literature that falls into this family is [42], in which Tsitsvero et al.”
Compressive Spectral Clustering (2016, methodology): “There has been recently a surge of interest around adapting classical sampling theorems to such bandlimited graph signals (Anis et al., 2015; Chen et al., 2015; Marques et al., 2015; Tsitsvero et al., 2015).”
Convolutional Neural Network Architectures for Signals Supported on Graphs (2018, background): “Apart from the challenge of selecting sampling matrices for graphs – see (16) and [7], [28]–[30] –, this does not require any further modification to (5).”