eGHWT: The extended Generalized Haar-Walsh Transform (with Y. Shao), Journal of Mathematical Imaging and Vision, vol. 64, no. 3, pp. 261-283, 2022.
Abstract
Extending computational harmonic analysis tools from the classical setting of
regular lattices to the more general setting of graphs and networks is very
important and much research has been done recently.
The Generalized Haar-Walsh Transform (GHWT) developed by Irion and Saito (2014)
is a multiscale transform for signals on graphs, which is a generalization of
the classical Haar and Walsh-Hadamard Transforms. We propose the
extended Generalized Haar-Walsh Transform (eGHWT), which is a
generalization of the adapted time-frequency tilings of Thiele and Villemoes
(1996). The eGHWT examines not only the efficiency of graph-domain partitions
but also that of "sequency-domain" partitions simultaneously.
Consequently, the eGHWT and its associated best-basis selection algorithm for
graph signals significantly improve the performance of the previous GHWT
with the similar computational cost, \(O(N \log N)\), where \(N\) is the number of
nodes of an input graph. While the GHWT best-basis algorithm seeks the most
suitable orthonormal basis for a given task among more than \((1.5)^N\) possible
orthonormal bases in \(\mathbb{R}^N\), the eGHWT best-basis algorithm can find a
better one by searching through more than \(0.618\cdot(1.84)^N\) possible
orthonormal bases in \(\mathbb{R}^N\). This article describes the details of the
eGHWT best-basis algorithm and demonstrates its superiority using several
examples including genuine graph signals as well as conventional digital
images viewed as graph signals. Furthermore, we also show how the eGHWT can be
extended to 2D signals and matrix-form data by viewing them as a tensor
product of graphs generated from their columns and rows and demonstrate its
effectiveness on applications such as image approximation.
Keywords:
Graph wavelets and wavelet packets; Haar-Walsh wavelet packet transform; best basis selection; graph signal approximation; image analysis
Get the full paper (via arXiv:2107.05121 [eess.SP]) : PDF file.
Get the official version via doi:10.1007/s10851-021-01064-w.
Please email
me if you have any comments or questions!
Go
back to Naoki's Publication Page