Sample efficient toeplitz covariance estimation

Yonina C. Eldar, Jerry Li, Cameron Musco, Christopher Musco

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We study the sample complexity of estimating the covariance matrix T of a distribution 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 ~ 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 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. These bounds follow from a novel analysis of classical and widely used estimation algorithms (along with new variants), including methods based on selecting entries from each vector sample according to a so-called sparse ruler. 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, we develop a new estimation strategy that further improves on 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. Our results utilize tools from random matrix sketching, leverage score based sampling techniques for continuous time signals, and sparse Fourier transform methods. In many cases, we pair our upper bounds with matching or nearly matching lower bounds.

    Original languageEnglish (US)
    Title of host publication31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
    EditorsShuchi Chawla
    PublisherAssociation for Computing Machinery
    Number of pages20
    ISBN (Electronic)9781611975994
    StatePublished - 2020
    Event31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States
    Duration: Jan 5 2020Jan 8 2020

    Publication series

    NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


    Conference31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020
    Country/TerritoryUnited States
    CitySalt Lake City

    ASJC Scopus subject areas

    • Software
    • General Mathematics


    Dive into the research topics of 'Sample efficient toeplitz covariance estimation'. Together they form a unique fingerprint.

    Cite this