Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
arXiv:1106.3693 · doi:10.1109/TSP.2012.2188718
Abstract
In this work we propose the construction of two-channel wavelet filterbanks for analyzing functions defined on the vertices of any arbitrary finite weighted undirected graph. These graph based functions are referred to as graph-signals as we build a framework in which many concepts from the classical signal processing domain, such as Fourier decomposition, signal filtering and downsampling can be extended to graph domain. Especially, we observe a spectral folding phenomenon in bipartite graphs which occurs during downsampling of these graphs and produces aliasing in graph signals. This property of bipartite graphs, allows us to design critically sampled two-channel filterbanks, and we propose quadrature mirror filters (referred to as graph-QMF) for bipartite graph which cancel aliasing and lead to perfect reconstruction. For arbitrary graphs we present a bipartite subgraph decomposition which produces an edge-disjoint collection of bipartite subgraphs. Graph-QMFs are then constructed on each bipartite subgraph leading to "multi-dimensional" separable wavelet filterbanks on graphs. Our proposed filterbanks are critically sampled and we state necessary and sufficient conditions for orthogonality, aliasing cancellation and perfect reconstruction. The filterbanks are realized by Chebychev polynomial approximations.
32 pages double spaced 12 Figures, to appear in IEEE Transactions of Signal Processing
References in corpus (1)
Cited by in corpus (67)
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Discrete Signal Processing on Graphs
- Discrete Signal Processing on Graphs: Sampling Theory
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Signal Recovery on Graphs: Variation Minimization
- Compact Support Biorthogonal Wavelet Filterbanks for Arbitrary Undirected Graphs
- A Spectral Graph Uncertainty Principle
- Local-set-based Graph Signal Reconstruction
- Greedy Sampling of Graph Signals
- On the Graph Fourier Transform for Directed Graphs
- Learning parametric dictionaries for graph signals
- Adaptive Least Mean Squares Estimation of Graph Signals
- Adaptive Graph Signal Processing: Algorithms and Optimal Sampling Strategies
- Graph Unrolling Networks: Interpretable Neural Networks for Graph Signal Denoising
- Subgraph-based filterbanks for graph signals
- Spectral Domain Sampling of Graph Signals
- Deep Unsupervised Learning of 3D Point Clouds via Graph Topology Inference and Filtering
- A Distributed Tracking Algorithm for Reconstruction of Graph Signals
- Distributed Adaptive Learning of Graph Signals
- Spectral Projector-Based Graph Fourier Transforms
- Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling
- Learning Graphs with Monotone Topology Properties and Multiple Connected Components
- Generalized Sampling on Graphs With Subspace and Smoothness Priors
- Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)
- Learning Laplacian Matrix in Smooth Graph Signal Representations
- Splines and Wavelets on Circulant Graphs
- Signal Representations on Graphs: Tools and Applications
- Graph Signal Sampling Under Stochastic Priors
- Sampling and Reconstruction of Sparse Signals on Circulant Graphs - An Introduction to Graph-FRI
- Graph Learning from Data under Structural and Laplacian Constraints
- Graph Signal Processing: Dualizing GSP Sampling in the Vertex and Spectral Domains
- Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
- Graph Signal Processing: Vertex Multiplication
- Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
- Joint Time-Vertex Fractional Fourier Transform
- Observing and Tracking Bandlimited Graph Processes
- Graph Signal Processing: Modulation, Convolution, and Sampling
- Multiresolution Representations for Piecewise-Smooth Signals on Graphs
- M-Channel Critically Sampled Spectral Graph Filter Banks With Symmetric Structure
- Graph Convolutional Networks with EigenPooling
- A Graph Signal Processing View on Functional Brain Imaging
- Color graph based wavelet transform with perceptual information
- Spectral Domain Spline Graph Filter Bank
- Detecting Localized Categorical Attributes on Graphs
- Signal Recovery on Graphs: Fundamental Limits of Sampling Strategies
- On the Shift Operator, Graph Frequency and Optimal Filtering in Graph Signal Processing
- Localization, Decomposition, and Dictionary Learning of Piecewise-Constant Signals on Graphs
- From graphs to signals and back: Identification of network structures using spectral analysis
- Polynomial graph filter of multiple shifts and distributed implementation of inverse filtering
- Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
- Sampling and Recovery of Graph Signals based on Graph Neural Networks
- Local Measurement and Reconstruction for Noisy Graph Signals
- Agile Inexact Methods for Spectral Projector-Based Graph Fourier Transforms
- Filter Design for Autoregressive Moving Average Graph Filters
- Dynamic Polygon Clouds: Representation and Compression for VR/AR
- Graph Blind Deconvolution with Sparseness Constraint
- Nonsubsampled Graph Filter Banks and Distributed Implementation
- Message Passing in Graph Convolution Networks via Adaptive Filter Banks
- A Graph Downsampling Technique Based On Graph Fourier Transform
- Learning Optimal Graph Filters for Clustering of Attributed Graphs
- Graph Equivalence Classes for Spectral Projector-Based Graph Fourier Transforms
- Spline-Like Wavelet Filterbanks with Perfect Reconstruction on Arbitrary Graphs
- Design of Sampling Set for Bandlimited Graph Signal Estimation
- Perfect Reconstruction Two-Channel Filter Banks on Arbitrary Graphs
- Spectral Graph Wavelet Transform as Feature Extractor for Machine Learning in Neuroimaging
- Estimating Network Processes via Blind Identification of Multiple Graph Filters
- Fast Decentralized Linear Functions Over Edge Fluctuating Graphs