Nguyen, Ha Q.Do, Minh N.2015-02-202015-02-202015-02-20201510.1109/Tsp.2014.2369013https://infoscience.epfl.ch/handle/20.500.14299/111342WOS:000346630900015Downsampling 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.Bipartite approximationdownsampling on graphsgraph multiresolutiongraph wavelet filter banksmax-cutmaximum spanning treesignal processing on graphstext::journal::journal article::research article