4
$\begingroup$

I am in a situation where as part of a sort of inverse power method scheme, I want to very often perform the following step:

  1. Apply a symmetric rank one update $uu^\top$ to my inverse matrix $A^{-1}$
  2. Compute the QR decomposition of my updated inverse

Right now, I'm using Sherman-Morrison-Woodbury formula to update my inverse:

  1. Update $A^{-1}$ with Sherman-Morrison-Woodbury:
    • Let $a = 1 / (1 + u^\top A^{-1} u)$
    • Update $A^{-1} \gets A^{-1} - a A^{-1} u u^\top A^{-1}$

and then I'm recomputing the QR from scratch:

  1. Recompute QR: $QR = A^{-1}$.

However, I'm aware that it's possible to efficiently update a QR decomposition with a low-rank update. Unfortunately, as we can see above the Sherman-Morrison update looks to be full rank, so we can't make use of the QR update.

I'm doubtful, but maybe there is some approach I am missing that can avoid the hit of recomputing the whole QR?

(Also: there are a lot of other questions here about low rank updates of different factorizations here, and I didn't see anything along these lines. Also, I have looked through Matrix Computations without success.)

$\endgroup$
2
$\begingroup$

The update on the inverse is actually rank-one. You can group the terms as $(A^{-1}u)(A^{-1}u)^T$ because of the symmetry of $A$.

$\endgroup$
  • 1
    $\begingroup$ Good answer, but here the symmetry of A is irrelevant I think. $\endgroup$ – Federico Poloni Oct 29 at 21:13
  • $\begingroup$ Of course, thanks cdipaolo! And yeah I guess it works even without symmetry, although in my case the expression here is great. $\endgroup$ – cwindolf Oct 29 at 21:42

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.