Global and Local Uncertainty Principles for Signals on Graphs

View Researcher's Other Codes

MATLAB code for the paper: “Global and local uncertainty principles for signals on graphs”.

Disclaimer: The provided code links for this paper are external links. Science Nest has no responsibility for the accuracy, legality or content of these links. Also, by downloading this code(s), you agree to comply with the terms of use as set out by the author(s) of the code(s).

Please contact us in case of a broken link from here

Authors Nathanael Perraudin, Benjamin Ricaud, David I Shuman, and Pierre Vandergheynst
Journal/Conference Name APSIPA Transactions on Signal and Information Processing
Paper Category
Paper 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.
Date of publication 2018
Code Programming Language MATLAB

Copyright Researcher 2022