# Online estimation of covariance matrix

I am trying to dynamically estimate the (low-dimensional) covariance matrix ${\mathbb E}[{\bf x}_t{\bf x}_t^\top]$ of a stream of data points ${\bf x}_t\in{\mathbb R}^N$ online, without any memory. For the mean $\mu = {\mathbb E}[{\bf x}_t]$ this is comparably easy, the update equation is simply

$$\tau\Delta\mu = -\mu + {\bf x}_t$$

where $\tau$ is some time-constant over which I estimate the mean (it's a dynamic environment in which the mean changes slowly over time). Now I am wondering what the best and numerically stable way is to estimate the covariance matrix in a similar way? I came across

http://www.johndcook.com/standard_deviation.html

on how to estimate the variance online (though not a dynamic estimator) and maybe there is something similar for the full problem of covariance matrices.

Thanks!

• Maybe I'm misunderstanding, but what's wrong with $\tau\Delta\tilde{\Sigma} = x_t x_t^T - \tilde{\Sigma}$? – Yoav Kallus Feb 11 '14 at 5:25

Control theory contains a vast literature on the Kalman filter, which deals with estimation in linear systems of the form $x_{k+1} = A x_k + B u_k; y_k = C x_k + D v_k$. Here $x$ is a state vector, $u$ and $v$ are random variables, and $A, B, C$ and $D$ are matrices of appropriate dimensions.

Take a standard reference on Kalman filters, pick the matrices 0 or the identity as needed, and you will most likely find all results that you need. There are almost too many good books on linear estimation to mention, at all levels of mathematical depth and engineering intuition (or lack thereof).

One way to do this - sometimes used for adaptive beamforming - is to use rank one updates to the covariance matrix. See, for example but in a different context, the link below:

     http://image.diku.dk/igel/paper/ACECMUaa1p1CMAfES.pdf


This paper seems relevant: Dasjupta&Hsu

The authors analyze the problem from an online learning perspective - that is, they give bounds on the regret: the gap between in performance between online estimation of mu and sigma and the optimal estimator when we have access to the entire data (the latter being the MLE, namely the sample mean and variance). They also provide an explicit update rule based on 'follow the leader' strategy for the mean and the covariance matrix when adding a new observation - see eq. (8) for the multivariate case.