3
$\begingroup$

I'm interested in computing the minimal 2-norm least squares solution for a possibly rank deficient (or numerically rank deficient) large sparse matrix A that's hidden behind some black box routine $F$. ($F(v)$ computes $Av$ for some vector $v$)

What are some efficient methods or resources I can look at for solving this?

Right now I'm only familiar with ways this can be solved with factorizations given a local copy of the matrix. Such as those in Golub/Van-Loan's Matrix Computations: TSVD, Regularized SVD, or Rank Revealing Pivoted QR.

Is there a common way to modify CGNE or CGNR to tackle the rank deficient case? What other iterative methods are there? Is it reasonable to form a randomized approximation to the SVD (such as CUR) and proceed with TSVD from there?

Edit: On further thought I think I could use Tikhonov regularization with CGNR by just replacing the inner product step with $ \langle Ax, Ax \rangle + \langle \Gamma x,\Gamma x \rangle $ (where $\Gamma$ is full rank). But I'm still curious about other methods!

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.