  In this paper, we provide a Graph Fourier Transform based approach to
downsample signals on graphs. For bandlimited signals on a graph, a test is
provided to identify whether signal reconstruction is possible from the given
downsampled signal. Moreover, if the signal is not bandlimited, we provide a
quality measure for comparing different downsampling schemes. Using this
quality measure, we propose a greedy downsampling algorithm. Most of the
prevailing approaches consider undirected graphs, and exploit the topological
properties of the graph in order to downsample the grid, while the proposed
method exploits spectral properties of graph signals, and is applicable to
directed graphs, undirected graphs, and graphs with negative edge-weights. We
provide several experiments demonstrating our downsampling scheme, and compare
our quality measure with measures like normalized cuts.
