國立高雄大學圖資館 |

Entropy Region Decomposition Techniques to Reduce the Complexity of Network Coding Capacity Region Proofs.

Record Type:	Electronic resources : Monograph/item
Title/Author:	Entropy Region Decomposition Techniques to Reduce the Complexity of Network Coding Capacity Region Proofs.
Author:	Liu, Yirui.
Published:	Ann Arbor : ProQuest Dissertations & Theses, 2022
Description:	130 p.
Notes:	Source: Dissertations Abstracts International, Volume: 83-05, Section: B.
Notes:	Advisor: Walsh, John MacLaren.
Contained By:	Dissertations Abstracts International83-05B.
Subject:	Electrical engineering.
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28775508
ISBN:	9798494497260

Entropy Region Decomposition Techniques to Reduce the Complexity of Network Coding Capacity Region Proofs.
Liu, Yirui.

Entropy Region Decomposition Techniques to Reduce the Complexity of Network Coding Capacity Region Proofs. - Ann Arbor : ProQuest Dissertations & Theses, 2022 - 130 p.

Source: Dissertations Abstracts International, Volume: 83-05, Section: B.

Thesis (Ph.D.)--Drexel University, 2022.

This item must not be sold to any third party vendors.

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.

ISBN: 9798494497260Subjects--Topical Terms:

454503
Electrical engineering.
Subjects--Index Terms:

Capacity region

Entropy Region Decomposition Techniques to Reduce the Complexity of Network Coding Capacity Region Proofs.
LDR:05441nmm a2200373 4500 001 616490
005 20220513114351.5
008 220920s2022 ||||||||||||||||| ||eng d
020 $a 9798494497260
035 $a (MiAaPQ)AAI28775508
035 $a AAI28775508
040 $a MiAaPQ $c MiAaPQ
100 1 $a Liu, Yirui. $0 (orcid)0000-0003-0829-1407 $3 915851
245 1 0 $a Entropy Region Decomposition Techniques to Reduce the Complexity of Network Coding Capacity Region Proofs.
260 1 $a Ann Arbor : $b ProQuest Dissertations & Theses, $c 2022
300 $a 130 p.
500 $a Source: Dissertations Abstracts International, Volume: 83-05, Section: B.
500 $a Advisor: Walsh, John MacLaren.
502 $a Thesis (Ph.D.)--Drexel University, 2022.
506 $a This item must not be sold to any third party vendors.
520 $a 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.
590 $a School code: 0065.
650 4 $a Electrical engineering. $3 454503
650 4 $a Information technology. $3 184390
650 4 $a Computer engineering. $3 212944
650 4 $a Codes. $3 915853
650 4 $a Computer science. $3 199325
650 4 $a Entropy. $3 191594
653 $a Capacity region
653 $a Complexity reduction
653 $a Entropyregion decomposition
653 $a Network coding
690 $a 0544
690 $a 0489
690 $a 0984
690 $a 0464
710 2 $a Drexel University. $b Electrical Engineering (College of Engineering). $3 915852
773 0 $t Dissertations Abstracts International $g 83-05B.
790 $a 0065
791 $a Ph.D.
792 $a 2022
793 $a English
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=28775508