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.