Let $E$ be a closed and convex set of distributions on a finite set $A$. Let $P',Q'\notin E$ and let $P^{\star},Q^{\star}$ be their respective estimates in $E$ with respect to the KL-divergence, i.e., $D(P'\|P^{\star})=\min_{P\in E}D(P'\|P)$ and similarly for $Q^{\star}$. I am wondering whether $D(P'\|Q')\ge D(P^{\star}\|Q^{\star})$.
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
4
3
|
||||||||||||||||||||
|
|
2
|
The inequality $D(P'|Q') \ge D(P^\star| Q^\star)$ does not need to hold. Here is an example. Let $A$ be the set $\{1,2,3,...,n\}$. Let $E$ be the set of measures $P$ on $A$ such that $P(\{1\}) = 0$. Projecting a measure $P$ on $E$ using $D$ is equivalent to conditioning $P$ on $ A- \{1\}$. Choose $P'$ and $Q'$ such that they both put equal and nonzero mass on $\{1\}$. By direct computation one sees: $D(P^\star| Q^\star) = \frac{1}{1-P'(\{1\})} D(P'|Q') > D(P' | Q')$. The details of the above computation are as follows. For ease of notation set $n=3$. Let $E$ be the set of measures $P$ with $P(\{1\}) =\epsilon$; to obtain the example above, one sets $\epsilon = 0$. Let us parametrize the measures on $\{1,2,3\}$ as follows: $P(\{1\}) = p_1$, $P(\{2\}) =p_2$ and $P(\{3\}) = 1-p_1 -p_2$. Our problem is: $$ \inf_{ Q \in E}\left[ p_1 \log \frac{p_1}{q_1} + p_2 \log \frac{p_2}{q_2} + (1-p_1 -p_2) \log\frac{ 1- p_1 - p_2}{ 1- q_1 - q_2 } \right]. $$ Let $F$ denote the expression after the $\inf$. $F$ is strictly convex in $Q$ and therefore will have a unique optimizer. In the above coordinates, the normal to $E$ is the vector $(1,0)$. Then $$ \frac{\partial F} {\partial q_1} = -\frac{p_1}{q_1} + \frac{1-p_1-p_2}{1-q_1-q_2} = \lambda $$ and $$ \frac{\partial F} {\partial q_2} = -\frac{p_2}{q_2} + \frac{1-p_1-p_2}{1-q_1-q_2} = 0. $$ We have the constraint that $Q\in E$, i.e., $q_1 =\epsilon$. From the last two equalities one infers: $$ q_2 = \frac{(1-\epsilon) p_2}{ 1-p_1}. $$ Going back to the coordinates $(p_1,p_2,p_3)$ to denote a measure on $\{1,2,3\}$, projecting a measure on $E$ using $D$ corresponds to the following map: $$ (p_1,p_2,p_3) \rightarrow \left(\epsilon, (1-\epsilon)\frac{p_2}{p_2+p_3}, (1-\epsilon)\frac{p_3}{p_2 + p_3}\right). $$ For $\epsilon =0$, this is the same as conditioning $P$ on $\{2,3\}$. One obtains the expression for the relative entropy given above by directly computing it using this formula for the projections. |
|||||||||||||||||
|
