Multi-link wavelets on hierarchical graphs

Much of the recent progress in one- and two-dimensional signal processing can be attributed to the introduction of sparse representation techniques such as wavelets. Researchers have recently focused on extending the sparse representation to more complicated data, such as high-dimensional data and data on graphs. Some wavelet techniques applicable to trees as special cases of graph structures have been proposed that are very computationally efficient and easy to implement. However, a tree is too simple to model a data manifold accurately, in particular since a node has at most one parent. In this paper we propose a new efficient wavelet transform applicable to a directed acyclic graph (DAG), in which nodes are allowed to have multiple parents. Our method generalizes a Haar-like wavelet on an unweighted tree by using a redundant representation. In our method, we treat a DAG that has some nodes with signals we wish to analyze and the remaining nodes without signals. Nodes without signals are used to represent the underlying hierarchical structure of the data domain. We also describe a practical application to semi-supervised learning and show that our approach demonstrates an improvement over tree-based wavelets.