Downsampling of Signals on Graphs via Maximum Spanning Trees
H.Q. Nguyen, M.N. Do
IEEE Transactions on Signal Processing, vol. 63, no. 1, pp. 182-191, January 1, 2015.
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.
@ARTICLE(http://bigwww.epfl.ch/publications/nguyen1501.html, AUTHOR="Nguyen, H.Q. and Do, M.N.", TITLE="Downsampling of Signals on Graphs via Maximum Spanning Trees", JOURNAL="{IEEE} Transactions on Signal Processing", YEAR="2015", volume="63", number="1", pages="182--191", month="January 1,", note="")