Efficient Node Selection Strategy for Sampling Bandlimited Signals on Graphs

Abstract

This paper addresses the problem of selecting an optimal sampling set for K-bandlimited signals on graphs. The proposed sampling method is based on two proposed notions of correlation quantity and effective node. First, we clarify the relationship between the uniqueness set and the effective node, and subsequently show that the effective node set selected by space division constitutes a uniqueness set for K-bandlimited signals, thereby obtaining an efficient reconstruction method for K-bandlimited signals. Then, to reduce the effect of noise, the proposed method finds an optimal sampling set by selecting the best node with the maximum correlation quantity in each node selection. Furthermore, we show that the proposed method can be performed for sampling K-bandlimited signals by using an estimation eigenspace without computing the eigendecomposition of a variation operator. Finally, we compare our approach with other existing sampling approaches through comparisons of reconstruction error and running time to evaluate its performance.