Conditional graph entropy as an alternating minimization problem
share
The systematic study of alternating minimization problems was initiated by Csiszár and Tusnády. The area gained renewed interest recently due to its applications in machine learning. We will use this theory in the context of conditional graph entropy. The unconditioned version of this entropy notion was introduced by Körner. The conditional version is important due to a result of Orlitsky and Roche showing that the minimal rate for a natural functional compression problem (with side information at the receiver) is given by conditional graph entropy. In this paper we show that conditional graph entropy can be formulated as an alternating minimization problem. More specifically, we present a function of two (vector-valued) variables such that, fixing any of the two variables, the optimal choice for the other variable can be expressed explicitly. Then minimizing in the fixed variable gives us the global minimum. Depending on which variable we start with, we get two different minimization problems with the same optimum. In one case we get back the original formula for conditional graph entropy. In the other we obtain a new formula. This new formula shows that conditional graph entropy is part of a more general framework: the solution of an optimization problem over a so-called convex corner. In the unconditioned case (i.e., graph entropy) this was known due to Csiszár, Körner, Lovász, 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. Furthermore, if we alternate in optimally choosing one variable given the other, then we get a decreasing sequence of function values converging to the minimum, which allows one to numerically compute (conditional) graph entropy.
READ FULL TEXT