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