Entropy Vectors, Convex Optimization and Network Information Theory

熵向量、凸优化和网络信息论

• 批准号: 0729203
• 负责人: Babak Hassibi
• 金额: $ 30万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729203&HistoricalAwards=false
• 关键词: Entropy; Vectors; Convex; Optimization; Network

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.

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