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

Let $K$ and $K^\prime$ positive definite $n \times n$ matrices, such that for all vectors $f \ge 0$ with nonnegative coordinates we have

$$\sum_{i,j} K_{ij} f_i f_j \le \sum_{ij} K^\prime_{ij} f_i f_j$$

Can someone prove the following inequality?

$$ \sum_{i,j} \exp K_{ij} \le \sum_{i,j} \exp K^\prime_{ij} $$

The reason why I believe it is true is that I have a proof using Slepian-Kahane-type comparison for Wick exponentials of Gaussian random vectors with covariance $K$ and $K^\prime$, which might look like a perverse way of doing something as simple-looking as this. Ideally, I'd like to see a more straightforward proof, or maybe some general suggestions on how to use that weird positivity condition on $K^\prime - K$.

Upd: The "weird positivity condition" is nothing but dual to something known by the name "complete positivity".

share|improve this question
    
This one essentially follows because for positive definite matrices $K, K'$ such that $K \preceq K'$, it follows that $K \circ K \preceq K' \circ K'$, where $\circ$ denotes the Schur (Hadamard) product. –  Suvrit Mar 23 at 18:57
    
@Suvrit: Actually, I don't see how to show even that unless the difference $K^\prime - K$ is positive definite. –  Alexander Shamov Mar 23 at 19:21
    
Ah, your first inequality has an extra nonnegativity hypothesis, which (despite its being bold), I missed seeing... –  Suvrit Mar 23 at 19:33
    
@Suvrit: That's the whole point. :) –  Alexander Shamov Mar 23 at 19:34
1  
The dual to the completely positive cone is called the "copositive cone", i.e. your assumption is that $K'-K$ be copositive. –  Noah Stein Mar 24 at 12:25

1 Answer 1

up vote 5 down vote accepted

Here is a simple proof (thanks to the OP for a proof that the Hadamard exponential is CP).

I'll write $K$ and $H \equiv K'$ to keep the notation simpler.

As $K \succeq 0$, it follows that its Schur exponent $[e^{k_{ij}}]$ is also psd. Thus, in particular, we can write the following factorization: \begin{equation*} [e^{k_{ij}}] = \sum\nolimits_l u_l u_l^T. \end{equation*}

Theorem. The Schur-Hadamard exponential $[e^{k_{ij}}]$ is completely positive, i.e., in the above factorization we can select the vectors $u_1,\ldots,u_n$ to be elementwise nonnegative.

In addition to the OP's elegant argument (see comments below), another proof to this theorem may also be found as Theorem 2.30 (pp 131) in Completely Positive Matrices, by Berman and ‎Shaked-Monderer.

Then, consider \begin{equation*} \sum\nolimits_{ij} e^{k_{ij}}(h_{ij}-k_{ij}) = \mbox{tr}[(H-K)\sum\nolimits_l u_lu_l^T] = \sum\nolimits_l u_l^T (H-K)u_l \ge 0, \end{equation*} where the final inequality follows from our hypothesis since $u_l \ge 0$.

Since $\exp(x)$ is a convex function, we have \begin{equation*} e^h \ge e^k + e^k(h-k),\qquad\forall h, k. \end{equation*} Thus, it follows that \begin{equation*} \sum_{ij} e^{h_{ij}} \ge \sum_{ij} e^{k_{ij}} + \sum_{ij} e^{k_{ij}}(h_{ij}-k_{ij}). \end{equation*} But the above argumentation showed that the last term on the rhs is nonnegative.$\qquad\blacksquare$

share|improve this answer
    
Actually, it is true that $\exp K$ is completely positive for every positive definite $K$. And guess what, this has a probabilistic reason: $\exp K_{ij} = \mathsf{E} \exp[X_i - \frac{1}{2} K_{ii}] \exp[X_j - \frac{1}{2} K_{jj}]$, where $X$ is the Gaussian with covariance $K$. –  Alexander Shamov Mar 23 at 20:39
    
So if exp is CP, we are done! –  Suvrit Mar 23 at 20:42
    
Very nice, thanks! –  Alexander Shamov Mar 23 at 20:49
    
I find your proof of CP of exp much nicer than using a bruteforce argument based on decomposing $K=\sum_l v_lv_l^T$, etc. –  Suvrit Mar 23 at 20:54
    
Actually, my original motivation was to avoid Gaussian tricks - and instead we arrived at special properties of exponential... –  Alexander Shamov Mar 23 at 21:00

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.