Speaker: Gautam Dasarathy

Learning covariance matrices from high-dimensional data is an important problem that has received a lot of attention recently. In many applications of interest, it could be expensive or physically infeasible to obtain samples from all the underlying variates. Fortunately, the target covariance matrix is often structured. As a means of leveraging this structure, we initiated the study of a framework for recovering a covariance matrix from compressed samples which we call covariance sketching. In this presentation, I will introduce this framework and demonstrate how one can consistently estimate a sparse covariance matrix from compressed samples. Furthermore, I will show that the estimator achieves near optimal compression rates and is computationally efficient.
This is based on work I did during my PhD with Pari Shah, Badri Bhaskar, and Rob Nowak. If you have time, you can skim through the following:
- (journal version)
- (slightly older arxiv version)
I will next discuss some interesting open problems that I am currently thinking about with Pari Shah and Aarti Singh. In particular, I will discuss some main roadblocks to understanding the precise statistical performance and the tradeoffs between compression ratio and sample complexity of such algorithms.