Full SVD, on an $m \times n$ matrix $A$, [U,S,V] = svd(A)
, would cost $O(m^2n + mn^2 + n^3)$ time. But what is the time complexity if we only need the $k$ largest singular values, say, [U_k,S_k,V_k] = svds(A,k)
?

2$\begingroup$ Can you add a reference for your bound? I presume that bound is for the zeroerror SVD? Are you only interested in that case? Do you care about the bitsize of the entries and condition numbers? $\endgroup$ – Juan Bermejo Vega Oct 16 '15 at 7:06

$\begingroup$ Your title says approximated, but your question text doesn't. $\endgroup$ – Federico Poloni Dec 17 '15 at 20:20
@ 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", GolubVan 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$... Nontiring 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.

$\begingroup$ What assumptions does this make on the columns of A? What if some columns of A are very dense or have a large norm, while others are sparse? $\endgroup$ – Alex Williams May 31 '16 at 21:39

$\begingroup$ You are right. If there is a too great disparity between the columns, then the approximation may be bad. In such cases, we must increase k $\endgroup$ – loup blanc Jun 1 '16 at 16:43

$\begingroup$ @AlexWilliams To prevent those problems, the norm of the columns is taken into account to draw them from a biased distribution and they are scaled before forming matrix $S$. $\endgroup$ – cangrejo Apr 5 '17 at 14:03

$\begingroup$ Isn't this in contradiction to what is written in this
sklearn
documentation on PCA?: scikitlearn.org/stable/modules/… it says complexity of PCA (which allegedly uses SVD internally) is $O(n_{max}^2n_{min})$. Yours says the opposite: $O(n_{min}^2 n_{max})$. $\endgroup$ – Michael Apr 10 '19 at 12:16 
Just as loup blanc's answer. Here is a link to a paper talking about this: http://sysrun.haifa.il.ibm.com/hrl/bigml/files/Holmes.pdf
According to the man page of svds, provided by MATLAB, svds is currently based on "Augmented Lanczos Bidiagonalization Algorithm" when it comes to the topk SVD computation of a largescale sparse matrix if k is small enough, instead of using the sampling technique answered by loup blanc (you can easily check it by typing edit svds in your MATLAB prompt). Please refer to the following paper:
 Baglama, James, and Lothar Reichel. "Augmented implicitly restarted Lanczos bidiagonalization methods." SIAM Journal on Scientific Computing 27.1 (2005): 1942.
This is considered as an anytime iterative algorithm, i.e., it iteratively computes and updates the target topk singular triplets until convergence. See Algorithm 3.1 of the above paper.
BTW, it is painful to strictly analyze the time complexity of Algorithm 3.1, since the algorithm is not that intuitive to capture the whole procedure and which part is the main bottleneck of the algorithm.
At a glance, it is considered as O(T(Ak + k^3 + c)) where T is # of iterations, A is # of nonzeros in the input sparse matrix A, k is the target number of the largest singular values, and c is the other computational cost for each step. Note that this might be wrong since it is roughly estimated based on sparse matrix multiplication and QR decomposition.
If k is not small enough, svds performs full svd based on sparseQR.