Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given two matrices $X$ and $Y$, it's easy to take the inverse of their Kronecker product:

$(X\otimes Y)^{-1} = X^{-1}\otimes Y^{-1}$

Now, suppose we have some diagonal matrix $\Lambda$ (or more generally an easily inverted matrix, or one for which we already know the inverse). Is there a closed-form expression or efficient algorithm for computing $(\Lambda + (X\otimes Y))^{-1}$?

share|improve this question
    
+1 What's the motivation for your question? –  draks ... Jan 30 '13 at 21:37
1  
I have a convex optimization problem I'm trying to solve, and the Hessian of the objective takes the form above. If I can compute the inverse Hessian efficiently I can use Newton's method, which is far preferable to gradient methods. –  David Pfau Jan 30 '13 at 22:36
add comment

1 Answer

up vote 1 down vote accepted

yes there is.

See equation 5 in http://books.nips.cc/papers/files/nips24/NIPS2011_0443.pdf

Stegle et al. Efficient inference in matrix-variate Gaussian models with iid observation noise

share|improve this answer
    
The matrices corresponding to $X$ and $Y$ in the cited paper are positive semidefinite and $\Gamma$ is a multiple of $I$, but I think what the OP asks for is more general. –  user1551 Feb 27 '13 at 8:49
    
Yes, its not a complete answer, I agree... but I think the eigen value decomposition as given in the paper will allow at least a partial solution. –  David Rohde Mar 4 '13 at 4:40
    
To elaborate further... the matrix must be diagonalizable.... maybe another matrix decomposition method could be used in the general case The expression for the inverse is given here en.wikipedia.org/wiki/Eigendecomposition_of_a_matrix I haven't checked, but I think the \Gamma is a multiple of I can be dealt with i.e. this constraint can be at least paritaly removed . So to qualify, I haven't given a full answer here (because, I don't know) - but I think this is the right approach... –  David Rohde Mar 4 '13 at 4:42
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.