Search Google Appliance


Wavelets on Graphs via Spectral Graph Theory
Friday, November 19, 2010 - 3:15pm

Portland State University
Fariborz Maseeh Department of Mathematics & Statistics

The Maseeh Mathematics and Statistics Colloquium Series

David Hammond
"NeuroInformatics Center, University of Oregon "

Wavelets on Graphs via Spectral Graph Theory

Wavelet analysis has proved to be a very successful tool for signal analysis and processing. However, many interesting data sets are defined on domains with complicated network-like structure to which classical wavelets are not suitable. In this talk I will describe a novel approach for generating a wavelet transform for data defined on the vertices of a finite weighted graph. A fundamental obstacle to extending classical  wavelet analysis to graph domains is the question of how to define translations and scalings for functions defined on an irregular graph. We sidestep this by appealing to analogy with the graph analogue of the Fourier transform generated by the spectral decomposition of the discrete graph Laplacian $\L$. Using a bandpass-shaped generating function $g$ and scale parameter $t$, we define the scaled wavelet operator "T^t_g=g(t\L)". The spectral graph wavelets are then formed by localizing this operator by applying it to indicator functions at each vertex. An analysis at fine scales shows that this procedure yields localized wavelets. I will describe how spectral graph wavelet frames can be designed through sampling of the scale parameter, with controllable frame bounds. Additionally, I will describe a fast algorithm for computing the wavelet coefficients based on Chebyshev polynomial approximation, which avoids the need to diagonalize "\L". I will conclude with illustrative examples of the spectral graph wavelets on several different problem domains.

This work was done in collaboration with Remi Gribonval and Pierre Vandergheynst.
Friday, November 19th, 2010, 3:15pm
Neuberger Hall room 237
(Refreshments served at 3:00 in NH 344)

* Sponsored by the Maseeh Mathematics and Statistics Colloquium Series Fund and the Fariborz Maseeh Department of Mathematics & Statistics, PSU. This event is free and open to the public.