Almost tight spectral graph wavelets with polynomial filters

The construction of spectral filters for graph wavelet transforms is addressed in this paper. Both the undecimated and decimated cases will be considered. The filter functions are polynomials and can be implemented efficiently without the need for any eigendecomposition, which is computationally expensive for large graphs. Polynomial filters also have the advantage of the vertex localization property. The construction is achieved by designing suitable transformations that are used on traditional multirate filter banks. It will be shown how the classical quadrature-mirror-filters and linear phase, critically/over-sampled filter banks can be used to construct spectral graph wavelets that are almost tight. A variety of design examples will be given to show the versatility of the design technique.