Scalable graph signal recovery for big data over networks
Alexander Jung, Peter Berger, Gábor Hannák, Gerald Matz · 2016
We formulate the recovery of a graph signal from noisy samples taken on a subset of graph nodes as a convex optimization 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.