New paper: Global and Local Uncertainty Principles for Signals on Graphs

I’m particularly proud to present this work since we have been working on it for almost 4 years. It started with my master thesis in 2012 before any publications on graph uncertainty were out. Even though there were new coming articles dealing with uncertainty every few months, we kept working our initial idea.

In this paper, we generalize some classical uncertainty principles for signals residing on Euclidean domains to uncertainty principles for signals residing on weighted graphs. To do so, we use generalizations of time-frequency transforms and ambiguity functions. Contrary to the classical setting, the uncertainty in the graph setting depends on the localization of the signal, leading to the new concept of “local uncertainty.”

ArXiv link: http://arxiv.org/abs/1603.03030


Uncertainty principles such as Heisenberg’s provide limits on the time-frequency concentration of a signal, and constitute an important theoretical tool for designing and evaluating linear signal transforms. Generalizations of such principles to the graph setting can inform dictionary design for graph signals, lead to algorithms for reconstructing missing information from graph signals via sparse representations, and yield new graph analysis tools. While previous work has focused on generalizing notions of spreads of a graph signal in the vertex and graph spectral domains, our approach is to generalize 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 whose atoms are jointly localized in the vertex and graph spectral domains. One challenge we highlight is that due to the inhomogeneity of the underlying graph data domain, the local structure in a single small region of the graph can drastically affect the uncertainty bounds for signals concentrated in different regions of the graph, limiting the information provided by global uncertainty principles. Accordingly, we suggest a new way to incorporate a notion 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 center vertex of the given atom. Finally, we demonstrate how our proposed local uncertainty measures can improve the random sampling of graph signals.