4
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\begingroup$ Maybe I'm misunderstanding, but what's wrong with $\tau\Delta\tilde{\Sigma} = x_t x_t^T - \tilde{\Sigma}$? $\endgroup$
    – Yoav Kallus
    Commented Feb 11, 2014 at 5:25
  • $\begingroup$ @YoavKallus I think that's not numerically stable. It might not always be posdef, for instance. $\endgroup$
    – valle
    Commented Jan 13 at 14:56

3 Answers 3

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
0
$\begingroup$

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
Improve this answer
$\endgroup$
1
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Dear @Or Zuk, could you please add some details to your answer? Thank you. $\endgroup$
    – Ricardo Andrade
    Commented Feb 11, 2014 at 1:58
  • $\begingroup$ 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. $\endgroup$
    – Or Zuk
    Commented Feb 11, 2014 at 12:04
  • $\begingroup$ Dear @Or Zuk, thank you. I think it would be very helpful if you could copy the content of your comment into your answer. $\endgroup$
    – Ricardo Andrade
    Commented Feb 11, 2014 at 14:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .