Sampling theory for graph signals

We propose a sampling theory for finite-dimensional vectors with a generalized bandwidth restriction, which follows the same paradigm of the classical sampling theory. We use this general result to derive a sampling theorem for bandlimited graph signals in the framework of discrete signal processing on graphs. By imposing a specific structure on the graph, graph signals reduce to finite discrete-time or discrete-space signals, effectively ensuring that the proposed sampling theory works for such signals. The proposed sampling theory is applicable to both directed and undirected graphs, the assumption of perfect recovery is easy both to check and to satisfy, and, under that assumption, perfect recovery is guaranteed without any probability constraints or any approximation.