Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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
add comment

1 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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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