Explore Courses Blog Tutorials Interview Questions
0 votes
in Machine Learning by (19k points)

I've been reading a paper on Sparse PCA, which is:

And it states that, if you have n data points, each represented with p features, then, the complexity of PCA is O(min(p^3,n^3)).

Can someone please explain how/why?

1 Answer

0 votes
by (33.1k points)

The complexity of Covariance matrix computation is O(p2n). Its eigenvalue decomposition is O(p3). So, the complexity of PCA is O(p2n+p3).

O(min(p3,n3)) would imply that you could analyze a two-dimensional dataset of any size in a fixed time.

For more details on the abovementioned topics, study Principal Component Analysis. One can also study Machine Learning Algorithms for a better grasp.

Hope this answer helps you!

Browse Categories