Running (one pass) calculation of covariance

Question

I got a set of 3d vectors (x,y,z), and I want to calculate the covariance matrix without storing the vectors.

I will do it in C#, but eventually I will implement it in C on a microcontroller, so I need the algorithm in itself, and not a library.

Pseudocode would be great also.

Answer 1

The formula is simple if you have Matrix and Vector classes at hand:

Vector mean;
Matrix covariance;
for (int i = 0; i < points.size(); ++i) {
  Vector diff = points[i] - mean;
  mean += diff / (i + 1);
  covariance += diff * diff.transpose() * i / (i + 1);
}
covariance *= 1 / points.size()

I personally always prefer this style rather than the two-pass calculation. The code is short and the results are flawless.

Matrix and Vector can have fixed dimension and can be easily coded for this purpose. You can even rewrite the code into discrete floating-point calculations and avoid computing the symmetric part of the covariance matrix.

Note that there is a vector outer product on the second last row of code. Not all vector libraries interpret it correctly.