On the Generalized Sampling Expansion (GSE) for Graph Signals

In this work, we study the problem of distributed sampling and interpolation for perfect reconstruction of graph signals. In particular, we explore and present a generalization of Papoulis' classic generalized sampling expansion (GSE) to graph signals. We consider a single-time instance of a graph signal from a space of bandlimited graph signals, appropriately defined via the graph Fourier transform associated to the graph. For such bandlimited graph signals, we first identify a sufficient condition for perfect reconstruction via distributed sampler/interpolator pairs, in the spirit of the Shannon-Nyquist criterion. When this perfect reconstruction criteria is satisfied by the individual sampler rates, we then propose a distributed sampler/interpolator architecture which is shown to be achievable for the underlying bandlimited space. The results represent a unique generalization of Papoulis' generalized sampling expansion (GSE) paradigm to graph signals. Interestingly, our results show that such achievable schemes-comprising several pairs of individual sampler/interpolator pairs-are such that every component sampler can be essentially perceived as a concatenation of a pre-sampling filtering operation followed by binary vertex-sampling. The corresponding interpolator is then obtained as a linear transformation which is completely dependent on the vertex-sampling operation but is independent of the pre-sampling filter.