Running n-lag correlation matrix? Working in python, I get data at regular interval. The data contains some features, $X_1,\dots,X_p$. I am trying to get an online algorithm to build correlation matrixes. The naive approach of keeping track of the last $n$ instances of $X$ is working but rather slow.
I have found some way to get variance and covariance of the whole sample in one or two  passes, but it doesn't seems to be what I am looking for. I am looking for a way to update some current calculation with mostly the last value (and removing the oldest values) in a running manner. Example: for a running sum, you can keep track of a cumulative sum, only adding / removing one value at each time step.
Any idea how to perform that? any idea how to perform that in a vectorized way so as to get matrixes as outputs?
 A: If I understand correctly, you have a sequence of observations $\{(X^t_1,\dots, X^t_p)\}_t$ and you want to compute the matrix
$$Corr(t)_{ij}=\sum_{t'=t-n+1}^t (X^{t'}_i-\mu_i^{t})(X^{t'}_j-\mu_j^{t})\left(\sum_{t'=t-n+1}^t (X_i^{t'}-\mu_i^t)^2\sum_{t'=t-n+1}^t (X^{t'}_j-\mu_j^t)^2\right)^{-1/2}$$
where $\mu_i^t=n^{-1}\sum_{t'=t-n+1}^t X^{t'}_i$ is the n-lag mean. Like I mentioned above, you can write this in terms of the lag-n covariance matrix in the usual way, so it is enough to compute the covariance $Cov(t)_{ij}=n^{-1}\sum_{t'=t-n+1}^t (X^{t'}_i-\mu_i^{t})(X^{t'}_j-\mu_j^{t})$, from which you can read off the correlations.
I think the easiest way to do it is to keep track of both the mean vector $\mu^t_i$ as well as the "uncentered covariances" $CovU(t)_{ij}=n^{-1}\sum_{t'=t-n+1}^t X^{t'}_iX^{t'}_j$. Each of these can be updated in responses to a new observation simply by adding and removing one value at a time.
Then once you have updated these values, you can read off the covariance by the formula $Cov(t)_{ij}=CovU(t)_{ij}-\mu^t_i\mu^t_j$ and likewise the correlations by $Corr(t)_{ij}=Cov(t)_{ij}/\sqrt{Cov(t)_{ii}Cov(t)_{jj}}$.
Also, depending on what you ultimately want to do, it may be worth trying an exponentially weighted moving average, rather than a hard cutoff. This has the advantage that you only have to store the previous estimate (rather than the previous estimate, as well as the previous n observations), and the update equation is considerably simpler.
A: Disclaimer: This is the notation taught to me by an engineering professor not a statistician.
Answer:
This is the mean over N elements:
$$ \mu_{N} = \frac{1}{N}\Sigma_{i=1}^{N} x_i$$
We can split out the last element like this:
$$ \mu_{N} = \frac{1}{N}\Sigma_{i=1}^{N-1} x_i + \frac{1}{N} x_N$$
We can re-contrive the sum term as the mean of $N-1$ elements:
$$ \mu_{N} = \left(\frac{N-1}{N}\right)\left(\frac{1}{N-1}\Sigma_{i=1}^{N-1} x_i \right) + \frac{1}{N} x_N$$
With substitution this becomes:
$$ \mu_{N} = \left(\frac{N-1}{N}\right)\left(\mu_{N-1} \right) + \frac{1}{N} x_N$$
So we have a 2-term update running mean, also called EWMA.
There is a similar definition for the variance:
$$ \sigma_{N}^2 = \frac{1}{N}\Sigma_{i=1}^{N-1} \left(x_i - \mu_{N}\right)^2   $$
We split out the last element as:
$$ \sigma_{N}^2 =  \frac{1}{N}\Sigma_{i=1}^{N} \left(x_i - \mu_{N}\right)^2 + \frac{1}{N} \left(x_N - \mu_{N}\right)^2 $$
We can then recontrive the sum over $N-1$ elements:
$$ \sigma_{N}^2 =  \frac{N-1}{N} \left( \sigma_{N-1}^2 \right) + \frac{1}{N} \left(x_N - \mu_{N}\right)^2 $$
You could extend this to multiple variables with some algebra, and it should be relatively quick to update. You will need a measure of central tendency, so you might want to use the running mean to estimate the true mean.
