0
$\begingroup$

[Also posted here: https://mathoverflow.net/q/464433/]

Many good algorithms are out there computing truncated SVD: https://mathoverflow.net/q/161252.

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

  1. 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.
  2. For such huge epsilon, the inequality does not really hold in general in practice when the algorithm halts.
$\endgroup$
6
  • 1
    $\begingroup$ Why do you need $\mu>0$? As far as I know you can also use $\mu=0$ or $\mu<0$ in shift-and-invert Arnoldi. $\endgroup$ Commented Feb 19 at 11:43
  • $\begingroup$ @FedericoPoloni You are right. But here, we already know a priori that all eigenvalues are non-negative, so $\mu<0$ does not help at all. $\endgroup$
    – Ma Joad
    Commented Feb 19 at 12:11
  • 1
    $\begingroup$ @MaJoad Then don't you know a lower bound of $\sigma_{\min}$, namely $0$? $\endgroup$
    – lightxbulb
    Commented Feb 19 at 12:13
  • $\begingroup$ @lightxbulb Yes, but this bound might not be good enough to reasonably speed up convergence! $\endgroup$
    – Ma Joad
    Commented Feb 19 at 12:44
  • $\begingroup$ Do you know anything about the structure or distribution of $A$ a priori? There may be some heuristics from tail estimates in random matrix theory that could provide decent first guesses. $\endgroup$
    – whpowell96
    Commented Feb 19 at 17:59

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.