  The covariance matrix of a $p$-dimensional random variable is a fundamental
quantity in data analysis. Given $n$ i.i.d. observations, it is typically
estimated by the sample covariance matrix, at a computational cost of
$O(np^{2})$ operations. When $n,p$ are large, this computation may be
prohibitively slow. Moreover, in several contemporary applications, the
population matrix is approximately sparse, and only its few large entries are
of interest. This raises the following question, at the focus of our work:
Assuming approximate sparsity of the covariance matrix, can its large entries
be detected much faster, say in sub-quadratic time, without explicitly
computing all its $p^{2}$ entries? In this paper, we present and theoretically
analyze two randomized algorithms that detect the large entries of an
approximately sparse sample covariance matrix using only $O(np\text{ poly log }
p)$ operations. Furthermore, assuming sparsity of the population matrix, we
derive sufficient conditions on the underlying random variable and on the
number of samples $n$, for the sample covariance matrix to satisfy our
approximate sparsity requirements. Finally, we illustrate the performance of
our algorithms via several simulations.
