We propose a novel method for constructing wavelet transforms of functions defined on the vertices of an arbitrary finite weighted graph. Our approach is based on defining scaling using the the graph analogue of the Fourier domain, namely the spectral decomposition of the discrete graph Laplacian @math . Given a wavelet generating kernel @math and a scale parameter @math , we define the scaled wavelet operator @math . The spectral graph wavelets are then formed by localizing this operator by applying it to an indicator function. Subject to an admissibility condition on @math , this procedure defines an invertible transform. We explore the localization properties of the wavelets in the limit of fine scales. Additionally, we present a fast Chebyshev polynomial approximation algorithm for computing the transform that avoids the need for diagonalizing @math . We highlight potential applications of the transform through examples of wavelets on graphs corresponding to a variety of different problem domains.
Geller and Mayeli @cite_48 studied a construction for wavelets on compact differentiable manifolds that is formally similar to our approach on weighted graphs. In particular, they define scaling using a pseudodifferential operator @math , where @math is the manifold Laplace-Beltrami operator and @math is a scale parameter, and obtain wavelets by applying this to a delta impulse. They also study the localization of the resulting wavelets, however the methods and theoretical results in their paper are different as they are in the setting of smooth manifolds.
@cite_48
2003334210
Let M be a smooth compact oriented Riemannian manifold, and let ΔM be the Laplace–Beltrami operator on M. Say ( 0 f S ( R ^+) ) , and that f (0) = 0. For t > 0, let Kt(x, y) denote the kernel of f (t2 ΔM). We show that Kt is well-localized near the diagonal, in the sense that it satisfies estimates akin to those satisfied by the kernel of the convolution operator f (t2Δ) on ( R ^n ) . We define continuous ( S )-wavelets on M, in such a manner that Kt(x, y) satisfies this definition, because of its localization near the diagonal. Continuous ( S )-wavelets on M are analogous to continuous wavelets on ( R ^n ) in ( S ) ( ( R ^n )). In particular, we are able to characterize the Holder continuous functions on M by the size of their continuous ( S )-wavelet transforms, for Holder exponents strictly between 0 and 1. If M is the torus ( T^2 ) or the sphere S2, and f (s) = se−s (the “Mexican hat” situation), we obtain two explicit approximate formulas for Kt, one to be used when t is large, and one to be used when t is small.