A Framework of Adaptive Multiscale Wavelet Decomposition for Signals on Undirected Graphs

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

2 Scopus Citations
View graph of relations

Author(s)

  • Xianwei Zheng
  • Yuan Yan Tang
  • Jiantao Zhou

Detail(s)

Original languageEnglish
Article number8632761
Pages (from-to)1696-1711
Journal / PublicationIEEE Transactions on Signal Processing
Volume67
Issue number7
Online published1 Feb 2019
Publication statusPublished - 1 Apr 2019

Abstract

The state-of-the-art graph wavelet decomposition was constructed by maximum spanning tree (MST)-based downsampling and two-channel graph wavelet filter banks. In this work, we first show that: 1) the existing MST-based downsampling could become unbalanced, i.e., the sampling rate is far from 1/2, which eventually leads to low representation efficiency of the wavelet decomposition; and 2) not only low-pass components, but also some high-pass ones can be decomposed to potentially achieve better decomposition performance. Based on these observations, we propose a new framework of adaptive multiscale graph wavelet decomposition for signals defined on undirected graphs. Specifically, our framework consists of two phases. Phase 1, called pre-processing, addresses the downsampling unbalance issues. We design maximal decomposition level estimation, unbalance detection, and unbalance reduction algorithms such that the downsampling rates of all levels are close to 1/2. Phase 2 concerns about adaptively finding low- or high-pass components that are worthy to be decomposed to improve the compactness of the decomposition. We suggest a graph signal Shannon-entropy-based adaptive decomposition algorithm. With applications on synthetic and real-world graph signals, we demonstrate that our framework provides better performance in terms of downsampling balance and signal compression, compared with other graph wavelet decomposition methods.

Research Area(s)

  • adaptive multiscale decomposition, downsampling unbalance, Graph signal, graph signal Shannon entropy, maximum spanning tree (MST)

Citation Format(s)

A Framework of Adaptive Multiscale Wavelet Decomposition for Signals on Undirected Graphs. / Zheng, Xianwei; Tang, Yuan Yan; Zhou, Jiantao.

In: IEEE Transactions on Signal Processing, Vol. 67, No. 7, 8632761, 01.04.2019, p. 1696-1711.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal