Applied and computational harmonic analysis on graphs and networks (with J. Irion), Wavelets and Sparsity XVI (M. Papadakis, V. K. Goyal, D. Van De Ville, eds.), Proc. SPIE 9597, Paper #95971F, 2015. Invited paper.


In recent years, the advent of new sensor technologies and social network infrastructure has provided huge opportunities and challenges for analyzing data recorded on such networks. In the case of data on regular lattices, computational harmonic analysis tools such as the Fourier and wavelet transforms have well-developed theories and proven track records of success. It is therefore quite important to extend such tools from the classical setting of regular lattices to the more general setting of graphs and networks. In this article, we first review basics of graph Laplacian matrices, whose eigenpairs are often interpreted as the frequencies and the Fourier basis vectors on a given graph. We point out, however, that such an interpretation is misleading unless the underlying graph is either an unweighted path or cycle. We then discuss our recent effort of constructing multiscale basis dictionaries on a graph, including the Hierarchical Graph Laplacian Eigenbasis Dictionary and the Generalized Haar-Walsh Wavelet Packet Dictionary, which are viewed as generalizations of the classical hierarchical block DCTs and the Haar-Walsh wavelet packets, respectively, to the graph setting. Finally, we demonstrate the usefulness of our dictionaries by using them to simultaneously segment and denoise 1-D noisy signals sampled on regular lattices, a problem where classical tools have difficulty.

Keywords: spectral graph partitioning, multiscale basis dictionaries on graphs, wavelets on graphs, the best basis algorithm, signal segmentation, denoising

  • Get the full paper: PDF file.
  • Get the official version via doi:10.1117/12.2186921.

  • Please email me if you have any comments or questions!
    Go back to Naoki's Publication Page