We propose two-channel critically-sampled filter banks for signals on undirected graphs that utilize spectral domain sampling. Unlike conventional approaches based on vertex domain sampling, our transforms have the following desirable properties: 1) perfect reconstruction regardless of the characteristics of the underlying graphs and graph variation operators and 2) a symmetric structure; i.e., both analysis and synthesis filter banks are built using similar building blocks. Along with the structure of the filter banks, this paper also proves the general criterion for perfect reconstruction and theoretically shows that the vertex and spectral domain sampling coincide for a special case. The effectiveness of our approach is evaluated by comparing its performance in nonlinear approximation and denoising with various conventional graph transforms.
Several CS GWTs using vertex domain sampling have been proposed for signals on bipartite graphs. They can be used on non-bipartite graphs by dividing the original graph into several bipartite graphs and then using a multidimensional" decomposition. Filter design methods for this class of CS GWT include: graphQMF @cite_47 , which utilizes quadrature mirror filters; graphBior @cite_38 a biorthogonal and polynomial filter solution with spectral factorization; a frequency conversion method @cite_36 that transforms time domain filters into graph spectral filters; near-orthogonal polynomial filter design methods proposed in @cite_2 @cite_43 . Oversampled graph filter banks were introduced in @cite_50 @cite_40 as an extension of CS GWTs for bipartite graphs.
@cite_38 @cite_36 @cite_43 @cite_40 @cite_50 @cite_2 @cite_47
2004559848 2469743904 2024496749 2535123509
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. Graph signal processing deals with the processing of signals defined on irregular domains and is an emerging area of research. Graph filter banks allow the wavelet transform to be extended for processing graph signals. Sakiyama and Tanaka (2015) 22 recently proposed a technique to convert linear-phase biorthogonal filter banks for regular domain signals to biorthogonal graph filter banks. Perfect reconstruction is preserved using the technique but the resulting spectral filter functions are transcendental and not polynomial. Polynomial function filters are desired for the localization property and implementation efficiency. In this work we present alternative techniques to perform the conversion. Perfect reconstruction is preserved with the proposed techniques and the resulting spectral filters are polynomial functions. HighlightsWe design filter banks for signal defined over bipartite graphs.Spectral filters are polynomials resulting in localization and efficient implementation.Technique is based on converting 1D regular domain filter banks.Perfect reconstruction is exactly preserved and spectral response shape is almost preserved. This paper extends previous results on wavelet filterbanks for data defined on graphs from the case of orthogonal transforms to more general and flexible biorthogonal transforms. As in the recent work, the construction proceeds in two steps: first we design “one-dimensional” two-channel filterbanks on bipartite graphs, and then extend them to “multi-dimensional” separable two-channel filterbanks for arbitrary graphs via a bipartite subgraph decomposition. We specifically design wavelet filters based on the spectral decomposition of the graph, and state sufficient conditions for the filterbanks to be perfect reconstruction and orthogonal. While our previous designs, referred to as graph-QMF filterbanks, are perfect reconstruction and orthogonal, they are not exactly k-hop localized, i.e., the computation at each node is not localized to a small k-hop neighborhood around the node. In this paper, we relax the condition of orthogonality to design a biorthogonal pair of graph-wavelets that are k-hop localized with compact spectral spread and still satisfy the perfect reconstruction conditions. The design is analogous to the standard Cohen-Daubechies-Feauveau's (CDF) construction of factorizing a maximally-flat Daubechies half-band filter. Preliminary results demonstrate that the proposed filterbanks can be useful for both standard signal processing applications as well as for signals defined on arbitrary graphs. This paper builds upon the basic theory of multirate systems for graph signals developed in the companion paper (Part I) and studies @math -channel polynomial filter banks on graphs. The behavior of such graph filter banks differs from that of classical filter banks in many ways, the precise details depending on the eigenstructure of the adjacency matrix @math . It is shown that graph filter banks represent, (linear and) periodically, shift-variant systems only when @math satisfies the noble identity conditions developed in Part I. It is then shown that perfect reconstruction graph filter banks can always be developed when @math satisfies the eigenvector structure satisfied by @math -block cyclic graphs and has distinct eigenvalues (further restrictions on eigenvalues being unnecessary for this). If @math is actually @math -block cyclic then these PR filter banks indeed become practical, i.e., arbitrary filter polynomial orders are possible, and there are robustness advantages. In this case, the PR condition is identical to PR in classical filter banks—any classical PR example can be converted to a graph PR filter bank on an @math -block cyclic graph. It is shown that for @math -block cyclic graphs with all eigenvalues on the unit circle, the frequency responses of filters have meaningful correspondence with classical filter banks. Polyphase representations are then developed for graph filter banks and utilized to develop alternate conditions for alias cancellation and perfect reconstruction, again for graphs with specific eigenstructures. It is then shown that the eigenvector condition on the graph can be relaxed by using similarity transforms.