# What is the time complexity of truncated SVD?

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)?

• Can you add a reference for your bound? I presume that bound is for the zero-error SVD? Are you only interested in that case? Do you care about the bit-size of the entries and condition numbers? – Juan Bermejo Vega Oct 16 '15 at 7:06
• Your title says approximated, but your question text doesn't. – 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 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)$$.

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.

• 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? – Alex Williams May 31 '16 at 21:39
• 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 – loup blanc Jun 1 '16 at 16:43
• @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$. – cangrejo Apr 5 '17 at 14:03
• Isn't this in contradiction to what is written in this sklearn documentation on PCA?: scikit-learn.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})$. – Michael Apr 10 '19 at 12:16
• @Michael cf. my edit. – loup blanc Apr 14 '19 at 18:28