A Framework for Multiscale Transforms on Graphs
Preprint
Abstract
Multiscale transforms designed to process analog and discrete-time signals and images cannot be directly applied to analyze high-dimensional data residing on the vertices of a weighted graph, as they do not capture the intrinsic geometric structure of the underlying graph data domain. In this paper, we present a modular framework to adapt multiscale transforms such as the Laplacian pyramid, critically sampled filter bank, and lifting scheme so that they can be used to analyze high-dimensional data residing on the vertices of a weighted graph. Our approach is to study existing methods and develop new methods for the three fundamental operations of filtering for signals on graphs, graph downsampling, and graph reduction. Equipped with appropriate notions of these operations, we leverage the basic multiscale constructs and intuitions from classical signal processing to generate specific examples of new multiscale graph signal processing transforms.Keywords
All Related Versions
This publication has 23 references indexed in Scilit:
- The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domainsIEEE Signal Processing Magazine, 2013
- Wavelets on graphs via spectral graph theoryApplied and Computational Harmonic Analysis, 2011
- A Lower Bound for Nodal Count on Discrete and Metric GraphsCommunications in Mathematical Physics, 2007
- Nodal domain counts and the chromatic number of graphsJournal of Physics A: Mathematical and Theoretical, 2007
- The Haar Wavelet Transform of a DendrogramJournal of Classification, 2007
- Diffusion waveletsApplied and Computational Harmonic Analysis, 2006
- Discrete nodal domain theoremsLinear Algebra and its Applications, 2001
- Fast multilevel implementation of recursive spectral bisection for partitioning unstructured problemsConcurrency: Practice and Experience, 1994
- On the eigenvectors belonging to the minimum eigenvalue of an essentially nonnegative symmetric matrix with bipartite graphLinear Algebra and its Applications, 1989
- The Laplacian Pyramid as a Compact Image CodeIEEE Transactions on Communications, 1983