SAMPLING LARGE DATA ON GRAPHS

We consider the problem of sampling from data defined on the nodes of a weighted graph, where the edge weights capture the data corre-lation structure. As shown recently, using spectral graph theory one can define a cut-off frequency for the bandlimited graph signals that can be reconstructed from a given set of samples (i.e., graph nodes). In this work, we show how this cut-off frequency can be computed exactly. Using this characterization, we provide efficient algorithms for finding the subset of nodes of a given size with the largest cut-off frequency and for finding the smallest subset of nodes with a given cut-off frequency. In addition, we study the performance of random uniform sampling when compared to the centralized optimal sam-pling provided by the proposed algorithms. Index Terms — Sampling, Graph signal processing, cut-off fre-quency, spectral graph theor