Intertwining wavelets or multiresolution analysis on graphs through random forests |
| |
| Institution: | 1. Leiden University, Netherlands;2. Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France;1. Department of Mathematics, Vanderbilt University, Nashville, TN, 37212, USA;2. Department of Mathematical Science, Northern Illinois University, Dekalb, IL, 60115, USA;3. Department of Mathematics, Johns Hopkins University, Baltimore, MD, 21218, USA;1. Department of Mathematical Sciences, Norwegian University of Science and Technology, N-7491 Trondheim, Norway;2. Simula Research Laboratory AS, 1364 Fornebu, Norway;3. Machine Intelligence Department, Simula Metropolitan Center for Digital Engineering, 0167 Oslo, Norway;1. Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge CB3 0WA, United Kingdom;2. Department of Mathematics, University of Oslo, 0316 Oslo, Norway |
| |
| 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 . 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 . We illustrate the method by numerical experiments. |
| |
| Keywords: | Graph signal processing Multiresolution analysis Wavelet basis Intertwining Markov processes Random spanning forests Determinantal processes |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
