Sample Efficient Toeplitz Covariance Estimation
Cameron Musco, University of Massachusetts, Amherst
Fuller Labs 320
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 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 minimize both 1) the number of d-dimensional samples taken from the distribution and 2) the number of entries accessed in each sample, which often equates to minimizing equipment requirements.
We give some of the first nontrivial non-asymptotic bounds on these sample complexity measures. We analyze widely used estimation algorithms, in particular methods based on accessing entries in 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 and leverage score based sampling techniques for continuous time signals. This work is part of a broader agenda to address fundamental problems in signal processing using tools from theoretical computer science and randomized algorithm design.
Cameron Musco is an Assistant Professor of Computer Science at the University of Massachusetts Amherst. He studies algorithms, working at the intersection of theoretical computer science, numerical computation, optimization, and machine learning. He is especially interested in randomized methods and those that adapt to streaming and distributed computation. Before UMass, Cameron completed his Ph.D. at MIT and was a postdoctoral researcher at Microsoft Research New England.