Proving and Disproving Information Inequalities : Theory and Scalable Algorithms

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

5 Scopus Citations
View graph of relations

Author(s)

  • Siu-Wai Ho
  • Lin Ling
  • Chee Wei Tan
  • Raymond W. Yeung

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number9044774
Pages (from-to)5522-5536
Journal / PublicationIEEE Transactions on Information Theory
Volume66
Issue number9
Online published23 Mar 2020
Publication statusPublished - Sep 2020

Abstract

Proving or disproving an information inequality is a crucial step in establishing the converse results in coding theorems. However, an information inequality involving more than a few random variables is difficult to be proved or disproved manually. In 1997, Yeung developed a framework that uses linear programming for verifying linear information inequalities. Under the framework, this paper considers a few other problems that can be solved by using Lagrange duality and convex approximation. We will demonstrate how linear programming can be used to find an analytic proof of an information inequality or an analytic counterexample to disprove it if the inequality is not true in general. The way to automatically find a shortest proof or a smallest counterexample is explored. When a given information inequality cannot be proved, the sufficient conditions for a counterexample to disprove the information inequality are found by linear programming. Lastly, we propose a scalable algorithmic framework based on the alternating direction method of multipliers to accelerate solving a multitude of user-specific problems whose overall computational cost can be amortized with the number of users, and present its publicly-available software implementation for large-scale problems.

Research Area(s)

  • automated reasoning by convex optimization, Entropy, information inequality, mutual information

Citation Format(s)

Proving and Disproving Information Inequalities : Theory and Scalable Algorithms. / Ho, Siu-Wai; Ling, Lin; Tan, Chee Wei; Yeung, Raymond W.

In: IEEE Transactions on Information Theory, Vol. 66, No. 9, 9044774, 09.2020, p. 5522-5536.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review