I am computing pairwise correlation between the N rows of a matrix $X_{(N,G)}$ using two methods.

1- Direct computation

Zx is the z-scored X along the columns


2- On-line computation

In this case, we assume that we know the correlation (and the covariance) of the N-1 rows and we would like to compute the new correlation using a new observation $x_n$.

To compute the correlation on-line between two vectors X and Y, I used the following formula:




The standard deviation is computed on-line using this formula:


Where we also use the computation of the mean on-line

$\bar X_n = n^{-1}[X_n + (n-1)\bar X_{n-1}]$

My question is when does it become interesting (in memory usage and/or speedup) to use on-line versus direct (there is only one step in on-line method)?

The first approach is in $O(G*N^2)$ but I could not figure out the complexity of the second approach.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.