Bespoke multiresolution analysis of graph signals
Preprint
Abstract
We present a novel framework for discrete multiresolution analysis of graph signals. The main analytical tool is the samplet transform, originally defined in the Euclidean framework as a discrete wavelet-like construction, tailored to the analysis of scattered data. The first contribution of this work is defining samplets on graphs. To this end, we subdivide the graph into a fixed number of patches, embed each patch into a Euclidean space, where we construct samplets, and eventually pull the construction back to the graph. This ensures orthogonality, locality, and the vanishing moments property with respect to properly defined polynomial spaces on graphs. Compared to classical Haar wavelets, this framework broadens the class of graph signals that can efficiently be compressed and analyzed. Along this line, we provide a definition of a class of signals that can be compressed using our construction. We support our findings with different examples of signals defined on graphs whose vertices lie on smooth manifolds. For efficient numerical implementation, we combine heavy edge clustering, to partition the graph into meaningful patches, with landmark \texttt{Isomap}, which provides low-dimensional embeddings for each patch. Our results demonstrate the method's robustness, scalability, and ability to yield sparse representations with controllable approximation error, significantly outperforming traditional Haar wavelet approaches in terms of compression efficiency and multiresolution fidelity.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Multiresolution kernel matrix algebraNumerische Mathematik, 2024
- Haar-Like Wavelets on Hierarchical TreesJournal of Scientific Computing, 2024
- Spectral graph wavelet packets framesApplied and Computational Harmonic Analysis, 2023
- Monitoring and flaw detection during wire-based directed energy deposition using in-situ acoustic sensing and wavelet graph signal analysisMaterials & Design, 2022
- Samplets: Construction and scattered data compressionJournal of Computational Physics, 2022
- Wavelets on graphs via spectral graph theoryApplied and Computational Harmonic Analysis, 2011
- The Haar Wavelet Transform of a DendrogramJournal of Classification, 2007
- Fast computation in adaptive tree approximationNumerische Mathematik, 2004
- A theory for multiresolution signal decomposition: the wavelet representationIEEE Transactions on Pattern Analysis and Machine Intelligence, 1989
- Multidimensional Scaling: I. Theory and MethodPsychometrika, 1952