• Home
• Research
• Software
• Facilities
• People
• Publications
• Contact us

Characterizing the set of entropy vectors under various distribution constraints is a fundamentally important problem in information theory  [B1, B2]. Not only would such an accurate characterization allow for the determination of all information inequalities, but it would enable the direct computation of all rate regions for network coding and multiterminal source coding. That is, understanding the fundamental limits for communication over networks is inherently linked with understanding the boundary of the set of entropic vectors.

The interest in the (closure of) the set of entropy vectors for discrete unbounded cardinality random variables Γ_N^*  [B1] and its normalized counterpart Ω_N^*  [B2, B3] originated in the study of linear information inequalities  [B4, B5, B6], as these correspond to supporting halfspaces for these sets. More recently, it has been noted that the network coding capacity region  [B1, B7] is a linear projection of Γ_N^* intersected with a vector subspace. These two problems are inherently related, as it has been shown  [B8] that for every non-Shannon type inequality (i.e., every supporting half space of Γ_N^*) there is a multi-source network coding problem for which the capacity region requires this inequality.

More generally, as all achievable rate regions in information theory are expressed in terms of information measures between random variables obeying certain distribution constraints, they can be expressed as linear projections of entropy vectors associated with these constrained random variables. Hence, there is a fundamental interest in multi-terminal information theory in the region of entropy vectors Γ_N^*() associated with random variables obeying distribution constraints .

Γ_N^* is difficult to characterize for arbitrary N ≥ 4, as Matùš recently definitively proved  [B9], because there are an infinite number of associated linear information inequalities. There are few known computationally tractable inner bounds for Γ_N^* for N ≥ 4  [B10]  [B3], and it is generally unknown how to determine whether a given candidate vector h ∈ R₊^2N-1 is entropic or not. A computational algorithm capable of determining whether or not h ∈Γ_N^* is not presently available for N ≥ 4. Our work  [A1, A2] points out that by restricting the discrete random variables to be binary, one can obtain efficient descriptions of the entropy region, called the set of binary entropy vectors, Φ_N. In particular, we introduce an algorithm which can definitively determine whether a candidate vector h ∈ R₊^2N-1 can be generated by a distribution on N bits. This has enabled us to deliver in  [A3, A4, A2] our primary contribution: an algorithm which, given any polytope outer bound for convΦ_N(), returns a tuned inner bound agreeing on all of its (tight) exposed faces shared with convΦ_N(). Because the inner bounds have this property, their performance increases with increasingly better performing outer bounds. The inner bound technique is easily extended to obtaining bounds for convΓ_N^*() and convΩ_N^*() as a function of outer bounds for these sets, as they contain convΦ_N().

Our current work is applying these inner bound techniques to gain insights about the tightness of existing outer bounds for Ω_N^*, and is dedicated to finding as many extreme points of Ω_N^* as possible.

Fig. 1: Pictorial representation of relationships among bounds for the region of normalized entropy vector Ω₄^* that are discussed in  [A3, A4, A2].

Funding for this Topic:

This work supported by the National Science Foundation under the CAREER award CCF-1053702.

Relevant Publications & Presentations

External References