Conditional graph entropy as an alternating minimization problem

In this paper we show that conditional graph entropy can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. The systematic study of alternating minimization problems was initiated by Csisz\'ar and Tusn\'ady. We apply this theory to conditional graph entropy, which was shown to be the minimal rate for a natural functional compression problem with side information at the receiver. This also leads to a new formula which shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a convex corner. In the special case of graph entropy (i.e., unconditioned version) this was known due to Csisz\'ar, K\"orner, Lov\'asz, Marton, and Simonyi. In that case the role of the convex corner was played by the so-called vertex packing polytope. In the conditional version it is a more intricate convex body but the function to minimize is the same.