  We study the sample complexity of estimating the covariance matrix $T$ of a
distribution $\mathcal{D}$ over $d$-dimensional vectors, under the assumption
that $T$ is Toeplitz. This assumption arises in many signal processing
problems, where the covariance between any two measurements only depends on the
time or distance between those measurements. We are interested in estimation
strategies that may choose to view only a subset of entries in each vector
sample $x \sim \mathcal{D}$, which often equates to reducing hardware and
communication requirements in applications ranging from wireless signal
processing to advanced imaging. Our goal is to minimize both 1) the number of
vector samples drawn from $\mathcal{D}$ and 2) the number of entries accessed
in each sample.
  We provide some of the first non-asymptotic bounds on these sample complexity
measures that exploit $T$'s Toeplitz structure, and by doing so, significantly
improve on results for generic covariance matrices. Our bounds follow from a
novel analysis of classical and widely used estimation algorithms (along with
some new variants), including methods based on selecting entries from each
vector sample according to a so-called sparse ruler. In many cases, we pair our
upper bounds with matching or nearly matching lower bounds.
  In addition to results that hold for any Toeplitz $T$, we further study the
important setting when $T$ is close to low-rank, which is often the case in
practice. We show that methods based on sparse rulers perform even better in
this setting, with sample complexity scaling sublinearly in $d$. Motivated by
this finding, we develop a new covariance estimation strategy that further
improves on all existing methods in the low-rank case: when $T$ is rank-$k$ or
nearly rank-$k$, it achieves sample complexity depending polynomially on $k$
and only logarithmically on $d$.
