APSIPA Transactions on Signal and Information Processing > Vol 7 > Issue 1

Global and local uncertainty principles for signals on graphs

Nathanael Perraudin, Swiss Federal Institute of Technology (EPFL and ETH Zürich), Switzerland, nathanael.perraudin@epfl.ch , Benjamin Ricaud, Swiss Federal Institute of Technology (EPFL), Switzerland, David I Shuman, Statistics, and Computer Science, Macalester College, USA, Pierre Vandergheynst, Swiss Federal Institute of Technology (EPFL), Switzerland
 
Suggested Citation
Nathanael Perraudin, Benjamin Ricaud, David I Shuman and Pierre Vandergheynst (2018), "Global and local uncertainty principles for signals on graphs", APSIPA Transactions on Signal and Information Processing: Vol. 7: No. 1, e3. http://dx.doi.org/10.1017/ATSIP.2018.2

Publication Date: 02 Apr 2018
© 2018 Nathanael Perraudin, Benjamin Ricaud, David I Shuman and Pierre Vandergheynst
 
Subjects
 
Keywords
Signal processing on graphsUncertainty principleLocal uncertaintyTime-frequency analysisLocalizationConcentration boundNon-uniform random sampling
 

Share

Open Access

This is published under the terms of the Creative Commons Attribution licence.

Downloaded: 2026 times

In this article:
I. INTRODUCTION 
II. NOTATION AND GRAPH SIGNAL CONCENTRATION 
III. GLOBAL UNCERTAINTY PRINCIPLES RELATING THE CONCENTRATION OF GRAPH SIGNALS IN TWO DOMAINS 
IV. GRAPH SIGNAL PROCESSING OPERATORS AND DICTIONARIES 
V. GLOBAL UNCERTAINTY PRINCIPLES BOUNDING THE CONCENTRATION OF THE ANALYSIS COEFFICIENTS OF A GRAPH SIGNAL IN A TRANSFORM DOMAIN 
VI. LOCAL UNCERTAINTY PRINCIPLES FOR SIGNALS ON GRAPHS 
VII. CONCLUSION 

Abstract

Uncertainty principles such as Heisenberg's provide limits on the time-frequency concentration of a signal, and constitute an important theoretical tool for designing linear signal transforms. Generalizations of such principles to the graph setting can inform dictionary design, lead to algorithms for reconstructing missing information via sparse representations, and yield new graph analysis tools. While previous work has focused on generalizing notions of spreads of graph signals in the vertex and graph spectral domains, our approach generalizes the methods of Lieb in order to develop uncertainty principles that provide limits on the concentration of the analysis coefficients of any graph signal under a dictionary transform. One challenge we highlight is that the local structure in a small region of an inhomogeneous graph can drastically affect the uncertainty bounds, limiting the information provided by global uncertainty principles. Accordingly, we suggest new notions of locality, and develop local uncertainty principles that bound the concentration of the analysis coefficients of each atom of a localized graph spectral filter frame in terms of quantities that depend on the local structure of the graph around the atom's center vertex. Finally, we demonstrate how our proposed local uncertainty measures can improve the random sampling of graph signals.

DOI:10.1017/ATSIP.2018.2