# How to calculate the inverse of the sum of two eigen-decomposed matrices

The are two eigen-decomposed matrices $A$ = $U_1$$V_1$$U_1$$^H, B = U_2$$V_2$$U_2$$^H$, in which $V_1$ and $V_2$ are the eigen-matrices formed by the non-negative eigenvalues and the eigenvalues are all less than 1, $U_1$ and $U_2$ are unitary matrices formed by the eigenvectors. Is there any efficient way (including any efficient iterative solution) to calcualte the following vector?

$y$ = ($A$+$B$+$I$)$^{-1}$$x$

in which $I$ is the identity matrix, and $x$ could be an arbitrary vector.

Thanks for any discussions.

-
is $x$ given? Are $U, V$ unitary matrices? –  Betrand Dec 6 '12 at 19:42
You are right. x is a given vector. U1 and U2 are the unitary matrices, while V1 and V2 are diagonal matrices, formed by the eigen-vectors of A and B respectively. –  Soup Dec 7 '12 at 6:42
I think there is no general trick, unless $A$ or $B$ have very low rank or share a large eigenspace. There is much research going on on recycling subspaces in Krylov method, but unfortunately there are no easy formulas giving the answers you want. –  Federico Poloni Dec 7 '12 at 14:42
What if $A$ or $B$ have very low rank (but do not share a large eigenspace)? Any solution for this scenario? Thanks. –  Soup Dec 7 '12 at 17:32

In general we cannot do much to exploit the eigendecompositions. But assuming that either $A$ or $B$ has low-rank, we can exploit the situation. Let me outline the details below.

Let $A=UDU^\ast$ and $B=VLV^\ast$ be the decompositions. The question asks for a solution of $(I+A+B)y=x$. Consider therefore,

$$A + B + I = U( D + U^\ast VLV^\ast U + I)U^\ast = U(D' + WLW^\ast)U^\ast,$$ so that using $\bar{y}=U^\ast y$, $\bar{x}=U^\ast x$, we may write the linear system as $$(D' + WLW^*)\bar{y} = \bar{x}.$$ We can now obtain the solution $\bar{x}$ by inverting $(D' + WLW^\ast)$ using the Matrix inversion lemma (SMW)---this lemma applies because $D'$ is invertible, and assuming $B$ is low-rank, we have $WLW^\ast = \sum_i l_i w_iw_i^\ast$, which can be exploited in the SMW formula.

-
So we only need to inverse a matrix with the size = rank($B$), right? This is a good solution. Thank you very much! –  Soup Dec 11 '12 at 7:08
Yes, $WLW^\ast = PCR$, where $P$ is $n\times k$, $C=I_k$, and $R$ is $k \times n$, when applying the SMW formula. –  Suvrit Dec 11 '12 at 17:01