# complexity of computing the singular vector corresponding to the smallest singular value

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.

• 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. – Nawaf Bou-Rabee Dec 18 '16 at 1:15
• @NawafBou-Rabee: I agree. – Manos Dec 18 '16 at 1:18
• You want the smallest nonzero singular value, right? Even then, what if there are multiple equal (or nearly equal) values? – Brian Borchers Dec 19 '16 at 6:13
• @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. – Manos Dec 19 '16 at 13:58

• 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. – Manos Dec 18 '16 at 22:42