Symmetry reduction of information inequalities
Symmetry reduction of information inequalities
复制标题
信息不平等的对称性减少
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Tian
中科院分区：
文献类型：
--
作者：
Kai Zhang;C. Tian
信息不平等可以用来限制通信系统和数据存储系统的基本限制。信息不等式，特别是香农型不等式和问题特定约束通常是线性等式或联合熵的不等式，因此基本极限的外边界可以视为线性规划（LP）并求解。然而，对于许多实际工程问题，所得的LP是非常大的。以前的研究表明，这些问题中的对称性可以用来减少LP的规模，但是减少的确切数量还没有得到很好的理解。在这项工作中，我们提供了一种通用的方法来确定这种减少。特别研究了三个问题：极值两两循环熵不等式、代码再生问题和缓存问题。将对称看成是特定集合上的诱导置换群，可以应用Pólya计数定理，但需要确定诱导置换的循环指数。
Information inequalities can be used to bound the fundamental limits of communication systems and data storage systems. Information inequalities, particularly Shannon-type inequalities, and the problem-specific constraints are usually either linear equalities or inequalities of joint entropies, and thus outer bounding the fundamental limit can be viewed and solved as a linear program (LP). However, for many practical engineering problems, the resultant LP is very large. It was shown previously that symmetry in these problems can be used to reduce the scale of the LP, however the precise amount of reduction was not well understood. In this work, we provide a generic method to pinpoint this reduction. In particular, three problems are studied: extremal pairwise cyclic entropy inequalities, the regenerating code problem, and the caching problem. By viewing the symmetry as an induced permutation group on certain set, Pólya counting theorem can be applied, which however requires identifying the cycle index of the induced permutation.