5
$\begingroup$

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$.

$\endgroup$
8
  • $\begingroup$ 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 ? $\endgroup$ Jul 26, 2010 at 12:26
  • $\begingroup$ You link did not work for me, but I found the document you mention here renyi.hu/~csiszar/Publications/… $\endgroup$ Jul 26, 2010 at 12:30
  • $\begingroup$ 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. $\endgroup$
    – Ashok
    Jul 30, 2010 at 14:56
  • $\begingroup$ 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 ? $\endgroup$ Aug 2, 2010 at 11:50
  • $\begingroup$ 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. $\endgroup$
    – Ashok
    Aug 5, 2010 at 11:07

2 Answers 2

3
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much for the reference. Ours is not a Bregman divergence. Moreover, ours is only quasi-convex. $\endgroup$
    – Ashok
    Sep 15, 2010 at 10:19
2
$\begingroup$

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 ?

$\endgroup$

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