Logo image
Back
Entropy region decomposition techniques to reduce the complexity of network coding capacity region proofs
Dissertation   Open access

Entropy region decomposition techniques to reduce the complexity of network coding capacity region proofs

Yirui Liu
Doctor of Philosophy (Ph.D.), Drexel University
Oct 2021
DOI:
https://doi.org/10.17918/00000624
pdf
Liu_Yirui_20211.98 MBDownloadView
PDF Open Access Open Access (License Unspecified)

Abstract

Electric capacity Coding theory Complexity reduction Entropy region decomposition
The fundamental limits of a wide variety of coded information systems are dictated by network coding capacity regions. Indeed, coded caching systems, efficient transmission on broadcast cellular downlinks with index coding, and the design of resilient cloud storage systems, are all shown to have fundamental design tradeoffs dictated by the capacity regions of networks that can be abstracted from the way in which these systems must encode and decode messages they exchange and store. Given any such abstracted network, its capacity region can, in principle, be determined as a projection of the intersection of the entropy region with some constraints. More broadly, the entropy region is key to determining answers to a number of fundamental questions in information theory, including, among others, determining all information inequalities. While formal equivalences between the design tradeoffs in these applied coding problems, fundamental information theory questions, and expressing the entropy region have been shown, the use of the entropy region as a practical solution method to solve these problems is plagued by two main factors. First of all, the entropy region is incompletely characterized, with only loose outer and inner bounds being available for four or more random variables. As these random variables represent coded messages exchanged in the underlying engineering problems, all but the smallest problems suffer from the possibility that they may depend on a part of the entropy region where the bounds are not tight. Second of all, the bounds for the entropy region have prohibitive complexity, indeed, they are polyhedral cones with a number of dimensions and inequalities that are exponential in the number of random variables. This dissertation sets about addressing these two issues of incomplete determination and complexity of the entropy region using a divide-and-conquer style approach to obtain a decomposition of the entropy region. The main idea is that since the property of a putative function being entropic is preserved under the dropping, or projection removing the entropies of, random variables, a simple bound relating some of the dimensions of the entropy region among a higher number of variables can be obtained by pasting together several entropy region of smaller subsets of random variables. While the region obtained in this manner will always be an outer bound, this dissertation proves a number of novel circumstances in which this outer bound is also an inner bound, and thus is tight, fully determining a projection of the entropy region. Notably, the conditions proven can be utilized in an iterative manner to obtain results about projections of the entropy region for an arbitrarily large number of random variables. The results are then shown, using this iterative argument, to address the issue of complexity as well. Indeed, certain structures are proven to not only be completely determined using the techniques, but also to have complexity that scales only linearly in the number of random variables. Shifting attention back towards applications, the dissertation next sets about showing how the entropy region decomposition can be applied to reduce the complexity of calculating network coding capacity regions. The notion of a valid cut is introduced to link a decomposition of a network graph and a decomposition of an associated entropy region. Then, two different approaches for reducing the complexity of network coding rate region using the associated entropy region decomposition are discussed. First, we show that, using a valid cut of a particular large network, its capacity region can be determined by pasting together lower dimensional entropy region bounds associated with its parts. Second, considering the problem of computing the capacity region of a large series of networks, we show common subnetworks, resulting from a valid cut of a large network, may be shared among several big networks, and thus a wise memory-computation tradeoff can be performed by computing and saving only a small fraction of partial rate regions of these subnetworks and reuse them to calculate the rate regions of a relatively large collection of non-isomorphic big networks.

Metrics

77 File views/ downloads
33 Record Views

Details

Logo image