I am using a calculation of the Variance-Covariance matrix in a program I wrote (for Principal Component Analysis), and am wondering what the complexity of it is. While obviously the Eigenvector decomposition is causing the largest performance hit, I am wondering how much of that hit is caused by the Covariance Matrix computation.

The asymptotic running time I estimate it to use is $O(N\cdot n^2)$ using a naive algorithm, because it has to take the means of all the data of size $N$ and then has to do it for every dimension (where $n$ is the number of dimensions) in a nested iteration, and thus producing a $n^2$ size matrix.

Is my assumption correct, or if not what is the asymptotic complexity?


Your conjecture is correct.

If $X\in \mathbb{R}^{N \times n}$ with $N$ as number of datapoints and $n$ being the number of features, then you can obtain the covariance matrix by $X^TX$ (apart from the mean subtraction which can be ignored from a complexity perspective).

Thus, covariance matrix computation is matrix multiplication which is naively indeed in $\mathcal{O}(Nn²)$ see here, since you have to do roughly $2N$ operations to fill every of the $n²$ positions in your covariance matrix $X$. In practice, matrix multiplication is speeded up to $\mathcal{O}(n^{2.73})$ for quadratic matrices (see the link).

| cite | improve this answer | |

Your Answer

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

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