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 VegaOct 16, 2015 at 7:06

$\begingroup$ Your title says approximated, but your question text doesn't. $\endgroup$– Federico PoloniDec 17, 2015 at 20:20
3 Answers
@ 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$ May 31, 2016 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$ Jun 1, 2016 at 16:43

1$\begingroup$ @loupblanc Thank you for the update. I do not doubt your answer. I am just confused that
sklearn
 a widely used package  report the wrong complexity. $\endgroup$– MichaelApr 23, 2019 at 17:28 
1$\begingroup$ Can anyone comment on why the SVD of S is similar to that of A? As far as I can tell, they are not only different but incomparable (the right singular vectors have different sizes for A and S). And even the singular values themselves are very different when I generate random matrix. Do I misunderstand that you suggest to just take the SVD of S and use it as an approximation of the SVD of A or is there more to it? $\endgroup$ May 15, 2020 at 15:58

1$\begingroup$ @Tan, I wrote about the complexity of the full SVD because the OP gave a wrong estimate of it. For the truncated SVD, have a look on the jin's answer. If $k$ is small, then the complexity of an iteration is roughly $O(mnk)$. If $A$ is illconditioned, then you have to do a lot of iterations. $\endgroup$ Jan 12, 2022 at 18:40
According to the man page of svds, provided by MATLAB, svds is currently based on "Augmented Lanczos Bidiagonalization Algorithm" when it comes to the top$k$ 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 top$k$ 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\big(T(Ak + k^3 + c)\big) $$ 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.
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

1$\begingroup$ This link is no orphan. Can someone post an updated link/ reference? $\endgroup$– simarFeb 11, 2021 at 20:47