Downsampling graphs using spectral theory

In this paper we present methods for downsampling datasets defined on graphs (i.e., graph-signals) by extending downsampling results for traditional N-dimensional signals. In particular, we study the spectral properties of k-regular bipartite graphs (K-RBG) and prove that downsampling in these graphs is governed by a Nyquist-like criteria. The results are useful for designing critically sampled filter-banks in various data-domains where the underlying relations between data locations can be represented by undirected graphs. In order to illustrate our results we represent images as a set of k-RBG graphs and apply our downsampling results to them. The results show that common 2-D lattice downsampling methods can be seen special cases of (K-RBG) based downsampling. Further we demonstrate new downsampling schemes for images with non-rectangular connectivity.