  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.
