论文标题
一种新的方法来计算信息理论外界及其在再生代码中的应用
A New Approach to Compute Information Theoretic Outer Bounds and Its Application to Regenerating Codes
论文作者
论文摘要
信息系统的基本限制的研究是信息理论的中心主题。传统的分析方法和最近提出的计算方法都有很大的局限性，其中前者主要是由于其对人类创造力的依赖，而后者是由于其指数记忆和计算复杂性。在这项工作中，我们提出了一种新的计算方法，以较低的内存和计算要求来解决该问题，这些方法自然可以利用某些直觉，但也可以维持现有计算方法的强大计算优势。首先提出了基础优化问题的重新重新制定，该问题将大型线性程序转换为最大化问题。这导致了一种迭代解决程序，该程序使用LP双重二元进行了迭代之间的学习证据。重新制定问题的关键是选择良好的信息不平等，可以与之形成放松的LP。一个特别有力的直觉是一种潜在的最佳代码构建，我们提供了一种直接在新算法中使用它的方法。作为一个应用程序，我们为$（6,5,5）$再生代码问题提供了更严格的外部限制，该框架的折衷方案至少涉及30个随机变量，并且无法使用先前已知的计算方法进行计算。
The study of the fundamental limits of information systems is a central theme in information theory. Both the traditional analytical approach and the recently proposed computational approach have significant limitations, where the former is mainly due to its reliance on human ingenuity, and the latter due to its exponential memory and computational complexity. In this work, we propose a new computational approach to tackle the problem with much lower memory and computational requirements, which can naturally utilize certain intuitions, but also can maintain the strong computational advantage of the existing computational approach. A reformulation of the underlying optimization problem is first proposed, which converts the large linear program to a maximin problem. This leads to an iterative solving procedure, which uses the LP dual to carry over learned evidence between iterations. The key in the reformulated problem is the selection of good information inequalities, with which a relaxed LP can be formed. A particularly powerful intuition is a potentially optimal code construction, and we provide a method that directly utilizes it in the new algorithm. As an application, we derive a tighter outer bound for the storage-repair tradeoff for the $(6,5,5)$ regenerating code problem, which involves at least 30 random variables and is impossible to compute with the previously known computational approach.
