论文标题
条件图熵作为交替的最小化问题
Conditional graph entropy as an alternating minimization problem
论文作者
论文摘要
已知有条件的图形熵是与接收器的侧面信息的天然功能压缩问题的最小速率。在本文中，我们表明它可以作为交替的最小化问题进行配方，这导致了用于数值计算（条件）图熵的简单迭代算法。这也导致了一个新公式，该公式表明条件图熵是一个更通用的框架的一部分：在凸角上优化问题的解决方案。在图形熵的特殊情况下（即无条件的版本），这是由于Csiszár，Körner，Lovász，Marton和Simonyi而闻名的。在这种情况下，凸角的角色是由所谓的顶点填料polytope扮演的。在条件版本中，它是一个更复杂的凸体，但最小化的功能是相同的。此外，我们描述了一个双重问题，该问题导致最佳检查和迭代算法绑定的错误。
Conditional graph entropy is known to be the minimal rate for a natural functional compression problem with side information at the receiver. In this paper we show that it can be formulated as an alternating minimization problem, which gives rise to a simple iterative algorithm for numerically computing (conditional) graph entropy. 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á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, we describe a dual problem that leads to an optimality check and an error bound for the iterative algorithm.
