  We introduce a technique for estimating a structured covariance matrix from
observations of a random vector which have been sketched. Each observed random
vector $\boldsymbol{x}_t$ is reduced to a single number by taking its inner
product against one of a number of pre-selected vector $\boldsymbol{a}_\ell$.
These observations are used to form estimates of linear observations of the
covariance matrix $\boldsymbol{\varSigma}$, which is assumed to be
simultaneously sparse and low-rank. We show that if the sketching vectors
$\boldsymbol{a}_\ell$ have a special structure, then we can use straightforward
two-stage algorithm that exploits this structure. We show that the estimate is
accurate when the number of sketches is proportional to the maximum of the rank
times the number of significant rows/columns of $\boldsymbol{\varSigma}$.
Moreover, our algorithm takes direct advantage of the low-rank structure of
$\boldsymbol{\varSigma}$ by only manipulating matrices that are far smaller
than the original covariance matrix.
