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.


Published in:
Ieee Transactions On Signal Processing, 63, 1, 182-191
Year:
2015
Publisher:
Piscataway, Ieee-Inst Electrical Electronics Engineers Inc
ISSN:
1053-587X
Keywords:
Laboratories:




 Record created 2015-02-20, last modified 2018-03-17

External links:
Download fulltextURL
Download fulltextURL
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)