Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data

By Sunil K. Narang, Antonio Ortega. IEEE Transactions on Signal Processing, 2011

411 citations recorded by the source corpus.

In this work, we propose the construction of two-channel wavelet filter banks 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 filter banks, 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 filter banks on graphs. Our proposed filter banks are critically sampled and we state necessary and sufficient conditions for orthogonality, aliasing cancellation and perfect reconstruction. The filter banks are realized by Chebychev polynomial approximations.

Subfields: Computer Vision and Pattern Recognition, Media Technology

View Paper: https://www.semanticscholar.org/paper/1aff2a421aaa24e46214bf1fc86f44cc42558609

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

Toward an uncertainty principle for weighted graphs (2015, background): “Graph signal processing [3] is a generalization of classical Fourier analysis in which the support for the signal is not necessarily a uniform sampling in time but may be a more complex structure, represented as a graph.”
Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies (2015, methodology): “For example, spectral filters in the form of polynomials of the variation operator are used in the design of wavelet filterbanks for graph signals [21], [17], [18] to offer a trade-off between frequency-domain and vertex-domain localization.”
Signal Recovery on Graphs: Variation Minimization (2014, background): “Recent work involves graph-based ﬁltering [3], [7], [8], graph-based transforms [3], [6], [9], sampling and interpolation on graphs [10]–[12], uncertainty principle on graphs [13], semi-supervised classiﬁcation on graphs [14]–[16], graph dictionary learning [17], [18], and community detection on…”
Graph Signal Processing: Overview, Challenges, and Applications (2017, background): “These types of filterbanks have been designed for bipartite graphs [68], [102], thus requiring the graph to be decomposed into a series of bipartite subgraphs [68], [103].”
Graph Learning From Data Under Laplacian and Structural Constraints (2016, methodology): “Moreover, in graph signal processing [4], basic signal processing operations such as filtering [10] [20], sampling [21], transformation [9] [22] are extended to signals defined on graphs associated with Laplacian matrices.”
Discrete Signal Processing on Graphs: Frequency Analysis (2013, background): “For example, the graph Fourier transform defined and considered in [8], as well as [16], [17], [18], [19], [20], [21], expands graph signals in the eigenbasis of the graph Laplacian.”
A Multiscale Pyramid Transform for Graph Signals (2013, methodology): “However, for large graphs 11Note that the graph-QMF transform only uses the adjacency matrix structure, and not the weights of the graphs.”
Discrete Signal Processing on Graphs: Sampling Theory (2015, methodology): “Previous works implemented graph downsampling via graph coloring [6], or minimum spanning tree [45].”
Graph Convolutional Networks with EigenPooling (2019, methodology): “Using the first H coefficients while discarding the others means that we focus more on the “smoother” part of the graph signal, which is common in a lot of applications such as signal denoising and compression [5, 29, 40].”
Global and Local Uncertainty Principles for Signals on Graphs (2016, background): “Most of the recently proposed dictionaries for graph signals are either orthogonal bases (e.g., [6, 15, 20]) , which are a subset of tight frames, or overcomplete frames (e.g., [13, 23, 22]).”
Learning Laplacian Matrix in Smooth Graph Signal Representations (2014, background): “We believe that our new framework can benefit numerous emerging real world applications, such as the analysis of transportation, biomedical, and social networks, where it is critical to infer hidden relationships between data entities.”
Spectral Graph Skeletons for 3D Action Recognition (2014, methodology): “Recent approaches for using graphs in machine learning include graph kernels [1,14,38], generalizations of signal processing frameworks to the graph domain [7, 24], and also graph wavelets [5,6,12,20,22], such as the spectral graph wavelet transform [12].”