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.
Best Answer
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.