A Network Compatibility Condition for Compressed Sensing over Complex Networks

Abstract

This paper continues our recently initiated line of work on analyzing the network Lasso (nLasso, which has been proposed as an efficient learning algorithm for massive networkstructured data sets (big data over networks). The nLasso extends the well-known Lasso estimator to network-structured datasets. In this paper we consider the nLasso using squared error loss and provide sufficient conditions on the network structure and available label information such that nLasso accurately recovers a clustered (piece-wise constant) graph signal (representing label information) from the information pro-vided by the labels of a few data points.