3
$\begingroup$

I have a single sparse matrix $A$ for which I can easily compute $Ax$ and $A^*x$ and I would like to solve $\min(||Ax||) \text{ s.t. } ||x||=1$. I know the answer is the right singular vector associated with the smallest singular value, and thus I can use something like Lanczos (or one of the modern bells-and-whistles versions) to find the smallest singular value. However, I've seen a lot of people warning me that Lanczos is numerically unstable especially for rank-deficient matrices (I know that $A$ should, in general, be 1-less than full rank -- that is, in the noiseless case, $Ax=0$ should have a non-trivial solution). Is there something smarter that I should be using?

$\endgroup$
1
$\begingroup$

If your sparse matrix isn't too large and you can store it in memory, you could use a sparse (rank-revealing) QR (or LU, or SVD) factorization to determine the kernel of your matrix $A$.

Alternately, if you know something about the spectrum of your operator, you could apply a shift to it -- solve for eigenvectors associated with an eigenvalue of $\lambda$ for $A' = A + \lambda I$ -- using (inverse) Lanczos iteration. The rate of convergence depends on the separation of the eigenvalue you're solving for (the largest/smallest eigenvalue of the shifted matrix) from the remainder of the spectrum. The larger the separation, the larger the rate of convergence. Picking $\lambda$ close to zero will probably work; generally, for shift-and-invert strategies, the shift parameter is chosen to be close to the desired eigenvalue, but not the exact eigenvalue. You might have to be careful about conditioning issues, because you'll have to invert the shifted matrix; hopefully you have a good preconditioner, if you're only interested in using Krylov subspace methods.

$\endgroup$
  • $\begingroup$ Thanks! Alas, my matrix is going to be way too large to explicitly store in memory. I'll try the shift strategy! $\endgroup$ – Eric J Jul 16 '14 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.