Inferring sparse graphs from smooth signals with theoretical guarantees

Abstract

We consider the problem of inferring a graph from signals which are assumed to be smooth over the graph, in the setting where the graph is also assumed to be sparse. We focus on the case where measurements are Gaussian vectors and the graph topology is encoded in the inverse of the covariance matrix. In addition, the weights of the inverse covariance are assumed to be such that the model is attractive-all partial correlations are non-negative. Unlike other approaches which seek to minimize the Laplacian quadratic form or involve solving a log-det program, we study a simple estimator based on soft thresholding. The estimator involves computing only a single eigenvalue decomposition, and so it can easily scale to networks with thousands of vertices. We provide theoretical results on the reconstruction error as a function of the number of observations and problem dimensions for the case where the underlying graph is assumed to be sparse.