Computational Techniques for Investigating Information Theoretic Limits of Information Systems
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 reductio...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-02-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/12/2/82 |
| _version_ | 1797396374609723392 |
|---|---|
| author | Chao Tian James S. Plank Brent Hurst Ruida Zhou |
| author_facet | Chao Tian James S. Plank Brent Hurst Ruida Zhou |
| author_sort | Chao Tian |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-09T00:50:21Z |
| format | Article |
| id | doaj.art-364368e4711d4ff6babfa98bd39a0e2d |
| institution | Directory Open Access Journal |
| issn | 2078-2489 |
| language | English |
| last_indexed | 2024-03-09T00:50:21Z |
| publishDate | 2021-02-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj.art-364368e4711d4ff6babfa98bd39a0e2d2023-12-11T17:14:27ZengMDPI AGInformation2078-24892021-02-011228210.3390/info12020082Computational Techniques for Investigating Information Theoretic Limits of Information SystemsChao Tian0James S. Plank1Brent Hurst2Ruida Zhou3Department of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USADepartment of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996, USADepartment of Electrical Engineering and Computer Science, University of Tennessee, Knoxville, TN 37996, USADepartment of Electrical and Computer Engineering, Texas A&M University, College Station, TX 77843, USAComputer-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.https://www.mdpi.com/2078-2489/12/2/82capacityconverse boundscomputational methods |
| spellingShingle | Chao Tian James S. Plank Brent Hurst Ruida Zhou Computational Techniques for Investigating Information Theoretic Limits of Information Systems Information capacity converse bounds computational methods |
| title | Computational Techniques for Investigating Information Theoretic Limits of Information Systems |
| title_full | Computational Techniques for Investigating Information Theoretic Limits of Information Systems |
| title_fullStr | Computational Techniques for Investigating Information Theoretic Limits of Information Systems |
| title_full_unstemmed | Computational Techniques for Investigating Information Theoretic Limits of Information Systems |
| title_short | Computational Techniques for Investigating Information Theoretic Limits of Information Systems |
| title_sort | computational techniques for investigating information theoretic limits of information systems |
| topic | capacity converse bounds computational methods |
| url | https://www.mdpi.com/2078-2489/12/2/82 |
| work_keys_str_mv | AT chaotian computationaltechniquesforinvestigatinginformationtheoreticlimitsofinformationsystems AT jamessplank computationaltechniquesforinvestigatinginformationtheoreticlimitsofinformationsystems AT brenthurst computationaltechniquesforinvestigatinginformationtheoreticlimitsofinformationsystems AT ruidazhou computationaltechniquesforinvestigatinginformationtheoreticlimitsofinformationsystems |