DOI

10.17077/etd.fzjsus7o

Document Type

Dissertation

Date of Degree

Fall 2016

Degree Name

PhD (Doctor of Philosophy)

Degree In

Mathematics

First Advisor

Palle E. Jorgensen

First Committee Member

Richard Baker

Second Committee Member

Weimin Han

Third Committee Member

Surjit Khurana

Fourth Committee Member

Gerhard Strohmer

Abstract

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.

Keywords

Haar, hierarchy, multiresolution, tree, wavelet

Pages

vii, 102 pages

Bibliography

Includes bibliographical references (pages 97-101).

Copyright

Copyright © 2016 Lu Yu

Included in

Mathematics Commons

Share

COinS