9
$\begingroup$

What is the best algorithm for computing covariance that would be accurate for a large number of values like 100,000 or more?

$\endgroup$
1
  • $\begingroup$ One quick note. I know some people will think this is basic but I have looked in a lot of places (numerical analysis texts, computational statistics texts and google scholar) and I've never seen it discussed. Doing the straightforward thing does not work for large datasets. $\endgroup$
    – Kim Greene
    Nov 18, 2009 at 20:26

3 Answers 3

8
$\begingroup$

Check out How to calculate correlation accurately. There are two common formulas that are algebraically equivalent but one has much better numerical properties than the other.

$\endgroup$
2
  • 1
    $\begingroup$ Yes, but that is only a partial answer. The problem is that the “good” formula requires two passes over the data, one to compute the arithmetic means and one to compute the quadratic sums. It would be very handy to have an algorithm that uses only a single pass, yet is numerically stable. Surely, someone must have thought of one? It doesn't seem to me an intractable problem. $\endgroup$ Nov 18, 2009 at 21:53
  • 2
    $\begingroup$ Here's a way to compute standard deviation in one pass. I imagine you could take the ideas from this algorithm to create an accurate single-pass algorithm for covariance. johndcook.com/standard_deviation.html $\endgroup$ Nov 19, 2009 at 0:17
6
$\begingroup$

The single-pass and parallel versions at Wikipedia may be what you're looking for. The single pass version is more numerically stable, but moves a division into the inner loop, which may hurt performance.

$\endgroup$
3
$\begingroup$

A single pass stable algorithm has been discovered in the time since this question has been originally answered:

Bennett, Janine, et al. "Numerically stable, single-pass, parallel statistics algorithms." Cluster Computing and Workshops, 2009. CLUSTER'09. IEEE International Conference on. IEEE, 2009.

An implementation is given in Boost.

$\endgroup$
4
  • $\begingroup$ It's online, but crazy slow. $\endgroup$
    – Anton K
    Apr 1, 2022 at 6:17
  • $\begingroup$ Data to support that claim? $\endgroup$
    – user14717
    Apr 1, 2022 at 18:40
  • $\begingroup$ My own experience with VTK. Not peer-reviewed. $\endgroup$
    – Anton K
    Apr 1, 2022 at 21:14
  • $\begingroup$ This file tests the performance of the boost implementation: github.com/boostorg/math/blob/develop/reporting/performance/… ; IIRC there was nothing slow about it. $\endgroup$
    – user14717
    Apr 1, 2022 at 22:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.