Efficient Graph Signal Recovery Over Big Networks

Graph-based models are attractive in the context of Big Data since their flexible topology is well-suited to deal with data of diverse nature. Furthermore, graph-based models facilitate distributed computation, which is key for handling large volumes of data. These facts are among the main reasons why graph signal processing (GSP) has recently become increasingly popular. In GSP, the dataset is associated with a graph such that nodes correspond to data points and edges capture their interaction. Application examples of GSP include online social networks, news sites and blog spaces, and proteomics. 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 optimiza- tion 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. Further- more, we develop a distributed implementation of our algorithm and verify the performance of our scheme on a large-scale real-world dataset.