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

I have been working on a problem(alternate minimization) where I want to establish an inequality in which I am stuck.

An $\alpha$- parameterized version of the divergence(Kullback-Leibler) takes the following form:

$$I_{\alpha}(P,Q)=\frac{1}{\rho}\log\left[\frac{h(Q)^{1-\alpha}}{h(P)}\sum_{a\in A}P(a)Q(a)^{\alpha-1}\right] $$ where $\alpha=\frac{1}{1+\rho}, \rho>0$ and I let $h(P)=\left(\sum P(a)^{\alpha}\right)^{\frac{1}{\alpha}}$, $A$ is a finite set and $P, Q$ are distributions on $A$.

By Holder's inequality I have shown that $\sum_{a\in A}P(a)Q(a)^{\alpha-1}\ge h(Q)^{\alpha-1}h(P)$. So $I_{\alpha}(P,Q)\ge 0$ and is $0$ iff $P=Q$.

The problem is the following:

Let $P$ be a distribution and $E$ be a closed and convex set. Let $I_{\alpha}(P,Q^*)=\min_{Q\in E}I_{\alpha}(P,Q)$.

I want to establish $I_{\alpha}(P',P)+I_{\alpha}(P',Q')\ge I_{\alpha}(P',Q^*)$ for any $P'$ and any $Q'\in E$.

The equivalent form of the above ineq. is $$\frac{h(P)^{1-\alpha}}{h(P')}\sum_{a\in A}P'(a)P(a)^{\alpha-1}\cdot \frac{h(Q')^{1-\alpha}}{h(P')}\sum_{a\in A}P'(a)Q'(a)^{\alpha-1}\ge \frac{h(Q^*)^{1-\alpha}}{h(P')}\sum_{a\in A}P'(a)Q^*(a)^{\alpha-1}$$

Imre Csiszar has proved the same inequality for the Kullback Leibler divergence where he employs a derivative argument. When I do the similar thing I get the following:

Let $Q_t=(1-t)Q^*+tQ'\in E, 0\le t\le 1$. Then $$0\le \frac{1}{t}\left[I_{\alpha}(P,Q_t)-I_{\alpha}(P,Q^*)\right]=\left[\frac{d}{dt}I_{\alpha}(P,Q_t)\right]_{t=\tilde{t}}, \quad 0<\tilde{t}\le t$$

As $t\to 0$, I get the following: $$\frac{1}{h(Q^*)^{\alpha}}\sum_{a\in A}P(a)Q^*(a)^{\alpha-1}. \sum_{a\in A}Q'(a)Q^*(a)^{\alpha-1}\ge \sum_{a\in A}P(a)Q'(a)Q^*(a)^{\alpha-2}$$ I don't know how to use this to prove the desired inequality. Can anyone help? You may refer Csiszar's book on Information theory and statistics- a tutorial page no 445-446, available here http://www.nowpublishers.com/product.aspx?product=CIT&doi=0100000004

Update 14, September.

If I denote $\frac{P'(a)}{h(P')}$'s by $a_i$, $\frac{P(a)}{h(P)}$'s by $b_i$, $\frac{Q'(a)}{h(Q')}$'s by $c_i$, and $\frac{Q^{\star}(a)}{h(Q^{\star})}$'s by $d_i$, then a, b, c, d are vectors whose $\alpha$th norm is $1$. Problem would be solved if we show the following. $$\min_{\|a\|_{\alpha}=1}\sum_{i=1}^n a_i b_i^{\alpha-1}.\sum_{i=1}^n a_i c_i^{\alpha-1}-\sum_{i=1}^n a_i d_i^{\alpha-1}\ge \sum_{i=1}^n b_i d_i^{\alpha-1}. \sum_{i=1}^n c_i d_i^{\alpha-1}-\sum_{i=1}^n b_i c_i d_i^{\alpha-2}$$ as the right hand side is $\ge 0$.

share|improve this question

closed as no longer relevant by Scott Morrison Nov 15 '10 at 23:18

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

    
You define the - parameterized version of the divergence(Kullback-Leibler), can you tell us why you call it like that (is the kullback leibler divergence obtained when p goes to infinity) ? You seem to be sure that your inquality is true, you may have a reference or is it intuition ? –  robin girard Jul 26 '10 at 12:26
    
You link did not work for me, but I found the document you mention here renyi.hu/~csiszar/Publications/… –  robin girard Jul 26 '10 at 12:30
    
I call it a parameterized version because it is kullback leibler as $\alpha \to 1$. We claim that this is the natural parameterized extension of KL as it also has the geometric analogous results which KL does. –  Ashok Jul 30 '10 at 14:56
    
Are you aware of the parametrisation in the old paper of Amari: projecteuclid.org/… related to chernoff distance? It is not the same and he calls it "$\alpha$-distance". (see Annex A2 in the paper). The extention in Amari has some interest with respect to some alpha-connection (Riemannian geometry) what about yours ? –  robin girard Aug 2 '10 at 11:50
    
Thank you for pointing out the Amari's paper. I don't know Riemannian geometry. But the $I_{\alpha}$ we have behaves like 'squared' euclidean distance and has the Pythagorean property. KL divergence also has the Pythagorean property which is crucial in several applications viz. Expectation Maximization algorithm(alternate divergence minimization) etc. The $\alpha$-divergence we have is not a cooked up one; it arose naturally as a redundancy measure when we do mismatched guessing(or mismatched compression). This is why we are trying to establish all the results for $I_{\alpha}$ analogous to KL. –  Ashok Aug 5 '10 at 11:07
show 3 more comments

2 Answers 2

If you can show that your $\alpha$-divergence above is a Bregman divergence that is convex in both its arguments, then the following paper points out a result that implies the abovementioned four-points property that you are trying to prove.

Link: http://math.haifa.ac.il/yair/AORfulltext.pdf

share|improve this answer
1  
Thank you very much for the reference. Ours is not a Bregman divergence. Moreover, ours is only quasi-convex. –  Ashok Sep 15 '10 at 10:19
add comment

If the inequality is true, you will find a proof with your technic by changing the transport you use: $Q_t$ . This transport is "adapted" to the geometry induced by KL but not by your $\alpha$-KL. I'll try to find the time to find the good transformation from my side and add it to the answer, or maibe you'll find it yourself :)


Remarks

You define the $\alpha$- parameterized version of the divergence(Kullback-Leibler), can you tell us why you call it like that (is the kullback leibler divergence obtained when $p$ goes to infinity) ? You seem to be sure that your inquality is true, you may have a reference or is it intuition ?

These optimal transformations things makes me remember about Theorem 5.24 and Example 5.27 of http://www.umpa.ens-lyon.fr/~cvillani/Cedrif/B07D.StFlour.pdf maybe this very general theorem can also help you ?

share|improve this answer
add comment

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