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

 

Characterizing the set of entropic vectors under various distribution constraints is a fundamentally important problem in information theory and network coding [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 entropic 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] and conditional independence structure representations  [B7, B8, B9]. More recently, it has been noted that the network coding capacity region  [B1, B10] is a linear projection of Γ_N^* intersected with a vector subspace. These two problems are inherently related, as it has been shown  [B11] 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 entropic vectors associated with these constrained random variables. Hence, there is a fundamental interest in multi-terminal information theory in the region of entropic vectors Γ_N^*() associated with random variables obeying distribution constraints .

In this project, we develop approaches that bound the region of entropic vectors, which include determining the entropic region for binary discrete random variables, matroid based inner bounds, and information geometric properties of entropic region.

Binary Region of Entropic Vectors

Γ_N^* is difficult to characterize for arbitrary N ≥ 4, as Matùš recently definitively proved  [B12], because there are an infinite number of associated linear information inequalities. There are few known computationally tractable inner bounds for Γ_N^* for N ≥ 4  [B13]  [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  [A4, A5] 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 entropic 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  [A6, A7, A5] 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.

Inner Bounds from Representable Matroids & Linear Polymatroids

Matroid theory  [B14] is an abstract generalization of independence in the context of linear algebra to the more general setting of set systems. Though there are many classes of matroids, we are especially interested in one of them, representable matroids, because they can be related to linear codes to solve network coding problems as discussed in  [A8, A9, A1]. A major direction for this research utilizes (representable) matroids, linear polymatroids, and linear codes to characterize the inner bounds on Γ_N^*. We use enumeration tools to obtain the list of (binary and ternary) representable matroids and linear codes. The conic hull of rank functions of these matroids (or codes) give us an inner bound that can be used to determine the linear codes achievable rate regions for networks, as discussed in our network coding project.

There exist some enumeration tools for matroid enumeration using single-element-extension  [B15]. One can get representable ones from the entire list of matroids by checking if the matroids have forbidden minors for the associated representability. However, the enumeration of matroids only goes to less than or equal to 9 elements, due to the double exponentially increase as the ground set size increases, as Fig. 2 shows. Adapting the enumeration tool with forbidden minor characterization of representable matroids enables us to directly enumerate representable ones. We can easily push the enumeration of binary, ternary representable matroids to ground set size 12, as shown in Fig. 2. As stated above, one of the applications of the representable matroid inner bound is to bound the network rate region. The linear space that the network variables can span determines the rank of representable matroids we need to use. If we only enumerate matroids with ranks up to a particular number, we can go further on the enumeration of both general matroids and representable ones. Our recent work  [A1] showed that one can further integrate the network constraints in the enumeration to reduce the enumeration load, as shown in Fig. 2.

Our another recent work  [A2] on this project also proved some important properties on the matroid, especially representable matroid bounds. It was shown that the extreme rays of representable matroid inner bound form a subset of extreme rays of matroid bound, which themselves form a subset of extreme rays of the Shannon outer bound. This implies that once we have extreme rays of Shannon, we can do some verification on them to determine the matroid and representable matroid inner bounds. The relations between different bounds related with matroids on 5,6,7 elements is shown in Fig. 3.

Information Geometric characterization of the Entropy Region Γ_N^*

The field of information geometry  [B16] is a mathematical science which treats sets of probability distributions as a differential geometric manifold with an endowed dually flat geometric structure. The idea is to think of a given probability distribution as a point in a space (through a smooth parameterization), and the collection of such points as a manifold. Of significant interest are natural parameterizations of families of probabilities distributions, especially exponential families, and how the endowed geometric structure implies fundamental limits for estimation within these families due to the Cramer-Rao lower bound.

Information geometry endows a manifold of probability distributions p(x;ξ), parameterized by a vector of real numbers ξ = [ξ_i], with a Riemannian metric, or inner product between tangent vectors, given by the Fisher information:

(1)

This allows us to calculate an inner product between two tangent vectors c = ∑ _ic_i∂_ξi and d = ∑ _id_i∂_ξi at a particular point ξ in the manifold of probability distributions, as

(2)

Selecting this Riemannian metric (indeed, we could have selected others), and some additional structure, allows the differential geometric structure to be related to familiar properties of exponential families and mixture families of probability distributions. The additional structure, called an affine connection(Fig. 4), is given to the manifold to allow us establish a correspondence, called parallel translation, between tangent vectors living the tangent space at two different points along a curve in the manifold by solving a system of ordinary differential equations involving given functions on the manifold called connection coefficients. Just as with a Riemannian metric, we have an infinite number possible of choices for the affine connection (embodied by selecting connection coefficients with respect to a particular parametrization), but if we choose particular ones, called the α-connections, certain differential geometric notions like flatness and autoparallel submanifolds can be related to familiar notions of probability distribution families/subfamilies like exponential families and mixture families.

The natural divergence functions arising in information geometry, which include the Kullback Leibler divergence, can easily be related to the Shannon entropy by measuring the divergence with the uniform distribution. Additionally, one could think of entropic vectors as characterizing simultaneous properties (entropies) of marginal distributions on subsets of variables, and this simultaneous marginal distribution relationship has a well studied structure in information geometry. Thus characterizing the region of entropic vector Γ_N^* could be though of as a problem in information geometry  [A3]. Along this line of work, it was first shown that Shannon facets possess certain information geometric properties, for example, Shannon facets was associated with affine subsets of family of probability distribution when it is regarded in an appropriate parameterization, also the submodularity of the entropy function can be viewed as a consequence of pythagorean style information projection relationships. Furthermore, we have shown that a special type of 4 atom support (0000)(0110)(1010)(1111) has a very natural information geometric explanation(Fig. 5).

Funding for this Topic:

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

Relevant Publications & Presentations

External References