4
$\begingroup$

It is known that the singular value decomposition of an $m \times n$ matrix $A$ is in general of complexity of the order $m n^2$, assuming that $m \ge n$. But what if we only want to compute say the singular vector corresponding to the smallest singular value? Can we do this significantly faster than $m n^2$ operations? Please note that $A$ is not assumed to have any specific structure, such as being sparse.

$\endgroup$
  • $\begingroup$ This seems to boil down to computing the smallest eigenvalue of the $n \times n$ matrix $A^T A$ and then calculating its associated eigenvector. However, if the matrix is not sparse, it naively seems like this cannot be done cheaply using iterative methods. $\endgroup$ – Nawaf Bou-Rabee Dec 18 '16 at 1:15
  • $\begingroup$ @NawafBou-Rabee: I agree. $\endgroup$ – Manos Dec 18 '16 at 1:18
  • $\begingroup$ You want the smallest nonzero singular value, right? Even then, what if there are multiple equal (or nearly equal) values? $\endgroup$ – Brian Borchers Dec 19 '16 at 6:13
  • $\begingroup$ @BrianBorchers: Actually what i really want is to compute a right nullvector of $A$. And when $A$ is full rank, i want to compute the right singular vector corresponding to its smallest singular value. I don't really care about computing the actual singular value though. And if there is some clustering of small singular values, then computing any corresponding singular vector would also do. $\endgroup$ – Manos Dec 19 '16 at 13:58
3
$\begingroup$

The question has been studied at some length. See, for example,

Hubert Schwetlick and Uwe Schnabel, MR 1997360 Iterative computation of the smallest singular value and the corresponding singular vectors of a matrix, Linear Algebra Appl. 371 (2003), 1--30.

And

Qiao Liang and Qiang Ye, MR 3291626 Computing singular values of large matrices with an inverse-free preconditioned Krylov subspace method, Electron. Trans. Numer. Anal. 42 (2014), 197--221.

I can't seem to find theoretical complexity result, but the practical performance seems comparable to computing the maximal singular value.

$\endgroup$
  • 1
    $\begingroup$ After looking at these papers and some others, i have the impression that the complexity is larger than that of computing the largest singular pair (which is $n^2$). I think the reason for this is that to compute the smallest singular pair iterative methods solve at each iteration some system of linear equations whose coefficient matrix is at least as large as $A$ (in an inverse power iteration style). Please let me know if you agree or think otherwise. $\endgroup$ – Manos Dec 18 '16 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.