Distributed sparsified graph filters for denoising and diffusion tasks

Abstract

Generally in distributed signal processing, and specifically in distributed graph filters, reducing the communication and computational complexity plays a key role in the network lifetime. In this work we present a novel algorithm to sparsify the graph filtering operation in a random way, where each node decides locally with a certain probability with which of its neighbors to communicate. We show that, if the filter coefficients are changed accordingly, the first and second order moment of the stochastic output are identical to the deterministic filter output and bounded, respectively. We apply our idea on the tasks of signal denoising and diffusion. Numerical results show that the distributed implementation costs of the filter can be reduced up to 95% with a variance of 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-3</sup> from the deterministic output.