Scalable Graph Signal Recovery for Big Data Over Networks

Abstract

We formulate the recovery of a graph signal from noisy sam- ples taken on a subset of graph nodes as a convex optimiza- tion problem that balances the empirical error for explaining the observed values and a complexity term quantifying the smoothness of the graph signal. To solve this optimization problem, we propose to combine the alternating direction method of multipliers with a novel denoising method that minimizes total variation. Our algorithm can be efficiently implemented in a distributed manner using message passing and thus is attractive for big data problems over networks.