TY - JOUR
T1 - Proving and Disproving Information Inequalities
T2 - Theory and Scalable Algorithms
AU - Ho, Siu-Wai
AU - Ling, Lin
AU - Tan, Chee Wei
AU - Yeung, Raymond W.
PY - 2020/9
Y1 - 2020/9
N2 - 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.
AB - 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.
KW - automated reasoning by convex optimization
KW - Entropy
KW - information inequality
KW - mutual information
KW - automated reasoning by convex optimization
KW - Entropy
KW - information inequality
KW - mutual information
KW - automated reasoning by convex optimization
KW - Entropy
KW - information inequality
KW - mutual information
UR - http://www.scopus.com/inward/record.url?scp=85090471966&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85090471966&origin=recordpage
U2 - 10.1109/TIT.2020.2982642
DO - 10.1109/TIT.2020.2982642
M3 - 21_Publication in refereed journal
VL - 66
SP - 5522
EP - 5536
JO - IRE Transactions on Information Theory
JF - IRE Transactions on Information Theory
SN - 0018-9448
IS - 9
M1 - 9044774
ER -