Discrete uncertainty principles on graphs

Abstract

This paper advances a new way to formulate the uncertainty principle for graphs, by using a non-local measure based on the notion of sparsity. The uncertainty principle is formulated based on the total number of nonzero elements in the signal and its corresponding graph Fourier transform (GFT). By providing a lower bound for this total number, it is shown that a nonzero graph signal and its GFT cannot be arbitrarily sparse simultaneously. The theoretical bound on total sparsity is derived. For several real-world graphs this bound can actually be achieved by choosing the graph signals to be appropriate eigenvectors of the graph.

Additional details