The Sample Complexity of Toeplitz Covariance Estimation

Wednesday, June 5, 2019 - 4:00pm to 5:00pm
Location: 
32-G575
Speaker: 
Jerry Li
Biography: 
Microsoft Research
We study the query complexity of estimating the covariance matrix T of a distribution D over d-dimensional vectors, under the assumption that T is Toeplitz. This assumption is standard in a wide variety of signal processing problems, where the covariance between any two measurements only depends on the time or distance between those measurements. In many of these applications, we are interested in
estimation strategies that may choose to view only a subset of entries in each d-dimensional sample x from D. We care about minimizing both 1) the number of samples taken and 2) the number of entries accessed in each sample, which often equates to minimizing equipment requirements in applications ranging from wireless transmission to advanced imaging.

We give many of the first non-asymptotic bounds on these sample complexity measures. We analyze classical and widely used estimation algorithms, in particular methods based on selecting entries from each sample according to a `sparse ruler'. We explain how sparse ruler based estimation can significantly outperform naive methods when T is close to low-rank, as is
often the case in practice. We also develop a novel sampling and estimation strategy that improves on known algorithms in the low-rank case. Our method utilizes tools from random matrix sketching, leverage score based sampling techniques for continuous time signals, and sparse Fourier transform algorithms.

Joint work with Y. Eldar, C. Musco, and C. Musco.