The generalized Haar-Walsh transform

We introduce a novel multiscale transform for signals on graphs which is a generalization of the classical Haar and Walsh-Hadamard Transforms. Using a recursive partitioning of the graph and successive averaging and differencing operations, our transform generates an overcomplete dictionary of orthonormal bases. We describe how to adapt the classical best-basis search algorithm to this setting, and show results from preliminary denoising experiments.