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

I want to solve a matrix $\Omega$ from a equation $\sum_k (\Omega + \Theta_k)^{-1} = Q$. The $Q$ and $\Theta, \forall k=1...K$ are known, and are positive definite matrices. $\Omega$ also has to be positive definite. all matrices are large (a few thousands of columns and rows). My questions are:

(1) Is there a closed-form solution? How do I simplify the sum of the inverse of two matrix sum?

(2) I'm OK to go for a numerical solution. But how do I define this problem? An optimization problem to minimize something like $f(\Omega) = ||\sum_k (\Omega + \Theta_k)^{-1} - Q||$? Do I need to minimize the frobenius norm, (just like minimizing the L-2 norm in a least square problem)? Considering the constraint that $\Omega$ is positive definite, can I solve it by semi-definite programming? How do I redefine the problem in a linear/semi-definite programming? I don't have much knowledge of linear programming. I would prefer a general gradient descent rather than LP. But I'm OK to use LP if I know how to do.

This problem comes from the estimation of inverse covariance matrix of multi-variate Gaussian distribution.

EDIT: Both $\Theta_k$ and $\Omega$ are sparse, if that helps.

share|improve this question
    
What is known about $\Theta_{k}$? Are they, perhaps, of low rank? –  Felix Goldberg Nov 27 '12 at 0:03
    
There might not always be a positive definite solution; are you ok with negative solutions? –  Suvrit Nov 27 '12 at 1:00
1  
How closed form would you want it to be? Even in the $1\times1$ case of real variables, this reduces to finding roots of polynomials, for which there is no closed form past degree 5. –  Ralph Furmaniak Nov 27 '12 at 1:43
    
Felix, $\Theta_k$ are not necessarily low rank, but they are sparse matrices. And I just edited the question for this information. –  Wei Liu Nov 27 '12 at 3:44
    
Hi Suvrit, by definition, $\Omega$ is the inverse covariance matrix of multivariate Gaussian. So I need it to be positive definite. –  Wei Liu Nov 27 '12 at 3:47
show 3 more comments

1 Answer

up vote 4 down vote accepted

Here is a partial solution to the first question in the original post. Let's look at the equation \begin{equation}\tag{1} \sum\nolimits_{i=1}^m (X+ \Theta_i)^{-1} = Q. \end{equation}

Lemma (Existence). If all $\Theta_i$ are (strictly) positive definite, then (1) has a positive semidefinite solution only if $Q \preceq \sum_i \Theta_i^{-1}$.

Proof. Suppose $Q=\sum_i \Theta_i^{-1}$, then clearly $X=0$ is the solution. Since, $(X+\Theta_i)^{-1} \preceq \Theta_i^{-1}$ for any $X \succeq 0$, on summing up we see that $Q \preceq \sum_i \Theta_i^{-1}$ must hold. Moreover, in this case if there is a solution, then it must be strictly positive definite. A little extra argument shows that in this case, there must exist a unique positive definite solution.

This lemma shows that in case $Q$ does not satisfy the requirement, the original equation has no solution, and it might be preferable to minimize $\|\sum_i (X+\Theta_i)^{-1}-Q\|_F^2$ instead.

Lemma (Bounds). Any feasible solution to (1) must lie in the set $\Omega := [0, mQ^{-1}]$.

Proof. The lower bound $X \succeq 0$ is obvious. Following an argument similar to the previous lemma, we see that $Q=\sum_i (X+\Theta_i)^{-1} \preceq \sum_i X^{-1}$, which implies that $m X^{-1} \succeq Q$, or equivalently, $X \preceq m Q^{-1}$.

Idea Now that we have a compact set $\Omega$, we just need to setup a strictly contractive nonlinear map $G : \Omega \to \Omega$. I have not proved strict contraction of the map below, but numerically it seems to work. As one might suspect from the above lemmas, the rate of convergence depends on $\|Q-\sum_i \Theta_i^{-1}\|$, so that for small values of this quantity, the iteration converges more slowly.

Suppose, that $X \succ 0$. Denote by $S^{++}$ the set of $n\times n$ strictly positive definite matrices. Then, define the nonlinear map $\mathcal{G} : S^{++} \to S^{++}$ as \begin{equation*} \mathcal{G} = X \mapsto X^{1/2}\left(\sum\nolimits_{i=1}^m Q^{-1/2}(X+\Theta_i)^{-1}Q^{-1/2}\right)X^{1/2}. \end{equation*}

TODO If I get time, I might think about proving that the above map generates convergent solutions. Or one can come up with some other fixed point iteration.

share|improve this answer
1  
I think that the technique in doi:10.1088/0951-7715/21/4/011 and doi:10.1016/j.laa.2008.10.034 can be applied to this problem. Short summary: composing sums, inversions and similarities should yield a contraction in the Finsler logarithmic metric on positive definite matrices; therefore, your matrix equation can be rewritten as $X=f(X)$ with $f$ a Finsler contraction; bingo. –  Federico Poloni Nov 27 '12 at 9:08
    
I would have written a Thompson metric contraction, but the presence of the $X^{1/2}$ in my iteration prevents that. Perhaps the papers that you cite still have a way around that (Also, it seems to not be the case that my iteration actually maps $\Omega \to \Omega$, but that is not so problematic, as we can always increase $\Omega$ in size until this gets ensured). But nevertheless, some version of the above idea can be made to work without too much difficulty (from its appearance it might be a contraction in some other less structured metric than the Finslerian class) –  Suvrit Nov 27 '12 at 18:06
    
Thanks Suvrit. The answer is so helpful. I'm not sure the Q satisfy the condition you gave, but at least the fixed point iteration gives me a starting point. It looks there is a 'nonlinear semidefinite problem' but it is far less explored. I'll give your solution a try, with the sparsity property of my matrices in mind. –  Wei Liu Dec 7 '12 at 17:44
    
@Wei -- as I showed above, if the $Q$ does not satisfy the conditions I mentioned, then your nonlinear equation has no solution, and you should rather solve a minimization problem---perhaps a technique similar to what I wrote above applies even here! –  Suvrit Dec 10 '12 at 5:28
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.