Finding Representative Sampling Subsets on Graphs

Abstract

In this work, we deal with the problem of reconstructing a complete bandlimited graph signal from partially sampled noisy measurements. For a known graph structure, some efficient centralized algorithms are proposed to partition the nodes of the graph into disjoint subsets such that sampling the graph signal from any of these subsets leads to a sufficiently accurate reconstruction. Furthermore, we consider the situation when the graph has a massive size, where processing the data centrally is impractical anymore. To overcome this issue, a distributed framework is proposed that allows us to implement the centralized algorithms in a parallelized fashion. Finally, we provide numerical simulation results on synthetic and real-world data to show that our proposals outperform state-of-the-art node partitioning techniques.