Find a single vector in the null space

Question

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?

Answer 1

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.