1
$\begingroup$

Consider calculating the inverse of matrix sum

$$A+B$$

where A is a symmetric dense matrix while B is a symmetric block diagonal matrix. I am interested in finding an efficient approach to update the inverse of the sum A+B if the values in one of the diagonal blocks of matrix B are multiplied by a real value s.

So my question is equivalent to updating the inverse of

$$A+B*K$$

where A and B are defined as above, and K is a diagonal matrix with some diagonal entries (corresponding to one block of B) being s while rest being 1. Is there a possible way for efficient iterative update of matrix inverse (A + B * K)-1 when s is changing?

Thanks.

$\endgroup$
  • $\begingroup$ I'm not familiar with the term 'dense matrix'. Can you please define? $\endgroup$ – David H Oct 21 '13 at 22:03
  • $\begingroup$ @DavidH "Dense" = "not sparse". $\endgroup$ – Vedran Šego Oct 21 '13 at 22:03
  • $\begingroup$ @VedranŠego Gotcha. Thanks. $\endgroup$ – David H Oct 21 '13 at 22:04
2
$\begingroup$

I think that this depends on the rank of the changed diagonal block in $B$.

The only thing that comes to mind is Sherman–Morrison formula, but this would require $r$ updates for if the rank of the block in question was $r$.

Also, to find the vectors $u$ and $v$ for each of these updates, one would probably also need an SVD, or - given that this is symmetric - the Eigenvalue decomposition of that diagonal block.

There may be better methods, more specific to what you want, but I'm not familiar with them.

$\endgroup$
  • $\begingroup$ Much appreciated for your reply, Vedran. I also find Woodbury matrix identity which is a more general case of Sherman Morrison formula. I am going to check whether I can get vectors u and v for the Sherman-Morrison formula cheaply. $\endgroup$ – webappl Oct 21 '13 at 23:19
  • $\begingroup$ Thank you for accepting this answer, but I suggest that you unaccept it for now, and wait a day or two longer. Someone may have a better answer for you, and they might not check the question if they see that it has an accepted answer. If you get no better answers by, let's say, Thursday, THEN (re)accept this answer (and maybe ask the question on MathOverflow). $\endgroup$ – Vedran Šego Oct 21 '13 at 23:29
  • $\begingroup$ Vedran, thanks for your kind suggestion. $\endgroup$ – webappl Oct 21 '13 at 23:35

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.