What is the time complexity of truncated SVD?

Question

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

Answer 1

@ 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.

Answer 2

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 large-scale 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): 19-42.

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(|A|k + k^3 + c)\big) $$ where

• $T$ is # of iterations,
• |A| is # of non-zeros 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.

Answer 3

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