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.
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. We propose filter banks in the graph spectral domain, where each filter is defined by a sum of sinusoidal waves. The main advantages of these filter banks are that (a) they have low approximation errors even if a lower-order shifted Chebyshev polynomial approximation is used, (b) the upper bound of the error after the @math th order Chebyshev polynomial approximation can be calculated rigorously without complex calculations, and (c) their parameters can be efficiently obtained from any real-valued linear phase finite impulse response filter banks in regular signal processing. The proposed filter bank has the same filter characteristics as the corresponding classical filter bank in the frequency domain and inherits the original properties, such as tight frame and no DC leakage. Furthermore, their approximation orders can be determined from the desired approximation accuracy. The effectiveness of our approach is evaluated by comparing them with existing spectral graph wavelets and filter banks. 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. In this paper, we propose an efficient graph learning approach for fast graph Fourier transform. We consider a maximum likelihood problem with additional constraints based on a matrix factorization of the graph Laplacian matrix, such that its eigenmatrix is a product of a block diagonal matrix and a butterfly-like matrix. We show that a special case of this problem reduces to a learning problem with constraints enforcing certain graph symmetries. Then, we provide an efficient approximation approach for the general problem without enforcing any symmetry constraint. We use this approach to design a fast nonseparable transform for intra predictive residual blocks in video compression. The resulting transform achieves a better rate-distortion performance than the 2D DCT and the hybrid DCT ADST transform. This paper proposes @math -channel oversampled filter banks for graph signals. The filter set satisfies the perfect reconstruction condition. A method of designing oversampled graph filter banks is presented that allows us to design filters with arbitrary parameters, unlike the conventional critically sampled graph filter banks. The oversampled graph Laplacian matrix is also introduced with a discussion of the entire redundancy of the oversampled graph signal processing system. The practical performance of the proposed filter banks is validated through graph signal denoising experiments. The construction of spectral filters for graph wavelet transforms is addressed in this paper. Both the undecimated and decimated cases will be considered. The filter functions are polynomials and can be implemented efficiently without the need for any eigendecomposition, which is computationally expensive for large graphs. Polynomial filters also have the advantage of the vertex localization property. The construction is achieved by designing suitable transformations that are used on traditional multirate filter banks. It will be shown how the classical quadrature-mirror-filters and linear phase, critically over- sampled filter banks can be used to construct spectral graph wavelets that are almost tight. A variety of design examples will be given to show the versatility of the design technique. 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.