8
$\begingroup$

Let $\{V_i\}_{i=1}^N$ be a set of $n\times m$, $n\geq m$, real matrices of full column rank and let $X=X^\top\in\mathbb{R}^{n\times n}$ be a positive definite trace-one matrix. Moreover, let $A^{1/2}=(A^{1/2})^\top$ denote the (unique) symmetric square root of a positive semi-definite matrix $A$, $\mathrm{tr}\, A$ the trace of $A$, and $\log A$ the matrix logarithm of $A$.

Question: Does the inequality $$\tag{$1$} \label{1} \sum_{i=1}^N \mathrm{tr}\log \left(\frac{1}{mN}\sum_{j=1}^N V_i^\top X^{1/2}V_j(V_j^\top X V_j)^{-1} V_j^\top X^{1/2}V_i\right) - \sum_{i=1}^N \mathrm{tr} \log \left(V_i^\top X V_i\right) \ge 0 $$ hold true?

My (very little) progress so far. Using the fact that $\mathrm{tr}\log Y+\mathrm{tr}\log Z=\mathrm{tr}\log YZ$ and $-\log\, Y=\log Y^{-1}$ for positive definite $Y$, $Z$, we can rewrite \eqref{1} as $$\tag{$2$} \sum_{i=1}^N \mathrm{tr}\log \left(\frac{1}{mN}\sum_{j=1}^N V_i^\top X^{1/2}V_j(V_j^\top X V_j)^{-1} V_j^\top X^{1/2}V_i\left(V_i^\top X V_i\right)^{-1}\right) \ge 0. $$ Also, exploiting the formula $\mathrm{tr}\log Y =\log \det Y$, we get $$\tag{$3$} \sum_{i=1}^N \log\det \left(\frac{1}{mN}\sum_{j=1}^N V_i^\top X^{1/2}V_j(V_j^\top X V_j)^{-1} V_j^\top X^{1/2}V_i\left(V_i^\top X V_i\right)^{-1}\right) \ge 0, $$ or, equivalently, $$\tag{$3$} \prod_{i=1}^N \det \left(\frac{1}{mN}\sum_{j=1}^N V_i^\top X^{1/2}V_j(V_j^\top X V_j)^{-1} V_j^\top X^{1/2}V_i\left(V_i^\top X V_i\right)^{-1}\right) \ge 1. $$ I'm stuck at this point. I believe that the problem can be further simplified to some well-known determinant inequality. However, at the moment, I don't know how to proceed.


Note 1. This question can be seen as a generalization of this problem. Indeed, for $m=1$, \eqref{1} reduces exactly to the case treated in that question, which has been proved to be true.

Note 2. Numerical simulations suggest that \eqref{1} is very likely to be true.

Edit. I edited the inequality by replacing the factor $1/N$ in the first logarithm by $1/(mN)$. This is a somewhat "stronger" version which I believe is the "right" generalization of the aforementioned problem.

$\endgroup$
  • $\begingroup$ Did you try a simple induction on $m$ to reuse Fedor's proof? $\endgroup$ – Suvrit Jan 29 '17 at 20:07
  • $\begingroup$ @Suvrit: Induction doesn't seem to me a viable way to solve the problem. In particular, in the inductive step $m-1\to m$ I don’t see how to decouple the inequality in order to apply Fedor’s argument for $m=1$ (the presence of the matrix logarithm and inverse make this task hard). However it's very possible that I’m mistaken. $\endgroup$ – Ludwig Jan 29 '17 at 20:40
  • $\begingroup$ Because this is essentially an inequality about determinants $\mathrm{tr}(\log Z) = \log\det(Z)$, I am still hopeful that it will work out. $\endgroup$ – Suvrit Jan 29 '17 at 20:55
  • $\begingroup$ why the 'exp' in there?? $\endgroup$ – Suvrit Jan 30 '17 at 16:45
  • 3
    $\begingroup$ The question looks really nice. I wish I had some more time to think about it. One brute-force approach may be to minimize the $\log\det$ part wrt $X>0$ under the constraint $\text{tr}(X)=1$, to see if the optimality conditions lead to any simplification. Alternatively, To use Schur complements to be able to trigger the induction. Not sure if these ideas are helpful at all though! $\endgroup$ – Suvrit Feb 1 '17 at 16:57
3
$\begingroup$

Fedor's proof can be generalized :

Let $S = X^{1/2}$, $U_i = V_i S^{1/2}$ and $W_i = U_i (U_i^T S U_i)^{-1/2}$ . Then $W_i^T S W_i = I_m$ where $I_m$ is the $m\times m$ identity .

Since $log(x) \ge 1 - 1/x$ it is enough to show that $$tr \sum_{i=1}^N \mu_i \le 1$$ where $$\mu_i = (\sum_{j=1}^N W_i^T W_j W_j^T W_i)^{-1}$$ .

Then $$tr \sum_{i=1}^N \mu_i = tr \sum_{i=1}^N \mu_i^2 \mu_i^{-1}$$ $$= tr [\sum_{i=1}^N \mu_i^2 \sum_{j=1}^N W_i^T W_j W_j^T W_i]$$ $$\ge tr \sum_{i=1}^N \sum_{j=1}^N W_i \mu_i W_i^T W_j \mu_j W_j^T$$ $$= tr [(\sum_{i=1}^N W_i \mu_i W_i^T)^2]$$ $$\ge [tr (S \sum_{i=1}^N W_i \mu_i W_i^T)]^2$$ $$= (tr \sum_{i=1}^N \mu_i)^2$$ ,

where I have used that $$tr (\mu_i^2 W_i^T W_j W_j^T W_i) + tr (\mu_j^2 W_j^T W_i W_i^T W_j) \ge 2 tr (W_i \mu_i W_i^T W_j \mu_j W_j^T)$$ .

This follows from $$0 \le tr[(W_i^T W_j \mu_j - \mu_i W_i^T W_j) (\mu_j W_j^T W_i - W_j^T W_i \mu_i)]$$ .

$\endgroup$
  • $\begingroup$ Thanks for the answer! Could you please elaborate a little more on the equivalent inequality $\mathrm{tr}\sum_{i=1}^N\mu_i\leq 1$? More precisely, how did you use the inequality $\log x \geq 1-1/x$ in order to derive the latter expression? $\endgroup$ – Ludwig Feb 12 '17 at 11:05
  • $\begingroup$ @Jacquard : I apply the inequality to (2) after moving the factor $(V_i^T X V_i)^{-1/2}$ to the left in order to make the operand symmetric. $\endgroup$ – jjcale Feb 12 '17 at 12:54
  • $\begingroup$ I'm still missing something: How does the inequality $\log x \ge 1-1/x$ apply to the case of the trace of the matrix logarithm? $\endgroup$ – Ludwig Feb 12 '17 at 13:08
  • $\begingroup$ For positive definite matrix A it follows $log A \ge I - A^{-1}$ . $\endgroup$ – jjcale Feb 12 '17 at 13:36
  • 1
    $\begingroup$ I added the trace. From $x \ge x^2$ it follows $x \le 1$ . In our case $x = tr \sum_{i=1}^N\mu_i$ . $\endgroup$ – jjcale Feb 12 '17 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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