  Sampling is a fundamental topic in graph signal processing, having found
applications in estimation, clustering, and video compression. In contrast to
traditional signal processing, the irregularity of the signal domain makes
selecting a sampling set non-trivial and hard to analyze. Indeed, though
conditions for graph signal interpolation from noiseless samples exist, they do
not lead to a unique sampling set. The presence of noise makes choosing among
these sampling sets a hard combinatorial problem. Although greedy sampling
schemes are commonly used in practice, they have no performance guarantee. This
work takes a twofold approach to address this issue. First, universal
performance bounds are derived for the Bayesian estimation of graph signals
from noisy samples. In contrast to currently available bounds, they are not
restricted to specific sampling schemes and hold for any sampling sets. Second,
this paper provides near-optimal guarantees for greedy sampling by introducing
the concept of approximate submodularity and updating the classical greedy
bound. It then provides explicit bounds on the approximate supermodularity of
the interpolation mean-square error showing that it can be optimized with
worst-case guarantees using greedy search even though it is not supermodular.
Simulations illustrate the derived bound for different graph models and show an
application of graph signal sampling to reduce the complexity of kernel
principal component analysis.
