Codes and Expansions (CodEx) Seminar

Naoki Saito (University of California Davis)
Multiscale Graph Basis Dictionaries

I will discuss my group's eight-year effort to develop multiscale graph basis dictionaries that generalize the classical counterparts: wavelet packet and local cosine basis dictionaries. After briefly reviewing the classical wavelet packets and local cosine basis dictionaries, I plan to describe the difficulties of lifting those to the graph setting, and how we could overcome them. There are two keys for successful constructions: 1) hierarchical bipartition tree of a given graph; and 2) the concept of the "dual" domain of a graph. I will first discuss the simplest of all, the Hierarchical Graph Laplacian Eigen Transform (HGLET) that corresponds to the classical hierarchical block discrete cosine transform, then the Generalized Haar-Walsh Transform (GHWT). Second, I will describe our idea of generating the dual domain of a given graph based on the geometry of graph Laplacian eigenvectors, and subsequently discuss the Natural Graph Wavelet Packets (NGWPs), which is a generalization of the Shannon wavelet packets. Finally, using the smooth orthogonal folding/unfolding operators on a graph, I will describe the "Lapped"-HGLET and "Lapped"-NGWPs, which correspond to the local cosine dictionary and the Meyer wavelet packets, respectively.

I will conclude my talk with my perspective on these tools and the information on our software package of these dictionaries completely written in the Julia programming language.