A Multiscale Pyramid Transform for Graph Signals
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 adapt the Laplacian pyramid transform for signals on Euclidean domains so that it 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 four fundamental operations of graph downsampling, graph reduction, and filtering and interpolation of signals on graphs. Equipped with appropriate notions of these operations, we leverage the basic multiscale constructs and intuitions from classical signal processing to generate a transform that yields both a multiresolution of graphs and an associated multiresolution of a graph signal on the underlying sequence of graphs.Keywords
All Related Versions
This publication has 18 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
- Variational Splines and Paley–Wiener Spaces on Combinatorial GraphsConstructive Approximation, 2008
- 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
- 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