Uncertainty Principle and Sampling of Signals Defined on Graphs

arXiv1512.00775MaRDI QIDQ6267983FDOQ6267983

Authors: Mikhail Tsitsvero, Sergio Barbarossa, Paolo Di Lorenzo 

Publication date: 2 December 2015

Abstract: In many applications, from sensor to social networks, gene regulatory networks or big data, observations can be represented as a signal defined over the vertices of a graph. Building on the recently introduced Graph Fourier Transform, the first contribution of this paper is to provide an uncertainty principle for signals on graph. As a by-product of this theory, we show how to build a dictionary of maximally concentrated signals on vertex/frequency domains. Then, we establish a direct relation between uncertainty principle and sampling, which forms the basis for a sampling theorem of signals defined on graph. Based on this theory, we show that, besides sampling rate, the samples' location plays a key role in the performance of signal recovery algorithms. Hence, we suggest a few alternative sampling strategies and compare them with recently proposed methods.

This page was built for publication: Uncertainty Principle and Sampling of Signals Defined on Graphs

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