Graph polynomial filter for signal denoising

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.