Signal processing on graphs: Case of sampling in Paley-Wiener spaces

Given a weighted undirected graph, this paper focuses on the sampling problem of uniquely recovering Paley-Wiener functions from a sampled set of vertices. In accordance with the measures of connectivity introduced by Pesenson [30], we address two optimization problems related to discrete sampling on graphs via the so-called uniqueness sets, namely: (i) determining the maximal bandwidth of the signal, which can be perfectly reconstructed by a sampling subset of vertices with a cardinality smaller than a given value; (ii) finding the minimal sampling subset of graph vertices, which guarantees the complete reconstruction of at least a required signal bandwidth. In this sense, two integer linear programs are provided together with their complexity and solution approach. Since the uniqueness sets are described in terms of Poincaré-Wirtinger type inequalities, the used approximation of the true cut-off-frequency KS is only a lower bound of the Poincaré constant, through which the removable subset of vertices is characterized. In spite of this limitation, conducted computational experiments illustrate, however, a considerable decision support and a practical interest, as well as, highlight the pertinence of the used measure KS against the true cut-off-frequency for signal sampling on graphs.