Finding Representative Sampling Subsets on Graphs via Submodularity

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, an efficient greedy algorithm is presented to partition the graph nodes into disjoint subsets such that sampling the graph signal from any subset leads to a sufficiently accurate reconstruction. Furthermore, we consider a scenario where the graph is massive and data processing centrally is no longer practical. To overcome this issue, a distributed framework is proposed that allows us to implement partitioning algorithms in a parallelized fashion. Finally, we provide numerical simulation results on synthetic and real-world data to show that our proposals outperform the state-of-the-art.