0
$\begingroup$

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

$C_n=\frac{Zx'*Zx}{(N-1)}$

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:

$COV_{n}(X,Y)=\frac{COV_{n-1}(X,Y).(N-1)+\frac{N}{N-1}(x-\bar{x_n})(y-\bar{y_n})}{N}$

then

$C_n=\frac{COV_{n}}{\sigma_{x,n}\sigma_{y,n}}$

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

$\sigma_n^2=\frac{n-2}{n-1}\sigma^2_{n-1}+\frac{1}{n}(X_n-\bar{X_{n-1}})^2$

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.

$\endgroup$

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.