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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Did you try a simple induction on $m$ to reuse Fedor's proof? $\endgroup$
    – Suvrit
    Jan 29, 2017 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, 2017 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, 2017 at 20:55
  • $\begingroup$ why the 'exp' in there?? $\endgroup$
    – Suvrit
    Jan 30, 2017 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, 2017 at 16:57

1 Answer 1

Reset to default
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)]$$ .

Improve this answer
$\endgroup$
6
  • $\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, 2017 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, 2017 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, 2017 at 13:08
  • $\begingroup$ For positive definite matrix A it follows $log A \ge I - A^{-1}$ . $\endgroup$
    – jjcale
    Feb 12, 2017 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, 2017 at 16:57

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.