2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ is $x$ given? Are $U, V$ unitary matrices? $\endgroup$
    – Betrand
    Dec 6, 2012 at 19:42
  • $\begingroup$ 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. $\endgroup$
    – Soup
    Dec 7, 2012 at 6:42
  • 2
    $\begingroup$ 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. $\endgroup$
    – Federico Poloni
    Dec 7, 2012 at 14:42
  • $\begingroup$ What if $A$ or $B$ have very low rank (but do not share a large eigenspace)? Any solution for this scenario? Thanks. $\endgroup$
    – Soup
    Dec 7, 2012 at 17:32

1 Answer 1

Reset to default
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.