Efficient graph signal recovery over big networks
Gábor Hannák, Peter Berger, Gerald Matz, Alexander Jung · 2016
We consider the problem of recovering a smooth graph signal from noisy samples taken at a small number of graph nodes. The recovery problem is formulated as a convex optimization problem which minimizes the total variation (accounting for the smoothness of the graph signal) while controlling the empirical error. We solve this total variation minimization problem efficiently by applying a recent algorithm proposed by Nesterov for non-smooth optimization problems. Furthermore, we develop a distributed implementation of our algorithm and verify the performance of our scheme on a large-scale real-world dataset.