Natural Graph Wavelet Packets

Naoki Saito
University of California, Davis
Tuesday, November 10, 2020 - 1:25pm to 2:25pm

I will discuss how to build a smooth multiscale wavelet packet dictionary for graph signal processing. Our approach utilizes the dual geometry of an input graph organized by new non-trivial eigenvector distances. More precisely, we construct a dual graph where each node represents a Laplacian eigenvector of the input graph and each weight is an affinity measure between the corresponding pair of the graph Laplacian eigenvectors, which is typically the inverse of the non-trivial distance between them. Once such a dual graph is formed, we bipartition the dual graph and construct tree structured subspaces. Finally, we generate smooth localized wavelet packet vectors (and the expansion coefficients of an input graph signal) on each such subspace that corresponds to a collection of the graph Laplacian eigenvectors. This can be viewed as a graph version of the "Shannon" wavelet packet dictionary. Using the best-basis algorithm or its variants on this graph wavelet packet dictionary, one can select a graph orthonormal basis suitable for a given task such as efficient approximation, denoising, classification.
I will also demonstrate the effectiveness of our graph wavelet packet dictionary compared to some other graph bases (e.g., graph Haar basis, graph Walsh basis, etc.) using both synthetic and real datasets.

This is joint work with Alex Cloninger (UC San Diego) and Haotian Li (UC Davis).

Naoki Saito is an applied and computational harmonic analyst who is interested in feature extraction, graph signal processing, Laplacian eigenfunctions, and human and machine perception. He received the B.Eng. and the M.Eng. degrees in mathematical engineering from the University of Tokyo, Japan, in 1982 and 1984, respectively. Then, he received his Ph.D. degree in applied mathematics from Yale in 1994 while working at the Schlumberger Doll Research. In 1997, he joined the Department of Mathematics at the University of California, Davis, where he is currently a professor and a director of the UC Davis TETRAPODS Institute of Data Science (UCD4IDS), one of the NSF's Transdisciplinary Research In Principles Of Data Science (TRIPODS) Institutes that bring together the theoretical computer science, electrical engineering, mathematics, and statistics communities to develop the theoretical foundations of data science.

Dr. Saito received the Best Paper Awards from SPIE (1994) and JSIAM (2016) as well as the Henri Doll Award from Schl