Greedy Local-set Based Sampling and Reconstruction for Band-limited Graph Signals

Signal processing on graphs extends signal processing concepts and methodologies from the classical signal processing theory to data indexed by general graphs. Downsampling on graphs is used to efficiently extract valuable information from the massive datasets for reducing the volume of big data. Band-limited graph signal can be reconstructed from sampled data on a sub-set of the vertices by exploiting its spatial correlation. In this paper, we propose a greedy graph signal downsampling method and corresponding reconstruction strategy. We compare the proposed downsampling algorithm with other correlative algorithms on various graph structures for analyzing the reconstruction performance and the robustness, using both synthetic data and real world data. The experimental results demonstrate that the proposed greedy downsampling strategy can achieve satisfactory reconstruction quality and lower sampling rate compared to the correlative algorithms.