A Distance-Based Formulation for Sampling Signals on Graphs

Abstract

We consider the problem of sampling signals defined on the nodes of a graph. This problem arises in many contexts where the data is not structured and needs to be reconstructed from a few samples. While other graph signal sampling techniques have been recently developed in the literature, these are based on graph spectral concepts. In contrast, here we develop a method that incorporates distances between graph vertices, and thus can provide additional insights about desirable properties of sampling sets relative to state-of-the-art techniques. We compare the accuracy of our method with two other fast methods in the literature and show that it achieves similar performance.