A great many problems in network information theory, both fundamental and applied, involve determining a minimal set of inequalities linking the Shannon entropies of a certain collection of subsets of random variables. In principle this minimal set of inequalities could be determined from the entropy region, whose dimensions are all the subsets of random variables, by projecting out dimensions corresponding to the irrelevant subsets. As a general solution technique, however, this method is plagued both by the incompletely known nature of the entropy region as well as the exponential complexity of its bounds. Even worse, for four or more random variables, it is known that the set of linear information inequalities necessary to completely describe the entropy region must be uncountably infinite. A natural question arises then, if there are certain nontrivial collections of subsets where the inequalities linking only these subsets is both completely known, and have inequality descriptions that are linear in the number of random variables. This paper answers this question in the affirmative. A decomposition expressing the collection of inequalities linking a larger collection of subsets from that of smaller collections of subsets is first proven. This decomposition is then used to provide systems of subsets for which it both exhaustively determines the complete list of inequalities, which is linear in the number of variables.

Determining the rate region of a network is of great importance in the research area of network coding. Lots of attempts have been made and significant progress has been achieved over the last decade on this topic. Although these researches provide us with multiple ways of calculating the outer or inner bounds of rate region, the sheer complexity of the problem, which involves expressing and projecting a very high dimensional polyhedra, makes it computationally infeasible beyond networks with 10s of edges. Aimed at reducing the complexity of the rate region calculation, in this paper a new theorem that implicitly determines the rate region of a network is proved and a corresponding systematic way of applying the theorem to calculate explicitly the outer bounds to a rate region is proposed. Compared with the traditional method, the proposed method has the potential to calculate the true rate region via the projection of simpler polyhedra that has exponentially less dimensions and is characterized by exponentially less facets.

A new method is presented, consisting of exclusively simple linear algebra computations, for computing the linear programming Shannon outer bound to the network coding capacity region of a directed hypergraph network. This linear algebraic formulation enables a new upper bound on the worst case complexity of computing the Shannon outer bound to a network coding capacity region to be determined.

The boundary of the entropy region has been shown to determine fundamental inequalities and limits in key problems in network coding, streaming, distributed storage, and coded caching. The unknown part of this boundary requires nonlinear constructions, which can, in turn, be parameterized by the support of their underlying probability distributions. Recognizing that the terms in entropy are submodular enables the design of such supports to maximally push out towards this boundary.

The rate regions of multilevel diversity coding systems (MDCSs), a sub-class of the broader family of multi-source multi-sink networks with special structure, are investigated in a systematic way. We enumerate all non-isomorphic MDCS instances with at most three sources and four encoders. Then, the exact rate region of every one of these more than 7000 instances is proven via computations showing that the Shannon outer bound matches with a custom constructed linear code-based inner bound. Results gained from these computations are summarized in key statistics involving aspects, such as the sufficiency of scalar binary codes, the necessary size of vector binary codes, and so on. Also, it is shown how to construct the codes for an achievability proof. Based on this large repository of rate regions, a series of results about general MDCS cases of arbitrary size that they inspired is introduced and proved. In particular, a series of embedding operations that preserve the property of sufficiency of scalar or vector codes is presented. The utility of these operations is demonstrated by boiling the thousands of MDCS instances for which scalar binary (superposition) codes are insufficient down to 12 (26) forbidden the smallest embedded MDCS instances.instances.

Recent algorithmic developments have enabled computers to automatically determine and prove the capacity regions of small hypergraph networks under network coding. A structural theory relating network coding problems of different sizes is developed to make the best use of this newfound computational capability. A formal notion of network minimality is developed, which removes components of a network coding problem that are inessential to its core complexity. Equivalence between different network coding problems under relabeling is formalized via group actions, an algorithm which can directly list single representatives from each equivalence class of minimal networks up to a prescribed network size is presented. This algorithm, together with rate region software, is leveraged to create a database containing the rate regions for all minimal network coding problems with five or fewer sources and edges, a collection of 744119 equivalence classes representing more than 9 million networks. In order to best learn from this database, and to leverage it to infer rate regions and their characteristics of networks at scale, a hierarchy between different network coding problems is created with a new theory of combinations and embedding operators.

A well-known inner bound on the stability region of the finite-user slotted Aloha protocol is the set of all arrival rates for which there exists some choice of the contention probabilities such that the associated worst case service rate for each user exceeds the user's arrival rate, denoted Λ. Although testing membership in Λ of a given arrival rate can be posed as a convex program, it is nonetheless of interest to understand the properties of this set. In this paper, we develop new results of this nature, including, 1) an equivalence between membership in Λ and the existence of a positive root of a given polynomial, 2) a method to construct a vector of contention probabilities to stabilize any stabilizable arrival rate vector, 3) the volume of Λ, 4) explicit polyhedral, spherical, and ellipsoid inner and outer bounds on Λ, and 5) characterization of the generalized convexity properties of a natural “excess rate” function associated with Λ, including the convexity of the set of contention probabilities that stabilize a given arrival rate vector.

Summary form only given. The problem of function computation arises in in many practical scenarios, such as query computation in distributed databases. In such scenarios, it is often possible to exploit the structure of the function to reduce the amount of information that needs to be exchanged in order to compute it. In a so-called a collocated network, information is exchanged as users take turns sending messages to a sink, the central estimation officer (CEO), with each user perfectly overhearing the message from every other user, as depicted in Fig 1. In this paper a problem of function computation is studied in a collocated network where m independent nodes in transmission range with each other, exchange messages with the aim of losslessly computing the extremization function f = arg maxi Xi, or f = maxi Xi. An optimal dynamic quantizer for the user's observations is proposed via a dynamic program which provides the CEO just enough information to compute the desired functions with no error. Both fundamental limits and practical schemes are presented. Ma et al, in [1] studied this problem in a distributed source coding framework, and proposed an iterative algorithm via a convex geometric approach to compute the minimum sum rate of for anyfinite and infinite number of rounds. Building upon this prior work, we propose an achievable scheme using scalar quantizers followed by Huffman encoding the results. We compute the fundamental limit from [1] for the extrema function, and study the the fundamental tradeoff between the rate-cost and the delay in optimal interactive quantization schemes. We also design some low complexity suboptimal scheme which substantially shrinks the search space of the optimal dynamic program. Moreover, using optimal heterogeneous quantizers result in substantial rate savings relative to the parallel homogenous quantizers in [2].

Several users observing independent random variables exchange error-free messages with one another and a central receiver, the central estimation officer (CEO), with the aim of enabling the CEO to compute either the maximum across users (the max), or a a user attaining this maximum (the arg max) for each element of their local observation sequences. The fundamental lower bound on the information exchange rate required over all quantization schemes, both scalar and vector, is computed for this interactive problem with a known iterative convex geometric method. Next, an optimal dynamic program achieving the minimum expected rate and expected rate delay tradeoff over all scalar quantization schemes is presented, and the benefits of enabling users to overhear each others' messages is assessed. Finally, a series of substantially reduced complexity dynamic programs are shown, both theoretically and empirically, to obtain performance close to the fundamental limits, and to scale favorably as the number of users grow.

This paper investigates when Shannon-type inequalities completely characterize the part of the closure of the entropy region Γ̅n* that is symmetric under the action of a specified random variable permutation group. This question is answered exhaustively for every group permuting n = 4 and n = 5 random variables, while multiple examples for arbitrary n ≥ 6 are provided for both tightness and non-tightness of the Shannontype inequalities. For instance, a new result shows that non-Shannon-type inequalities are necessary under the action of the cyclic group Cn, the dihedral group Dn, as well as S1× Cn-1and S1× Dn-1, for every n ≥ 6.

A key aspect of many resource allocation problems is the need for the resource controller to compute a function, such as the max or arg max, of the competing users' metrics. Information must be exchanged between the competing users and the resource controller in order for this function to be computed. In many practical resource controllers, the competing users' metrics are communicated to the resource controller, which then computes the desired extremization function. However, in this paper, it is shown that information rate savings can be obtained by recognizing that the controller only needs to determine the result of this extremization function. If the extremization function is to be computed losslessly, the rate savings are shown in most cases to be at most 2 b independent of the number of competing users. Motivated by the small savings in the lossless case, simple achievable schemes for both the lossy and interactive variants of this problem are considered. It is shown that both of these approaches have the potential to realize large rate savings, especially in the case where the number of competing users is large. For the lossy variant, it is shown that the proposed simple achievable schemes are in fact close to the fundamental limit given by the rate distortion function.

We establish connections between graph theoretic symmetry, symmetries of network codes, and symmetries of rate regions for k-unicast network coding and multi-source network coding. We identify a group we call the network symmetry group as the common thread between these notions of symmetry and characterize it as a subgroup of the automorphism group of a directed cyclic graph appropriately constructed from the underlying network's directed acyclic graph. Such a characterization allows one to obtain the network symmetry group using algorithms for computing automorphism groups of graphs. We discuss connections to generalizations of Chen and Yeung's partition symmetrical entropy functions and how knowledge of the network symmetry group can be utilized to reduce the complexity of computing the LP outer bounds on network coding capacity as well as the complexity of polyhedral projection for computing rate regions.

We propose algorithms for finding extreme rays of rate regions achievable with vector linear codes over finite fields Fq, q ∈ {2, 3, 4} for which there are known forbidden minors for matroid representability. We use the idea of single element extensions (SEEs) of matroids and enumeration of non-isomorphic matroids using SEEs, to first propose an algorithm to obtain lists of all non-isomorphic matroids representable over a given finite field.We modify this algorithm to produce only the list of all non-isomorphic connected matroids representable over the given finite field. We then integrate the process of testing which matroids in a list of matroids form valid linear network codes for a given network within matroid enumeration. We name this algorithm, which essentially builds all matroids that form valid network codes for a given network from scratch, as network-constrained matroid enumeration.

In this paper, we consider the problem of communicating over an Additive White Gaussian Noise (AWGN) channel with an unknown noise power without feedback. For the case where the noise power is drawn from a distribution with K distinct values, we model the channel as a K-user broadcast channel, with a user for each of the K possible noise powers. We propose two metrics for measuring the loss of using a broadcast code compared to an omniscient transmitter. Using these metrics, we solve for the optimal power allocation in a superposition code. For the case of K = 2, we prove several interesting properties of the optimal power allocation and the minimum loss.

This paper suggests that information geometry may form a natural framework to deal with the unknown part of the boundary of entropic region. An application of information geometry shows that distributions associated with Shannon facets can be associated, in the right coordinates, with affine collections of distributions. This observation allows an information geometric reinterpretation of the Shannon-type inequalities as arising from a Pythagorean style relationship. The set of distributions which violate Ingleton's inequality, and hence are linked with the part of the entropic region which is yet undetermined, is shown also to have a surprising affine information geometric structure in a special case involving four random variables and a certain support. These facts provide strong evidence for the link between information geometry and characterizing the boundary of the entropic region.

Authentication schemes based on wireless physical layer channel information have gained significant attention in recent years. It has been shown in recent studies, that the channel based authentication can either cooperate with existing higher layer security protocols or provide some degree of security to networks without central authority such as sensor networks. We propose a Gaussian Mixture Model based semi-supervised learning technique to identify intruders in the network by building a probabilistic model of the wireless channel of the network users. We show that even without having a complete apriori knowledge of the statistics of intruders and users in the network, our technique can learn and update the model in an online fashion while maintaining high detection rate. We experimentally demonstrate our proposed technique leveraging pattern diversity and show using measured channels that miss detection rates as low as 0.1% for false alarm rate of 0.3% can be achieved.

We present a variational Bayesian algorithm that enhances the log spectra of noisy speech using speaker dependent priors. This algorithm extends prior work by Frey et al. where the Algonquin algorithm was introduced to enhance speech log spectra in order to improve speech recognition in noisy environments. Our work is built on the intuition that speaker dependent priors would work better than priors that attempt to capture global speech properties. Experimental results using the TIMIT data set and the NIST 2004 speaker recognition evaluation (SRE) data are presented to demonstrate the algorithm's performance.

Practical codes are developed for quadratic Gaussian lossy compression when side information may be absent by hybridizing successively refinable trellis coded quantization (SR-TCQ) and low-density parity-check (LDPC) codes. A 2-refinement level SR-TCQ is used to generate a common description for both decoders and an individual description for the decoder with side information. Then, the common description is losslessly compressed while the individual description is compressed using a LDPC code which exploits the side information in a belief propagation decoder. Simulation results show that the practical codes require no more than 0.46 extra bits at moderate rates and no more than 0.7 extra bits at low rates from the theoretical bounds.

The effect of a power amplifier nonlinearity on multi-antenna orthogonal frequency division multiplexing (OFDM) transmitters utilizing subcarrier beamforming is investigated. Theoretical analysis and simulation shows that such systems can exhibit significant performance degradation due to the power amplifier nonlinearity when there are channel state feedback errors. The SINR degradation under solely channel mismatch is shown to be significantly better than when power amplifier nonlinearity effects are included. The ultimate conclusion is that power amplifier nonlinearity effects should be considered when designing per subcarrier transmit beamformers.

We present a variational Bayesian algorithm for joint speech enhancement and speaker identification that makes use of speaker dependent speech priors. Our work is built on the intuition that speaker dependent priors would work better than priors that attempt to capture global speech properties. We derive an iterative algorithm that exchanges information between the speech enhancement and speaker identification tasks. With cleaner speech we are able to make better identification decisions and with the speaker dependent priors we are able to improve speech enhancement performance. We present experimental results using the TIMIT data set which confirm the speech enhancement performance of the algorithm by measuring signal-to-noise (SNR) ratio improvement and perceptual quality improvement via the Perceptual Evaluation of Speech Quality (PESQ) score. We also demonstrate the ability of the algorithm to perform voice activity detection (VAD). The experimental results also demonstrate that speaker identification accuracy is improved.

A method for checking membership in the region of entropic vectors generated fromNbits is presented. A general technique for utilizing this method to create inner bounds for regions of entropic vectors as a function of outer bounds is then presented. These two algorithms are then used to provide new insights regarding relationships among well known bounds for the region of entropic vectors..

Belief propagation, via a novel reinterpretation of the Bethe free energy's pseudo-dual, is shown to be related to a novel relaxation of maximum likelihood detection via a constrained optimization. The conventional maximum likelihood detection falls out for a zero constraint, and belief propagation's fixed points are obtained for other constraint values.

Belief propagation is shown to be an instance of a hybrid between two projection algorithms in the convex programming literature: Dykstra's algorithm with cyclic Bregman projections and an alternating Bregman projections algorithm. Via this connection, new results concerning the convergence and performance of belief propagation can be proven by exploiting the corresponding literature about the two projections algorithms it hybridizes. In this regard, it is identified that the lack of guaranteed convergence for belief propagation results from the asymmetry of its Bregman divergence by proving that when the associated hybrid projection algorithm generalization is used with a symmetric Bregman divergence, it always converges. Additionally, by characterizing factorizations that are close to acyclic in a manner independent of their girth, a new collection of distributions for which belief propagation is guaranteed to perform well is identified using the new projection algorithm framework.

Via multiterminal information theory, a framework is presented for deriving fundamental rate–delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and random linear network coded networks. The rate–delay tradeoff is formulated as a calculus problem on a capacity region of a related abstracted broadcast channel. Given this general framework for studying such rate–delay tradeoffs, the extreme case of uniform networks, in which each possible received packet arrival order is equally likely, is considered. For these networks, the rate–delay calculus problem is simplified to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger numbers of packets, may be accurately approximated through the calculus of variations by appropriate relaxation of an integer constraint. Explicit expressions for the rate–delay tradeoff in uniform networks are presented in the special cases of i) constant packet inter-arrival times, and ii) exponential independent and identically distributed (i.i.d.) packet arrival times. Finally, the delay mitigating codes achieving these rate–delay tradeoffs are discussed.

The estimation error performance of Gaussian belief propagation based distributed estimation in a large sensor network employing random sleep strategies is explicitly evaluated for a simple model using density evolution analysis. Both regular sleep strategies, in which the number of nodes awake at any time instant is fixed, as well as irregular sleep strategies, in which the number of awake nodes may vary, are analyzed. The calculated estimation error is used to study the tradeoff between estimation accuracy and energy consumption, as well as to dictate the optimal parameters for the random sleep strategy.

Via multiterminal information theory, we present fundamental rate delay tradeoffs that delay mitigating codes must have when utilized over multipath routed and network coded networks. We formulate plotting the rate delay tradeoff as a calculus problem on a capacity region of a related abstracted broadcast channel. This calculus problem simplifies to an integer programming problem, which for small numbers of packets may be solved explicitly, or for larger values of packets, may be accurately approximated through the calculus of variations by relaxing the integer constraint. We prove the utility of our techniques by plotting the rate delay tradeoff for networks in which the packets experience independent exponentially distributed propagation and queuing delays while traversing the network.

Expectation propagation (EP) is a theoretical extension of the belief propagation family of message passing algorithms for statistical inference which allows for efficient handling of models with continuous random variables as well as second or higher order correlation via the use of standard exponential families of probability measures. Here we provide theoretically rigorous justifications for the use of density evolution to analyze the convergence and performance behavior of the family of algorithms in the large system regime by extending and expanding on the corresponding results for belief propagation decoding and turbo decoding.

We extend Gaussian approximation density evolution (DE) techniques from the soft iterative decoding of turbo and low density parity check (LDPC) codes to the performance and convergence analysis of belief propagation (BP) and expectation propagation (EP) in randomly connected very large sparse homogeneous factor graphs. A strict form of the Gaussian approximation allows the use of extrinsic information transfer (EXIT) charts to study the performance and convergence of the algorithms. The result is a graphical tool that design engineers can use to quickly predict the performance and convergence speed of BP or EP applied to these inference problems. We demonstrate the utility of the new tool, and a motivation for the generalization of the results, by showing how it may surprisingly be applied to determine the performance of a scheme for distributed data fusion in a sensor network.

The near-optimal performance of the turbo decoder has been a source of intrigue among communications engineers and information theorists, given itsad hocorigins that were seemingly disconnected from optimization theory. Naturally one would inquire whether the favorable performance might be explained by characterizing the turbo decoder via some optimization criterion or performance index. Recently, two such characterizations have surfaced. One draws from statistical mechanics and aims to minimize the Bethe approximation to a free energy measure. The other characterization involves constrained likelihood estimation, a setting perhaps more familiar to communications engineers. The intent of this paper is to assemble a tutorial overview of these recent developments, and more importantly to identify the formal mathematical duality between the two viewpoints. The paper includes tutorial background material on the information geometry tools used in analyzing the turbo decoder, and the analysis accommodates both the parallel concatenation and serial concatenation schemes in a common framework.

Expectation propagation defines a family of algorithms for approximate Bayesian statistical inference which generalize belief propagation on factor graphs with loops. As is the case for belief propagation in loopy factor graphs, it is not well understood why the stationary points of expectation propagation can yield good estimates. In this paper, given a reciprocity condition which holds in most cases, we provide a constrained maximum likelihood estimation problem whose critical points yield the stationary points of expectation propagation. Expectation propagation may then be interpreted as a nonlinear block Gauss Seidel method seeking a critical point of this optimization problem

The turbo decoder was not originally introduced as a solution to an optimization problem, which has impeded attempts to explain its excellent performance. Here it is shown, that the turbo decoder is an iterative method seeking a solution to an intuitively pleasing constrained optimization problem. In particular, the turbo decoder seeks the maximum-likelihood sequence (MLS) under the false assumption that the input to the encoders are chosen independently of each other in the parallel case, or that the output of the outer encoder is chosen independently of the input to the inner encoder in the serial case. To control the error introduced by the false assumption, the optimizations are performed subject to a constraint on the probability that the independent messages happen to coincide. When the constraining probability equals one, the global maximum of the constrained optimization problem is the maximum-likelihood sequence detection (MLSD), allowing for a theoretical connection between turbo decoding and MLSD. It is then shown that the turbo decoder is a nonlinear block Gauss-Seidel iteration that aims to solve the optimization problem by zeroing the gradient of the Lagrangian with a Lagrange multiplier of -1. Some conditions for the convergence for the turbo decoder are then given by adapting the existing literature for Gauss-Seidel iterations

Many previous attempts at analyzing the convergence behavior of turbo and iterative decoding, such as EXIT style analysis (ten Brink, S., 2001) and density evolution (El Gamal, H. and Hammons, A.R., Jr, 2001), ultimately appeal to results which become valid only when the block length grows rather large, while still other attempts, such as connections to factor graphs (Kshischang, F.R. et al., 2001) and belief propagation (McEliece, R.J., 1998), have been largely unsuccessful at showing convergence due to loops in the turbo coding graph. The paper presents an information geometric interpretation which, built on the results of M. Moher and T. A. Gulliver (IEEE Trans. Inform. Theory, vol.4, p.3097-104, 1998), S. Ikeda et al. (IEEE Trans. Inform. Theory, vol.50, p.1097-114, 2004), and T. Richardson (IEEE Trans. Inform. Theory, vol.46, p.9-23, 2000), allows us to relate the quantities of interest in the turbo decoder. Using it, we point out a measure which is key in studying convergence.

Many previous attempts at analyzing the convergence behavior of turbo and iterative decoding, such as EXIT style analysis (S. ten Brink, Oct. 2001) and density evolution (H. El Gamal and A. R. Hammons, Jr, Feb. 2001), ultimately appeal to results which become valid only when the block length grows rather large, while still other attempts, such as connections to factor graphs (F. R. Kshischang, et al., Feb. 2001) and belief propagation (R. J. McEliece, et al., Feb. 1998), have been largely unsuccessful at showing convergence due to loops in the turbo coding graph. The information geometric attempts (M. Moher and T. A. Gulliver, Nov. 1998), (T. Richardson, Jan. 2000), (S. Ikeda, et al., June 2004), (B. Muquest, et al., June 2002), and (J. Walsh, et al., March 2005), in turn have been inhibited by inability to efficiently describe intrinsic information extraction as an information projection. This paper recognizes turbo decoding as an instance of a Gauss-Seidel iteration on a particular nonlinear system of equations. This interpretation holds regardless of block length, and allows a connection to existing convergence results for nonlinear block Gauss Seidel iterations. We thus adapt existing convergence theory for the Gauss Seidel iteration to give sufficient conditions for the convergence of the turbo decoder that hold regardless of the block length

Channel shortening (a generalization of equalization) is often necessary for mitigation of intersymbol and intercarrier interference in multicarrier transceivers. The MERRY (multicarrier equalization by restoration of redundancy) algorithm has previously been shown to shorten a channel blindly and adaptively to the length of the guard interval in a multicarrier system. MERRY is modified to remove the square root and division needed at each iteration, with the added benefit of allowing the use of constraints other than a unit norm equalizer. An extension is proposed which allows for the use of more data in the MERRY update. The algorithm is generalized to the MIMO case. Blind symbol synchronization and initialization techniques are proposed. Simulations demonstrate the success of the algorithm and the synchronization technique in a MIMO setting.

We examine performance issues encountered when connecting two adaptive signal processing devices in a series feedforward fashion. After introducing the notion of an adaptive element, we develop a simple behavior theory for series feedforward connected adaptive elements given a few reasonable assumptions. We then move on to predict ways such interconnections of adaptive elements may misbehave. A brief example of misbehavior in a pair of interconnected adaptive receiver components is included to highlight the implications of this emerging theory.