6
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ What is known about $\Theta_{k}$? Are they, perhaps, of low rank? $\endgroup$ Nov 27, 2012 at 0:03
  • $\begingroup$ There might not always be a positive definite solution; are you ok with negative solutions? $\endgroup$
    – Suvrit
    Nov 27, 2012 at 1:00
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 27, 2012 at 1:43
  • $\begingroup$ Felix, $\Theta_k$ are not necessarily low rank, but they are sparse matrices. And I just edited the question for this information. $\endgroup$
    – Wei Liu
    Nov 27, 2012 at 3:44
  • $\begingroup$ Hi Suvrit, by definition, $\Omega$ is the inverse covariance matrix of multivariate Gaussian. So I need it to be positive definite. $\endgroup$
    – Wei Liu
    Nov 27, 2012 at 3:47

1 Answer 1

6
$\begingroup$

Here is a partial solution to the first question in the original post. Let's look at the equation \begin{equation}\label{1}\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 \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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 27, 2012 at 9:08
  • $\begingroup$ 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) $\endgroup$
    – Suvrit
    Nov 27, 2012 at 18:06
  • $\begingroup$ 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. $\endgroup$
    – Wei Liu
    Dec 7, 2012 at 17:44
  • $\begingroup$ @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! $\endgroup$
    – Suvrit
    Dec 10, 2012 at 5:28
  • $\begingroup$ @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. $\endgroup$
    – Ludwig
    Jan 6, 2016 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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