Mathematical Sciences Research Institute

Home » Covariance Estimation for Distributions with 2+ε Moments


Covariance Estimation for Distributions with 2+ε Moments September 07, 2011 (11:30 AM PDT - 12:30 PM PDT)
Parent Program: --
Location: MSRI: Simons Auditorium
Speaker(s) Nikhil Srivastava (University of California, Berkeley)
Description No Description
No Video Uploaded

A basic question motivated by applications in statistics and convex geometry is the following: given a mean zero random vector $X$ in $R^n$, how many independent samples $X_1,\ldots X_q$ does it take for the empirical covariance matrix $\tilde{C}=1/q\sum_i X_iX_i^T$ to converge to the actual covariance matrix $\E XX^T$?

In an influential paper, M. Rudelson that if $\|X\|\le O(\sqrt{n})$ a.s. and $\E XX^T=I$, then $O((n\log n)$ samples suffice for an arbitrary fixed constant approximation in the operator norm. Under these very weak assumptions on $X$, this bound is tight.

We show that as long as the k-dimensional marginals of $X$ have bounded 2+\epsilon moments for all k\le n, the logarithmic factor is not needed and O(n) samples are enough, which is the optimal bound.

No Notes/Supplements Uploaded No Video Files Uploaded