Computational Techniques for Investigating Information Theoretic Limits of Information Systems

Chao Tian, Department of Electrical and Computer Engineering, Texas A&M University,
James S. Plank, EECS Department, University of Tennessee,
Brent Hurst, EECS Department, University of Tennessee,
Ruida Zhou, Department of Electrical and Computer Engineering Texas A&M University.

Information, 2021, 12(2), 82.

This article is open-access: https://www.mdpi.com/2078-2489/12/2/82.

Abstract

Computer-aided methods, based on the entropic linear program framework, have been shown to be effective in assisting the study of information theoretic fundamental limits of information systems. One key element that significantly impacts their computation efficiency and applicability is the reduction of variables, based on problem-specific symmetry and dependence relations. In this work, we propose using the disjoint-set data structure to algorithmically identify the reduction mapping, instead of relying on exhaustive enumeration in the equivalence classification. Based on this reduced linear program, we consider four techniques to investigate the fundamental limits of information systems: (1) computing an outer bound for a given linear combination of information measures and providing the values of information measures at the optimal solution; (2) efficiently computing a polytope tradeoff outer bound between two information quantities; (3) producing a proof (as a weighted sum of known information inequalities) for a computed outer bound; and (4) providing the range for information quantities between which the optimal value does not change, i.e., sensitivity analysis. A toolbox, with an efficient JSON format input frontend, and either Gurobi or Cplex as the linear program solving engine, is implemented and open-sourced.

Citation Information

Plain Text:

author          C. Tian and J. S. Plank and B. Hurst and R. Zhou
title           Computational Techniques for Investigating Information Theoretic 
                Limits of Information Systems
journal         Information
volume          12
number          2
year            2021
url             https://www.mdpi.com/2078-2489/12/2/82
issn            2078-2489
doi             10.3390/info12020082
article-number  82

Bibtex:

@ARTICLE{tph:21:cti,
  author = "C. Tian and J. S. Plank and B. Hurst and R. Zhou",
  title = "Computational Techniques for Investigating Information Theoretic 
                Limits of Information Systems",
  journal = "Information",
  volume = "12",
  number = "2",
  year = "2021",
  url = "https://www.mdpi.com/2078-2489/12/2/82",
  issn = "2078-2489",
  doi = "10.3390/info12020082",
  article-number = "82"
}