Efficient approximation and denoising of graph signals using the multiscale basis dictionaries (with J. Irion), IEEE Transactions on Signal and Information Processing over Networks, vol.3, no.3, pp.607-616, 2017.


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 Transforms 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öolder 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.

Keywords: Multiscale basis dictionaries on graphs, graph wavelets and wavelet packets, best basis selection, graph signal approximation and denoising.

  • Get the full paper: PDF file (revised on 11/20/16).
  • Get the official version via doi:10.1109/TSIPN.2016.2632039.

  • Please email me if you have any comments or questions!
    Go back to Naoki's Publication Page