# 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? Dec 6, 2012 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, 2012 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. Dec 7, 2012 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, 2012 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,
\begin{equation} A + B + I = U( D + U^\ast VLV^\ast U + I)U^\ast = U(D' + WLW^\ast)U^\ast, \end{equation} so that using $\bar{y}=U^\ast y$, $\bar{x}=U^\ast x$, we may write the linear system as \begin{equation} (D' + WLW^*)\bar{y} = \bar{x}. \end{equation} 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!
• Yes, $WLW^\ast = PCR$, where $P$ is $n\times k$, $C=I_k$, and $R$ is $k \times n$, when applying the SMW formula. Dec 11, 2012 at 17:01