Graph Sampling with and Without Input Priors

Abstract

In this paper the focus is on sampling and reconstruction of signals supported on nodes of arbitrary graphs or arbitrary signals that may be represented using graphs, where we extend concepts from generalized sampling theory to the graph setting. To recover such signals from a given set of samples, we develop algorithms that incorporate prior knowledge on the original signal when available such as smoothness or subspace priors related to the underlying graph. For reconstructing arbitrary signals, we constrain the reconstruction to the graph, and provide a consistent reconstruction method, in which both the reconstructed signal and the input yield exactly the same measurements. Given a set of graph frequency domain samples, the sampling and interpolation operations may be efficiently implemented using linear shift-invariant graph filters.