Low-Rank Toeplitz Matrix Estimation Via Random Ultra-Sparse Rulers

Hannah Lawrence, Jerry Li, Cameron Musco, Christopher Musco

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

    Abstract

    We study how to estimate a nearly low-rank Toeplitz covariance matrix T from compressed measurements. Recent work of Qiao and Pal addresses this problem by combining sparse rulers (sparse linear arrays) with frequency finding (sparse Fourier transform) algorithms applied to the Vandermonde decomposition of T. Analytical bounds on the sample complexity are shown, under the assumption of sufficiently large gaps between the frequencies in this decomposition.In this work, we introduce random ultra-sparse rulers and propose an improved approach based on these objects. Our random rulers effectively apply a random permutation to the frequencies in T's Vandermonde decomposition, letting us avoid frequency gap assumptions and leading to improved sample complexity bounds. In the special case when T is circulant, we theoretically analyze the performance of our method when combined with sparse Fourier transform algorithms based on random hashing. We also show experimentally that our ultra-sparse rulers give significantly more robust and sample efficient estimation then baseline methods.

    Original languageEnglish (US)
    Title of host publication2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020 - Proceedings
    PublisherInstitute of Electrical and Electronics Engineers Inc.
    Pages4796-4800
    Number of pages5
    ISBN (Electronic)9781509066315
    DOIs
    StatePublished - May 2020
    Event2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020 - Barcelona, Spain
    Duration: May 4 2020May 8 2020

    Publication series

    NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
    Volume2020-May
    ISSN (Print)1520-6149

    Conference

    Conference2020 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2020
    CountrySpain
    CityBarcelona
    Period5/4/205/8/20

    Keywords

    • randomized methods
    • sparse array
    • sparse Fourier transform
    • Toeplitz covariance estimation

    ASJC Scopus subject areas

    • Software
    • Signal Processing
    • Electrical and Electronic Engineering

    Fingerprint Dive into the research topics of 'Low-Rank Toeplitz Matrix Estimation Via Random Ultra-Sparse Rulers'. Together they form a unique fingerprint.

    Cite this