Intertwining wavelets or multiresolution analysis on graphs through random forests
From MaRDI portal
Publication:2300767
determinantal processesgraph signal processingintertwiningMarkov processesmultiresolution analysisrandom spanning forestswavelet basis
Random walks on graphs (05C81) Graph algorithms (graph-theoretic aspects) (05C85) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Applications of continuous-time Markov processes on discrete state spaces (60J28) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)
Abstract: 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.
Recommendations
Cites work
- A Multiscale Pyramid Transform for Graph Signals
- An analogue of Pitman’s 2M – X theorem for exponential Wiener functionals: Part I: A time-inversion approach
- Beta-gamma random variables and intertwining relations between certain Markov processes
- Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
- Diffusion wavelets
- Downsampling of Signals on Graphs Via Maximum Spanning Trees
- Dyson's Brownian motions, intertwining and interlacing
- scientific article; zbMATH DE number 1256746 (Why is no real title available?)
- scientific article; zbMATH DE number 2001584 (Why is no real title available?)
- scientific article; zbMATH DE number 1380579 (Why is no real title available?)
- Loop-erased random walks, spanning trees and Hamiltonian cycles
- Markov functions
- Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data
- Random forests and networks analysis
- Some properties of the Wishart processes and a matrix extension of the Hartman-Watson laws
- Strong stationary times via a new form of duality
- Subgraph-Based Filterbanks for Graph Signals
- Ten Lectures on Wavelets
- The Schur complement and its applications
- Two applications of random spanning forests
- Wavelet decompositions of random forests -- smoothness analysis, sparse approximation and applications
- Wavelets on graphs via spectral graph theory
Cited in
(11)- Approximate and exact solutions of intertwining equations through random spanning forests
- Harmonic analysis on directed graphs and applications: from Fourier analysis to wavelets
- Loop-erased partitioning of a graph: mean-field analysis
- Stochastic processes under constraints. Abstracts from the workshop held September 27 -- October 3, 2020 (hybrid meeting)
- Representation of functions on big data: graphs and trees
- Metastable Markov chains
- On soft capacities, quasi-stationary distributions and the pathwise approach to metastability
- Multiscale methods for data on graphs and irregular multidimensional situations
- Haar-like wavelets on hierarchical trees
- Loop-erased partitioning via parametric spanning trees: monotonicities \& 1D-scaling
- Approximation theorems on graphs
This page was built for publication: Intertwining wavelets or multiresolution analysis on graphs through random forests
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2300767)
