Graph Signal Processing (GSP) leverages pair-wise relationship between nodes of a graph to formulate operators on signals defined over the nodes. Most existing graph signal operators in the literature are linear, and can be described by linear transformation matrices. Recently, works are emerging that consider the time correlation of graph signals, leading to time-vertex signal processing. By exploiting the joint correlations across the graph topology and time, better results can be obtained. In this work, we propose a median operator that will leverage the joint correlation, for denoising time-varying graph signals. The median operator, known for its robustness to outliers in statistics, has been very successful in traditional signal processing, especially for images. The efficient and highly localised graph median filters developed here are applied to denoising real world sensor network data. Real world sensor nodes are usually resource limited in terms of their computational and communication capacity, hence the imperative requirement for efficient localised filters. Comprehensive experimental results will show that in some cases, the performance is significantly better than the equivalent linear operator counterpart.

A technique for denoising signals defined over graphs was recently proposed by Chen et al . (2014). The technique is based on a regularisation framework and denoising is achieved by solving an optimisation problem. Matrix inversion is required and an approximate solution that avoids directly calculating the inverse, by using a graph filter, was proposed by Chen et al . (2014). The technique, however, requires an eigendecomposition and the resulting filter degree is high. In this study, the authors propose a computationally efficient technique that is based on a least squares approximation of the eigenvalues of the inverse. They show that a good approximation can be achieved with a low degree graph polynomial filter without the need for any eigendecomposition. Low degree filters also have the desirable property of vertex localisation (analogous to time localisation). The filter gives denoising results that are very similar to that using the exact solution and can be implemented using distributed processing.

Graph signal processing (GSP) is a field that deals with data residing on irregular domains, i.e. graph signals. In this field, the graph filter bank is one of the most important developments, owing to its ability to provide multiresolution analysis of graph signals. However, most of the current research on graph filter bank focuses on static graph signals. The research does not exploit the temporal correlations of time-varying signals in real-world applications, such as in wireless sensor networks. In this paper, the theory and design of joint time-vertex nonsubsampled filter bank are developed, using a generalized product graph framework. Several methods are proposed to design the filter bank with perfect reconstruction, while still achieving filters with good spectral characteristics. A notable feature of the designed filter bank is that it can be completely realized in a distributed manner. The subband filters are either of polynomial type or defined implicitly via iterative equations. In either case, implementing the subband filters requires only the exchange of information between neighboring nodes. The filter banks are therefore of low implementation complexity and suitable for processing large time-varying datasets. Numerical examples will demonstrate the effectiveness of the proposed designed methods. Application in time-varying graph signal denoising will show the superiority of joint time-vertex filter bank over other methods.

Graph filter banks play a crucial role in the vertex and spectral representation of graph signals. The notion of two-channel nonsubsampled graph filter banks (NSGFBs) on an undirected graph was introduced recently. The absence of downsampling/upsampling operators allows greater flexibility in the design of NSGFBs that achieve perfect reconstruction. However the design of NSGFBs that take the spectral response into account has not been adequately addressed yet. Based on the polynomial/rational lifting scheme, this letter presents a simple method to design NSGFBs with good spectral response and perfect reconstruction. Experimental results will demonstrate the effectiveness of the proposed method in tailoring the spectral responses of the lifted NSGFBs. Application of the NSGFB to denoising will also be considered.

The recovery of missing samples from available noisy measurements is a fundamental problem in signal processing. In the graph setting, the aim is to recover missing samples on a subset of vertices using samples from other vertices. This process is also sometimes known as graph signal inpainting, reconstruction, forecasting or inference. Many of the existing algorithms do not scale well with the size of the graph and/or they cannot be implemented efficiently in a distributed manner. In this paper, we develop efficient distributed algorithms for the recovery of time-varying graph signals. The a priori assumptions are that the signal is smooth with respect to the graph topology and correlative across time. These assumptions can be incorporated in an optimization formulation of the algorithm via Tikhonov regularization terms. Although this approach is widely used in many graph signal processing problems, our formulation is tailored to yield algorithms that can be efficiently implemented in a distributed manner. Two different distributed algorithms, arising from two different formulations, are proposed to solve the optimization problems. The first involves the $l_2$ norm, and a distributed least squared recovery algorithm (DLSRA) is proposed that leverages the graph topology and sparsity of the corresponding Hessian matrix. The proposed DLSRA is different from other Newton-like methods as there is no need to update the approximate inverse of the Hessian during the iterations. The second involves the $l_1$ norm and the philosophy of the alternating direction method of multipliers (ADMM) is utilized to develop the algorithm. To achieve a totally distributed algorithm, the proposed inexact Newton method is incorporated into the conventional ADMM to give a distributed ADMM recovery algorithm (DAMRA). The two distributed algorithms require only data exchanges between vertices in localized neighbourhood subgraphs. This is in contrast to centralized methods where global data exchanges are required. Experiments on a variety of synthetic and real-world datasets demonstrate that the proposed algorithms are superior to the existing methods

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.