THE NETWORK NULLSPACE PROPERTY FOR COMPRESSED SENSING OVER NETWORKS

We study compressed sensing of graph signals defined over complex networks. In particular, we propose and analyze a convex optimization method for recovering smooth graph signals from a small number of samples. Assuming the true underlying graph signal to be constant over well connected subset of nodes (clusters), we derive a sufficient condition on the sampling set and network structure such that the proposed convex method is accurate. This condition, which we coin the network nullspace property, characterizes which nodes of the graph should be sampled in order to retain the full information about the underlying graph signal.