Downsampling of Signals on Graphs Via Maximum Spanning Trees
Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approximated by a maximum spanning tree (MST) that naturally defines a graph multiresolution. This MST-based method significantly outperforms the two previous downsampling schemes, coloring-based and SVD-based, on both random and specific graphs in terms of computations and partition efficiency quantified by the graph cuts. The benefit of using MST-based downsampling for recently developed critical-sampling graph wavelet transforms in compression of graph signals is demonstrated.
- URL: http://bigwww.epfl.ch/publications/nguyen1501.html
- URL: http://bigwww.epfl.ch/publications/nguyen1501.pdf
- URL: http://bigwww.epfl.ch/publications/nguyen1501.ps
Record created on 2015-02-20, modified on 2016-08-09