How is the complexity of PCA O(min(p^3,n^3))?

Question

I've been reading a paper on Sparse PCA, which is: http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf

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?

Answer 1

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!