# Solve equation with matrix variable

I want to solve a matrix $$\Omega$$ from a equation $$\sum_k (\Omega + \Theta_k)^{-1} = Q$$. The $$Q$$ and $$\Theta, \forall k=1,\ldots,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.

• What is known about $\Theta_{k}$? Are they, perhaps, of low rank? Nov 27, 2012 at 0:03
• There might not always be a positive definite solution; are you ok with negative solutions? Nov 27, 2012 at 1:00
• 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. Nov 27, 2012 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. Nov 27, 2012 at 3:44
• Hi Suvrit, by definition, $\Omega$ is the inverse covariance matrix of multivariate Gaussian. So I need it to be positive definite. Nov 27, 2012 at 3:47

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

Lemma (Existence). If all $$\Theta_i$$ are (strictly) positive definite, then \eqref{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 \eqref{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.

• 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. Nov 27, 2012 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) Nov 27, 2012 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. Dec 7, 2012 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! Dec 10, 2012 at 5:28
• @Suvrit -- I would like to ask you if you eventually managed to prove that your proposed nonlinear mapping $\mathcal{G}$ is contractive w.r.t. a suitable metric. I ask you this because I found a kind of similarity with another nonlinear matrix mapping (see here) which I have been struggling to prove convergence for quite a long time. Thanks in advance for your help. Jan 6, 2016 at 12:01