Intertwining wavelets or Multiresolution analysis on graphs through random forests

Abstract

We propose a new method for performing multiscale analysis of functions\ndefined on the vertices of a finite connected weighted graph. Our approach\nrelies on a random spanning forest to downsample the set of vertices, and on\napproximate solutions of Markov intertwining relation to provide a subgraph\nstructure and a filter bank leading to a wavelet basis of the set of functions.\nOur construction involves two parameters q and q'. The first one controls the\nmean number of kept vertices in the downsampling, while the second one is a\ntuning parameter between space localization and frequency localization. We\nprovide an explicit reconstruction formula, bounds on the reconstruction\noperator norm and on the error in the intertwining relation, and a Jackson-like\ninequality. These bounds lead to recommend a way to choose the parameters q and\nq'. We illustrate the method by numerical experiments.\n