  We propose a method for estimating a covariance matrix that can be
represented as a sum of a low-rank matrix and a diagonal matrix. The proposed
method compresses high-dimensional data, computes the sample covariance in the
compressed space, and lifts it back to the ambient space via a decompression
operation. A salient feature of our approach relative to existing literature on
combining sparsity and low-rank structures in covariance matrix estimation is
that we do not require the low-rank component to be sparse. A principled
framework for estimating the compressed dimension using Stein's Unbiased Risk
Estimation theory is demonstrated. Experimental simulation results demonstrate
the efficacy and scalability of our proposed approach.
