Downsampling of signals on graphs via maximum spanning trees

Ha Q. Nguyen, Minh N. Do

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Article number6951462
Pages (from-to)182-191
Number of pages10
JournalIEEE Transactions on Signal Processing
Issue number1
StatePublished - Jan 1 2015


  • Bipartite approximation
  • Downsampling on graphs
  • Graph multiresolution
  • Graph wavelet filter banks
  • Max-cut
  • Maximum spanning tree
  • Signal processing on graphs

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing


Dive into the research topics of 'Downsampling of signals on graphs via maximum spanning trees'. Together they form a unique fingerprint.

Cite this