Document Type


Date of Degree

Fall 2016

Degree Name

PhD (Doctor of Philosophy)

Degree In


First Advisor

Jorgensen, Palle E.

First Committee Member

Baker, Richard

Second Committee Member

Han, Weimin

Third Committee Member

Khurana, Surjit

Fourth Committee Member

Strohmer, Gerhard


Signals on hierarchical trees can be viewed as a generalization of discrete signals of length 2^N. In this work, we extend the classic discrete Haar wavelets to a Haar-like wavelet basis that works for signals on hierarchical trees. We first construct a specific wavelet basis and give its inverse and normalized transform matrices.

As analogue to the classic case, operators and wavelet generating functions are constructed for the tree structure. This leads to the definition of multiresolution analysis on a hierarchical tree. We prove the previously selected wavelet basis is an orthogonal multiresolution. Classification of all possible wavelet basis that generate an orthogonal multiresolution is then given. In attempt to find more efficient encoding and decoding algorithms, we construct a second wavelet basis and show that it is also an orthogonal multiresolution. The encoding and decoding algorithms are given and their time complexity are analyzed.

In order to link change of tree structure and encoded signal, we define weighted hierarchical tree, tree cut and extension. It is then shown that a simply relation can be established without the need for global change of the transform matrix. Finally, we apply thresholding to the transform and give an upper bound of error.

Public Abstract

In pure and applied mathematics, the study of network graphs plays a central role. This thesis offers new tools for analysis and synthesis constructions for such specific finite graphs. We extend hierarchical algorithms which were first developed in the case of L2 function spaces. The setting of graphs is motivated by the need to represent real world data arising in the study of irregular and complex structures. Real world problems include traffic flow, neural network, cluster analysis, and data analysis in on-line social networks.

Classic signal processing analysis already has a history and relatively mature theories and methods exist there, but extensions to analysis on graphs is so far only in its infancy. While our setting is that of graphs, we stress connections to related algorithms which were first developed in the different context of L2 function-spaces. Our work makes precise and it identities, in the setting of graphs, hierarchical structures and associated multiresolution scales on realistic graph families. In our presentation, we also recall some mathematical background from signal processing.

Classic signal processing and multiresolution analysis already exist in continuous models with a history and relatively mature theories there. But we point out that extensions to various families of graphs pose a whole new set of problems. Indeed, hierarchical analysis on graphs is so far only in its infancy. Motivated by applications, our present results are for finite graphs.


Haar, hierarchy, multiresolution, tree, wavelet


vii, 102 pages


Includes bibliographical references (pages 97-101).


Copyright © 2016 Lu Yu

Included in

Mathematics Commons