@ user40484 , fortunately your estimate for the complexity of SVD is not optimal. Otherwise, you put unemployed specialists in image compression. The complexity is in $O(\min(mn^2,m^2n))$.

Assume the data points are in the columns of $A\in M_{m,n}(\mathbb{R})$ where $m\leq n$. Note that $AA^T$ is the dataset covariance matrix. Then a simple method is to randomly choose $k<m$ columns of $A$ that form a matrix $S$. Statistically, the SVD of $SS^T$ will be close to that of $AA^T$; thus it suffices to calculate the SVD of $S$, the complexity of which, is only $O(k^2m)$.

EDIT. Answer to Michael.

Let $A\in M_{m,n}$ where $m\geq n$ (otherwise change $A$ into $A^T$.

In "matrix computations", Golub-Van loan gave $O(m^2n)$ as complexity for the svd. The authors calculate $A^TA$ with complexity $nm^2$ and its eigenvalues with complexity $\approx 20n^3$... Non-tiring work.

The good idea is to find the eigenvalues of $A^TA$ without computing $A^TA$.

First step. Reduce $A$ into a $n\times n$ bidiagonal matrix $B$.

Second step. Compute the singular values and vectors of $B$.

This method has complexity $O(mn^2)$.

@ user40484 , fortunately your estimate for the complexity of SVD is not optimal. Otherwise, you put unemployed specialists in image compression. The complexity is in $O(\min(mn^2,m^2n))$.

Assume the data points are in the columns of $A\in M_{m,n}(\mathbb{R})$ where $m\leq n$. Note that $AA^T$ is the dataset covariance matrix. Then a simple method is to randomly choose $k<m$ columns of $A$ that form a matrix $S$. Statistically, the SVD of $SS^T$ will be close to that of $AA^T$; thus it suffices to calculate the SVD of $S$, the complexity of which, is only $O(k^2m)$.

EDIT. Answer to Michael.

Let $A\in M_{m,n}$ where $m\geq n$ (otherwise change $A$ into $A^T$.

In "matrix computations", Golub-Van loan gave $O(m^2n)$ as complexity for the svd. The authors calculate $A^TA$ with complexity $nm^2$ and its eigenvalues with complexity $\approx 20n^3$... Non-tiring work.

The good idea is to find the eigenvalues of $A^TA$ without computing $A^TA$.

First step. Reduce $A$ into a $n\times n$ bidiagonal matrix $B$.

Second step. Compute the singular values and vectors of $B$.

This method has complexity $O(mn^2)$.

Reference for the method

http://www.cs.utexas.edu/users/inderjit/public_papers/HLA_SVD.pdf

I have no reference for the calculation of its complexity.

@ user40484 , fortunately your estimate for the complexity of SVD is not optimal. Otherwise, you put unemployed specialists in image compression. The complexity is in $O(\min(mn^2,m^2n))$.

Assume the data points are in the columns of $A\in M_{m,n}(\mathbb{R})$ where $m\leq n$. Note that $AA^T$ is the dataset covariance matrix. Then a simple method is to randomly choose $k<m$ columns of $A$ that form a matrix $S$. Statistically, the SVD of $SS^T$ will be close to that of $AA^T$; thus it suffices to calculate the SVD of $S$, the complexity of which, is only $O(k^2m)$.

@ user40484 , fortunately your estimate for the complexity of SVD is not optimal. Otherwise, you put unemployed specialists in image compression. The complexity is in $O(\min(mn^2,m^2n))$.

Assume the data points are in the columns of $A\in M_{m,n}(\mathbb{R})$ where $m\leq n$. Note that $AA^T$ is the dataset covariance matrix. Then a simple method is to randomly choose $k<m$ columns of $A$ that form a matrix $S$. Statistically, the SVD of $SS^T$ will be close to that of $AA^T$; thus it suffices to calculate the SVD of $S$, the complexity of which, is only $O(k^2m)$.

EDIT. Answer to Michael.

Let $A\in M_{m,n}$ where $m\geq n$ (otherwise change $A$ into $A^T$.

In "matrix computations", Golub-Van loan gave $O(m^2n)$ as complexity for the svd. The authors calculate $A^TA$ with complexity $nm^2$ and its eigenvalues with complexity $\approx 20n^3$... Non-tiring work.

The good idea is to find the eigenvalues of $A^TA$ without computing $A^TA$.

First step. Reduce $A$ into a $n\times n$ bidiagonal matrix $B$.

Second step. Compute the singular values and vectors of $B$.

This method has complexity $O(mn^2)$.