7
$\begingroup$

I am going through the book Computational Optimal Transport by Peyré and Cuturi. In it (see Formula (4.1), P. 65/209) I came across the definition of the discrete entropy, which is not what I expected: $$ H(P) = - \sum_{i,j}P_{i,j}(\log(P_{i,j})-1), $$ with $P \in [0,1]^{n,m}$ being a coupling matrix, i.e. describing the transformation of discrete propability distributions. What confuses me is the $-1$ in the sum and I would like to know, why it is included. Since $\sum_{i,j} P_{i,j}=1$ it is shifting the result by $-1$. Still it confuses me.

$\endgroup$
2
  • $\begingroup$ Did you confirm that this is indeed an error in the book? I'm having the same doubt as you. $\endgroup$ Nov 15, 2020 at 12:48
  • $\begingroup$ It adds $+1$ to $H$, actually. $\endgroup$
    – J.G.
    Nov 15, 2020 at 14:22

3 Answers 3

4
+50
$\begingroup$

The obvious reason $-\sum_{i,\,j}P_{i,\,j}\ln P_{i,\,j}$ is a more common definition is that it's extensive, but we often don't care about that, so much as about relative entropies. In that case, one may as well add a constant $c$ to taste, giving $c-\sum_{i,\,j}P_{i,\,j}\ln P_{i,\,j}=-\sum_{i,\,j}P_{i,\,j}(\ln P_{i,\,j}-c)$. The choice $c=1$ has the unique attraction that the whole expression is just $-\sum_{i,\,j}\int_0^{P_{i,\,j}}\ln pdp$.

$\endgroup$
2
  • $\begingroup$ Does this has some computational advantage? I mean, things are already in a discrete setting, so do you see how such integral form can be beneficial? $\endgroup$ Nov 15, 2020 at 14:59
  • $\begingroup$ @DaviBarreira It's a continuous function equal to a discrete sum, but no, the choice of $c$ isn't computationally important. But this integral representation provides an alternative motivation for Shannon entropy. $\endgroup$
    – J.G.
    Nov 15, 2020 at 15:12
3
$\begingroup$

Adding to the answer by @J.G, one reason for adding the -1 term could be to have cleaner expressions for the partial derivative of the dual formulation with respect to the transport plan matrix $\mathbf{P}$.

If there was no $-1$ term, then the partial derivative (page 63 of Computational Transport by Peyré and Cuturi) would have an extra $\epsilon$ term. Having the $-1$ in the coupling entropy eliminates this $\epsilon$ term, leading to a simpler expression for the Sinkhorn iterations.

$\endgroup$
4
  • $\begingroup$ This does not provide an answer to the question. Once you have sufficient reputation you will be able to comment on any post; instead, provide answers that don't require clarification from the asker. - From Review $\endgroup$ Oct 11, 2021 at 17:27
  • $\begingroup$ @Suman Chakraborty. I disagree. This answer is actually far more valuable than the one of dirich1337 for instance. $\endgroup$
    – Tobsn
    Oct 11, 2021 at 17:44
  • $\begingroup$ I agree, the only thing I wanted to point out is that it is not an answer. Rather, it is a comment on another answer. $\endgroup$ Oct 11, 2021 at 18:04
  • $\begingroup$ I actually had the very same question as dba had in the original post. J.G's answer was helpful in reminding that adding a constant doesn't really change anything. Certainly doesn't change the original goal of adding entropy, that is to make the transport problem strongly convex (which isn't explicitly mentioned in the previous posts). I think the simplified expression is more relevant to the original problem than the unique attractive point P.G mentioned. Obviously, it's up to you guys where you want to place the answer, but I think others could benefit from this answer. $\endgroup$ Oct 11, 2021 at 18:46
1
$\begingroup$

I think it might just be a strange error... In Cuturi's Paper on Sinkhorn Distances entropy is defined in the usual way.

$\endgroup$
1
  • 1
    $\begingroup$ I don't think this answer is actually correct. If you look at the paper "Iterative Bregman Projections for Regularized Transportation Problems", by Benamou, Carlier, Cuturi, Nenna and Peyré, they also define entropy with "-1". $\endgroup$ Nov 15, 2020 at 14:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .