UC Davis

We propose methods to efficiently approximate and denoise signals sampled on the nodes of graphs using our overcomplete multiscale transforms/basis dictionaries for such graph signals: the hierarchical graph Laplacian eigen transform (HGLET) and the generalized Haar-Walsh transform (GHWT). These can be viewed as generalizations of the hierarchical discrete cosine transform and the Haar-Walsh wavelet packet transform, respectively, from regularly sampled signals to graph signals. Both of these transforms generate dictionaries containing an immense number of choosable bases, and in order to select a particular basis most suitable for a given task, we have generalized the best basis algorithm from classical signal processing. After briefly reviewing these transforms and the best basis algorithm, we precisely prove their efficiency in approximating graph signals belonging to discrete analogs of the space of Hölder continuous functions and the Besov spaces. Then, we validate their effectiveness with numerical experiments on real datasets, in which we compare them against other graph-based transforms. Building upon this approximation efficiency of our transforms, we devise a signal denoising method using the HGLET and GHWT and again compare against other transforms. Our results clearly demonstrate the superiority of our transforms over those other transforms in terms of both approximation and denoising.