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