Entropy Vectors, Convex Optimization and Network Information Theory

本文从熵向量和凸优化的角度研究网络信息理论。目前，人们对有线和无线网络上的信息传输问题非常感兴趣。信息论很有可能对未来网络的设计和维护方式产生影响，这既是因为有线网络对于网络编码的应用已经成熟，也是因为使用传统的网络工具无法令人满意地处理无线网络。面临的挑战是，大多数网络信息理论的问题是出了名的困难，所以必须克服的数学障碍往往是相当高的，在这项研究中采用的方法是通过规范化的熵向量的空间的定义，这略有不同，在文献中的熵是规范化的字母表大小的对数。这个定义对于确定网络的容量区域是更自然的，并且使得所得到的空间的闭合是凸的（和紧凑的），即使在网络内部的信道所施加的约束下也是如此。对于非循环无记忆网络，任意源和目的地集合的容量区域可以通过在信道约束的归一化熵向量和一些线性约束的集合上最大化线性函数来找到。虽然不一定使问题更简单，但这种方法肯定绕过了“无限字母特征”，以及早期公式的非凸性，并暴露了问题的核心，即确定归一化熵向量的空间。因此，大部分的研究集中在使用群论，格论，非香农不等式等工具来构造这个空间的可计算的内外界。

This research studies network information theory based on the viewpoint of entropic vectors and convex optimization. There is currently great interest in the problem of information transmission over wired and wireless networks. Information theory is well poised to have an impact on the manner in which future networks are designed and maintained, both because wired networks are ripe for the application of network coding and also because wireless networks cannot be satisfactorily dealt with using conventional networking tools. The challenge is that most network information theory problems are notoriously difficult and so the mathematical barriers that must be overcome are often quite high.The approach adopted in this research is through the definition of the space of normalized entropic vectors, which differs slightly from that in the literature in that entropy is normalized by the logarithm of the alphabet size. This definition is more natural for determining the capacity region of networks and renders the closure of the resulting space convex (and compact), even under constraints imposed by channels internal to the network. For acyclic memoryless networks, the capacity region for an arbitrary set of sources and destinations can be found by maximizing a linear function over the set of channel-constrained normalized entropic vectors and some linear constraints. While not necessarily making the problem simpler, this approach certainly circumvents the ``infinite-letter characterization'', as well as the nonconvexity of earlier formulations, and exposes the core of the problem as that of determining the space of normalized entropy vectors. Much of the research therefore focuses on constructing computable inner and outer bounds to this space using tools from group theory, lattice theory, non-Shannon inequalities, and others.