Proving Information Inequalities by Gaussian Elimination
Laigang Guo, Raymond W. Yeung, Xiao-Shan Gao · IEEE Transactions on Information Theory · 2025
The proof of information inequalities and identities under linear constraints on the information measures is an important problem in information theory. For this purpose, ITIP and other variant algorithms have been developed and implemented, which are all based on solving a linear program (LP). Building on our recent work (Guo et al., 2023), we developed in this paper an enhanced approach for solving this problem. Experimental results show that our new approach improves the time complexity by over 500 times compared with Guo et al. (2023) for the problem studied by Tian (2014).