Intertwining wavelets or multiresolution analysis on graphs through random forests

We propose a new method for performing multiscale analysis of functions defined on the vertices of a finite connected weighted graph. Our approach relies on a random spanning forest to downsample the set of vertices, and on approximate solutions of Markov intertwining relation to provide a subgraph...

Full description

Saved in:
Bibliographic Details
Published in:Applied and computational harmonic analysis 2020-05, Vol.48 (3), p.949-992
Main Authors: Avena, Luca, Castell, Fabienne, Gaudillière, Alexandre, Mélot, Clothilde
Format: Article
Language:English
Subjects:
Determinantal processes
Graph signal processing
Information Theory
Intertwining
Markov processes
Mathematics
Multiresolution analysis
Probability
Random spanning forests
Wavelet basis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We propose a new method for performing multiscale analysis of functions defined on the vertices of a finite connected weighted graph. Our approach relies on a random spanning forest to downsample the set of vertices, and on approximate solutions of Markov intertwining relation to provide a subgraph structure and a filter bank leading to a wavelet basis of the set of functions. Our construction involves two parameters q and q′. The first one controls the mean number of kept vertices in the downsampling, while the second one is a tuning parameter between space localization and frequency localization. We provide an explicit reconstruction formula, bounds on the reconstruction operator norm and on the error in the intertwining relation, and a Jackson-like inequality. These bounds lead to recommend a way to choose the parameters q and q′. We illustrate the method by numerical experiments.
ISSN:1063-5203
1096-603X
DOI:10.1016/j.acha.2018.09.006