Abstract
We study the sample complexity of estimating the covariance matrix$\mathbf{\Sigma} \in \mathbb{R}^{d\times d}$ of a distribution $\mathcal D$over $\mathbb{R}^d$ given independent samples, under the assumption that$\mathbf{\Sigma}$ is graph-structured. In particular, we focus on shortest pathcovariance matrices, where the covariance between any two measurements isdetermined by the shortest path distance in an underlying graph with $d$ nodes.Such matrices generalize Toeplitz and circulant covariance matrices and arewidely applied in signal processing applications, where the covariance betweentwo measurements depends on the (shortest path) distance between them in timeor space. We focus on minimizing both the vector sample complexity: the number ofsamples drawn from $\mathcal{D}$ and the entry sample complexity: the number ofentries read in each sample. The entry sample complexity corresponds tomeasurement equipment costs in signal processing applications. We give a verysimple algorithm for estimating $\mathbf{\Sigma}$ up to spectral norm error$\epsilon \left\|\mathbf{\Sigma}\right\|_2$ using just $O(\sqrt{D})$ entrysample complexity and $\tilde O(r^2/\epsilon^2)$ vector sample complexity,where $D$ is the diameter of the underlying graph and $r \le d$ is the rank of$\mathbf{\Sigma}$. Our method is based on extending the widely applied idea ofsparse rulers for Toeplitz covariance estimation to the graph setting. In the special case when $\mathbf{\Sigma}$ is a low-rank Toeplitz matrix, ourresult matches the state-of-the-art, with a far simpler proof. We also give aninformation theoretic lower bound matching our upper bound up to a factor $D$and discuss some directions towards closing this gap.