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

I have a matrix $K$ which is the sum of a identity and a Kronecker product of two symmetric matrices as following and I want to calculate the inverse of it $K^{-1}$. \begin{eqnarray} K=\mathbf{I}_{mn}+XX^\top\otimes YY^\top \end{eqnarray} where $X$ and $Y$ are $m\times p$ and $n\times q$ matrices respectively and $m>p,n>q$.

Since the size of Kronecker product of two matrices is the product of their sizes, the matrix to be inverted is very large. Can this calculation be simplified?

Using Woodbury matrix identity, the matrix to be inverted can be reduced from $mn\times mn$ to $pq\times pq$ as \begin{eqnarray} \left(\mathbf{I}+XX^\top\otimes YY^\top\right)^{-1} &=&\left(\mathbf{I}+(X\otimes Y)(X\otimes Y)^\top\right)^{-1}\\\ &=&\mathbf{I}-(X\otimes Y)\left(\mathbf{I}+(X\otimes Y)^\top(X\otimes Y)\right)^{-1}(X\otimes Y)^\top \end{eqnarray} However, in my application, $p$ and $q$ are not much less than $m$ and $n$. Thus inverting a $pq\times pq$ matrix is still a consuming work and I want to find a more simple calculation of $K^{-1}$.

Consider the following problem. If there is not the identity matrix $\mathbf{I}_{m\times n}$, we can invert $XX^\top$ and $YY^\top$ respectively and then calculate the Kronecker product as $$ (XX^\top\otimes YY^\top)^{-1}=(XX^\top)^{-1}\otimes(YY^\top)^{-1} $$ using the property of Kronecker product. However, if the identity item exists, this property cannot be utilized.

Then my question is that if there is any way to decompose the calculation of $K^{-1}$ into inverses of some smaller matrices whose size is linear with $m$ and $n$ but not their products? Or is it possible to extract the Kronecker product $\otimes$ out of the inverse?

If you have any suggestion or idea, please let me know. Thank you very much for your help!

share|improve this question
    
If $X$ is $m \times p$ with $m>p$, $(XX^T)^{-1}$ does not exist. –  Federico Poloni Jun 11 '12 at 16:16
    
Do you really need the inverse, or do you just want to solve linear systems with it? The latter task is much easier. For the inverse, I don't think there's anything better than what you already suggested with the Woodbury identity. –  Federico Poloni Jun 11 '12 at 16:19
    
@Federico Poloni, yes, you are right! $(XX^\top)^{-1}$ really does not exist. Thank you! –  ppyang Jun 12 '12 at 2:07
    
@Federico Poloni, thank you for your suggestion. What is more, the purpose that I took that example is to show that I want to simplify the calculation utilizing the property of Kronecker product, however, there is some mistake in it. Thank you! –  ppyang Jun 12 '12 at 2:12
    
@ppyang: So is the thing off or not? Because the original question still makes sense, I think. –  Felix Goldberg Jun 12 '12 at 9:08

1 Answer 1

up vote 4 down vote accepted

I assume spectral decomposition of a symmetric matrix does not cost too much. Let $PXX^TP=\Lambda_1$, $QYY^TQ=\Lambda_2$ be the spectral decomposition of $XX^T, YY^T$, respectively. Here $\Lambda_1, \Lambda_2$ are diagonal and $P, Q$ are orthogonal. Then $$K^{-1}=(P\otimes Q)^T(I+\Lambda_1\otimes \Lambda_2)^{-1}(P\otimes Q).$$

$(I+\Lambda_1\otimes \Lambda_2)^{-1}$ can be read directly.

share|improve this answer
    
You provide an excellent idea that reduce the most complex calculation of an $mn\times mn$ matrix into a $m\times m$ matrix and a $n\times n$ matrix, where the inverse is taken on only a diagonal. I think it solve my problem. Thank you very much! –  ppyang Jun 17 '12 at 11:38
    
You are welcome. –  Betrand Jun 17 '12 at 13:20

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.