Files and links (2)
Video (supplemental) Presentation of Dissertation defense April 9th 2021 Drexel Univ. Philadelphia Open Access Open Access (License Unspecified)
Dissertation
Designing probabilistic supports to map the entropy region: group actions and a submodularity-based structural theory
Doctor of Philosophy (Ph.D.), Drexel University
Jun 2021
DOI:
https://doi.org/10.17918/00000435
Abstract
Multiple problems in engineering and science have fundamental limits that can be determined by computing network coding capacity regions. Network coding capacity regions, in turn, are implicitly and exactly characterized in terms of the entropy region. For four or more random variables, the boundary of the entropy region is unknown. At four random variables, it is known that reaching the unknown part of the entropy region necessitates nonlinear code constructions. Those nonlinear constructions can, in turn, be parameterized by the supports of the their induced probability distributions. Since different supports can reach identical collections of entropy vectors, and thus the same part of the entropy region, supports are grouped into equivalence classes based on the part of the entropy region they map to. Equivalence classes can easily be formalized through group actions by encoding supports as sets of set partitions. For supports with a fixed number of random variables and a fixed number of atoms, a single representative from every equivalence class can be exhaustively listed utilizing the Leiterspiel algorithm from the theory of group actions. A structural analysis of supports, leveraging sub-modularity of a particular class of functions, is presented that enables a large number of support equivalence classes to be proven incapable of reaching the unknown part of the entropy region. The tools underlying this structural analysis can also be utilized to prove when one support generates entropy vectors which push out farther in a given direction in entropy space than another support; a relationship identified as dominance of the former support over the latter. Furthermore, proofs of violation and dominance can be generated automatically utilizing linear programs constructed from the supports. The power of the structural theory of dominance is demonstrated by providing a highly concise structural characterization of those supports that maximally violate the Ingleton inequality.
Metrics
59 File views/ downloads
49 Record Views
Details
- Title
- Designing probabilistic supports to map the entropy region
- Creators
- Alejandro Erick Trofimoff
- Contributors
- John MacLaren Walsh (Advisor)
- Awarding Institution
- Drexel University
- Degree Awarded
- Doctor of Philosophy (Ph.D.)
- Publisher
- Drexel University; Philadelphia, Pennsylvania
- Number of pages
- vi, 168 pages
- Resource Type
- Dissertation
- Language
- English
- Academic Unit
- College of Engineering (1970-2026); Electrical (and Computer) Engineering (1970-2026); Drexel University
- Other Identifier
- 991015241980604721