I am going through this paper, where the following claim is unproven (page 3, after the first equality):

Let $r,c \in \mathbb{R}_+^d$ be discrete probability histograms, and $P \in \mathbb{R}_+^{d,d}$ a joint probability matrix that has $r,c$ as marginals. Then we have $$KL(P||rc^T) = H(r) + H(c)-H(P).$$

It is supposed to be easy, but I dont see how I can arrive at this result.


With $r,c$, being $d\times 1$ column vectors, their outer product results in the matrix $rc^T$. We want to compare this resulting $d\times d$ distribution with any $P$ that has $r,c$ as marginals. I let subscript $i,j$ indicate the position in the matrices, and by $[d] = \{1,2,\ldots, d-1, d\}$. Thus,

$$KL(P||rc^T) = \sum_{(i,j) \in [d]\times[d]} P_{i,j} \log \frac{P_{i,j}}{rc^T_{i,j}} = \sum_{(i,j) \in [d]\times[d]} P_{i,j} \log P_{i,j} - P_{i,j} \log rc^T_{i,j}. $$

Now for any $i$, when you sum over each $j \in [0,d]$, you marginalize out the dependence on $j$, and similarly for fixed $j$ and varying $i$. But we also know that $P_{i,j}$ has the correct marginals of $r$ and $c$. Thus for the second term, you get

\begin{align} \sum_{(i,j) \in [d]\times[d]} - P_{i,j} \log rc^T_{i,j} &= \sum_{(i,j) \in [d]\times[d]} - P_{i,j} \log r_i - P_{i,j} \log c_j \\&= -\sum_i \log r_i \sum_{j} P_{i,j} - \sum_j \log c_j \sum_{i} P_{i,j} \\&= -\sum_{i} r_i \log r_i - \sum_{j} c_j \log c_j, \end{align} and by the definition of entropy $H(p) = -\sum_{i} p_{i} \log p_{i}$, we get the result.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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