In many applications, the observations can be represented as a signal defined
over the vertices of a graph. The analysis of such signals requires the
extension of standard signal processing tools. In this work, first, we provide
a class of graph signals that are maximally concentrated on the graph domain
and on its dual. Then, building on this framework, we derive an uncertainty
principle for graph signals and illustrate the conditions for the recovery of
band-limited signals from a subset of samples. We show an interesting link
between uncertainty principle and sampling and propose alternative signal
recovery algorithms, including a generalization to frame-based reconstruction
methods. After showing that the performance of signal recovery algorithms is
significantly affected by the location of samples, we suggest and compare a few
alternative sampling strategies. Finally, we provide the conditions for perfect
recovery of a useful signal corrupted by sparse noise, showing that this
problem is also intrinsically related to vertex-frequency localization
properties.

本研究提出了一类集中在图形域和图形对偶上的图形信号，并基于此提出了图形信号的不确定性原理，探讨了从样本子集中恢复带限信号的条件和提出了替代信号恢复算法，包括基于帧的重构方法，同时提出了几种替代采样策略和相关的条件和反演方法，最后展示了完美恢复被稀疏噪声损坏的信号与顶点 - 频率定位特性之间的内在相关性。