<p>I've been reading a paper on Sparse PCA, which is:
<a href="http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf" rel="nofollow">http://stats.stanford.edu/~imj/WEBLIST/AsYetUnpub/sparse.pdf</a></p>

<p>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))$.</p>

<p>Can someone please explain how/why?</p>

CC BY-SA 3.0
2013-12-11T12:08:03.613Z
I think it has to do with the fact that the number of principal components is min(p,n).
George
CC BY-SA 3.0
2016-08-12T05:27:20.953Z
An answer is here : http://scicomp.stackexchange.com/q/3220/1316
Abhinav
<machine-learning><time-complexity><matrices>
How is the complexity of PCA $O(\min(p^3,n^3))$?
GrowinMan
# How is the complexity of PCA $O(\min(p^3,n^3))$?

(Asked by: username_0 on 2013-12-10)

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?

**Tags:** machine-learning, time-complexity, matrices

> **Comments:**
> **username_1**: I think it has to do with the fact that the number of principal components is min(p,n).  
> **username_2**: An answer is here : http://scicomp.stackexchange.com/q/3220/1316  

---

## 0 answers

