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

matrix machine-learning time-complexity pca
GrowinMan picture GrowinMan · Dec 11, 2013 · Viewed 15.4k times · Source

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

Don Reba picture Don Reba · Dec 11, 2013

Covariance matrix computation is O(p2n); its eigen-value 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 fixed time, which is patently false.

Related questions

How to define a two-dimensional array?

I want to define a two-dimensional array without an initialized length like this: Matrix = [][] but it does not work... I've tried the code below, but it is wrong too: Matrix = [5][5] Error: Traceback ... IndexError: list index out of range What is …

Read More
How do I find the length (or dimensions, size) of a numpy matrix in python?

For a numpy matrix in python from numpy import matrix A = matrix([[1,2],[3,4]]) How can I find the length of a row (or column) of this matrix? Equivalently, how can I know the number of rows or columns? So far, the …

Read More
numpy matrix vector multiplication

When I multiply two numpy arrays of sizes (n x n)*(n x 1), I get a matrix of size (n x n). Following normal matrix multiplication rules, a (n x 1) vector is expected, but I simply cannot find any information …

Read More