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.
4
-
$\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-RabeeCommented Dec 18, 2016 at 1:15
-
$\begingroup$ @NawafBou-Rabee: I agree. $\endgroup$– ManosCommented Dec 18, 2016 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 BorchersCommented Dec 19, 2016 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$– ManosCommented Dec 19, 2016 at 13:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Dec 18, 2016 at 2:22
-
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$– ManosCommented Dec 18, 2016 at 22:42