Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Complete list of metadata
Contributor : Valeria Borodin Connect in order to contact the contributor
Submitted on : Tuesday, May 22, 2018 - 3:05:48 PM
Last modification on : Monday, June 27, 2022 - 3:05:09 AM



Valeria Borodin, Hichem Snoussi, Faicel Hnaien, Nacima Labadie. Signal processing on graphs: Case of sampling in Paley-Wiener spaces. Signal Processing, Elsevier, In press, ⟨10.1016/j.sigpro.2018.05.016⟩. ⟨emse-01797354⟩



Record views