We study the problem of selecting the best sampling set for bandlimited
reconstruction of signals on graphs. A frequency domain representation for
graph signals can be defined using the eigenvectors and eigenvalues of
variation operators that take into account the underlying graph connectivity.
Smoothly varying signals defined on the nodes are of particular interest in
various applications, and tend to be approximately bandlimited in the frequency
basis. Sampling theory for graph signals deals with the problem of choosing the
best subset of nodes for reconstructing a bandlimited signal from its samples.
Most approaches to this problem require a computation of the frequency basis
(i.e., the eigenvectors of the variation operator), followed by a search
procedure using the basis elements. This can be impractical, in terms of
storage and time complexity, for real datasets involving very large graphs. We
circumvent this issue in our formulation by introducing quantities called graph
spectral proxies, defined using the powers of the variation operator, in order
to approximate the spectral content of graph signals. This allows us to
formulate a direct sampling set selection approach that does not require the
computation and storage of the basis elements. We show that our approach also
provides stable reconstruction when the samples are noisy or when the original
signal is only approximately bandlimited. Furthermore, the proposed approach is
valid for any choice of the variation operator, thereby covering a wide range
of graphs and applications. We demonstrate its effectiveness through various
numerical experiments.

本文研究了在图上进行带限重建的最佳抽样集的选择问题，通过引入称为图谱代理的数量来近似图信号的频谱内容，提出了一种不需要计算和存储基元素的直接抽样集选择方法，并证明了该方法在嘈杂数据或原始信号仅近似带限时提供稳定的重建能力，该方法适用于各种图、各种应用，并通过各种数值实验展示了其有效性。