Compressed Sensing of Big Data Networks

In this talk, we discuss our recent work on developing a theory of compressed sensing for graph signals defined over complex networks. These graph signals represent the label information contained in massive network-structured datasets (big data over networks). By drawing on compressed sensing for ordinary sparse signals, we have introduced the network nullspace property (NNSP) and the network compatibility condition (NCC), which guarantee that certain convex learning methods, including the recently proposed network Lasso, accurately learn clustered graph signals from a small number of signal samples. These conditions involvethe connectivity structure of the underlying network via requiring the existence of certain network flows.