On the Sparsity of Wavelet Coefficients for Signals on Graphs

A number of new localized, multiscale transforms have recently been introduced to analyze data residing on weighted graphs. In signal processing tasks such as regularization and compression, much of the power of classical wavelets on the real line is derived from their theoretically and empirically proven ability to sparsely represent piecewise-smooth signals, which appear to be locally polynomial at sufficiently small scales. As of yet in the graph setting, there is little mathematical theory relating the sparsity of localized, multiscale transform coefficients to the structures of graph signals and their underlying graphs. In this paper, we begin to explore notions of global and local regularity of graph signals, and analyze the decay of spectral graph wavelet coefficients for regular graph signals.