Signal processing on graphs: Case of sampling in Paley-Wiener spaces - Mines Saint-Étienne Access content directly
Journal Articles Signal Processing Year : 2018

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.
No file

Dates and versions

emse-01797354 , version 1 (22-05-2018)



Valeria Borodin, Hichem Snoussi, Faicel Hnaien, Nacima Labadie. Signal processing on graphs: Case of sampling in Paley-Wiener spaces. Signal Processing, 2018, 152, pp.130-140. ⟨10.1016/j.sigpro.2018.05.016⟩. ⟨emse-01797354⟩
117 View
0 Download



Gmail Mastodon Facebook X LinkedIn More