Many good algorithms are out there computing truncated SVD: What is the time complexity of truncated SVD?.
I am trying to implement some codes to find the smallest singular value of a big matrix $A$. ARPACK can do that via eigenvalues of $M = A^\ast A,$ using Arnoldi methods. However, the "naive" version converges extremely slow when eigenvalues are clustered together.
The shift-and-invert technique speed up convergence a lot. Suppose that we know $\mu>0$ is very close to $\sigma_\text{min}>\mu,$ the smallest singular value of $M.$ Then we can consider $(M-\mu I)^{-1}$ which "pulls" clusters of eigenvalues apart.
The issue is that - this technique requires a lower bound on $\sigma_\text{min},$ which I do not know any algorithm to calculate. And frankly, obtaining a lower bound seems a very necessary thing on its own - otherwise how can we be sure that the Arnoldi iterates are accurate? Does anybody know such an algorithm?
By the way, the stopping criterion of ARPACK is designed so that we can "expect" $$ |\lambda_c - \lambda_a| \leq \epsilon |\lambda_c| $$ where $\epsilon$ is the error tolerance parameter, $\lambda_c$ the computed eigenvalue, and $\lambda_a$ the closest actual eigenvalue. This does not help my question because
- Guaranteeing this stopping criterion makes the algorithm extremely slow, even with huge $\epsilon$ like $0.5.$ Conceptually the inequality above is way stronger than what I need.
- For such huge epsilon, the inequality does not really hold in general in practice when the algorithm halts.
