One-sentence Summary

Researchers from IEEE-affiliated institutions and Yuanming Yu establish new optimality results for Marton's bound in broadcast channels by leveraging a novel cardinality bounding method, proving the bound is tight for specific product channels while demonstrating that existing outer bounds are not universally tight.

Key Contributions

• The paper establishes the optimality of Marton's inner bound for new classes of product broadcast channels by computing their exact capacity regions.
• This work demonstrates that the best known outer bound by Nair and El Gamal is not tight in general by showing a gap between this bound and the capacity region for specific channels.
• The authors derive sufficient conditions for a global maximizer of Marton's bound that prove the 2-letter extension does not increase the achievable rate, and they introduce a new outer bound for product broadcast channels based on these findings.

Introduction

In network information theory, determining the exact capacity region of a broadcast channel remains a fundamental open problem where a sender transmits private messages to multiple receivers over a noisy medium. While Marton's inner bound is the tightest known achievable rate region, it is unclear if it is optimal in general, and the best existing outer bound by Nair and El Gamal has been suspected of being loose but lacked a definitive counterexample. The authors leverage a recently developed method for bounding auxiliary random variable cardinalities to analyze the multi-letter extension of Marton's bound, which allows for numerical evaluation and rigorous comparison. They establish the optimality of Marton's bound for new classes of product broadcast channels and prove that the Nair–El Gamal outer bound is strictly suboptimal by constructing a specific example where the two bounds diverge.

Method

The authors investigate the capacity region of product broadcast channels, focusing on the interplay between achievable rates and outer bounds. The general communication framework is illustrated in the system diagram below.

In this setup, an encoder maps a pair of private messages $(M_1, M_2)$(M1​,M2​) into a codeword $X^n$Xn. This signal is transmitted over a broadcast channel defined by the transition probability $q(y, z|x)$q(y,z∣x). The channel generates two distinct outputs, $Y^n$Yn and $Z^n$Zn, which are processed by Decoder 1 and Decoder 2 to produce message estimates $\hat{M}_1$M^1​ and $\hat{M}_2$M^2​. The primary objective is to characterize the set of achievable rate pairs $(R_1, R_2)$(R1​,R2​) for this system.

To analyze specific channel behaviors, the authors examine product channels formed by combining two independent broadcast channels. A critical example used to demonstrate the suboptimality of certain outer bounds is the reversely semi-deterministic product channel. The structure of this specific channel is depicted in the graph below.

The diagram displays two component channels. In the left component, the mapping from input $X_1$X1​ to output $Y_1$Y1​ is deterministic (blue edges), while the mapping to $Z_1$Z1​ is stochastic (red edges). In the right component, this relationship is reversed: the mapping from $X_2$X2​ to $Z_2$Z2​ is deterministic (red edges), while the mapping to $Y_2$Y2​ is stochastic (blue edges). This "reversely" semi-deterministic structure is pivotal for the theoretical results presented.

The core analytical method relies on the $\lambda$λ-sum-rate, a weighted sum of mutual information terms defined for auxiliary random variables $(U, V, W)$(U,V,W) satisfying the Markov chain $(U, V, W) \rightarrow X \rightarrow (Y, Z)$(U,V,W)→X→(Y,Z). The $\lambda$λ-sum-rate is given by:

$\lambda \mathrm{-} SR_M(\mathbf{q}, p(u,v,w,x)) := \lambda I(W;Y) + (1-\lambda)I(W;Z) + I(U;Y|W) + I(V;Z|W) - I(U;V|W)$λ−SRM​(q,p(u,v,w,x)):=λI(W;Y)+(1−λ)I(W;Z)+I(U;Y∣W)+I(V;Z∣W)−I(U;V∣W)

The authors leverage this quantity to derive sufficient conditions under which the sum rate factorizes over product channels. They establish that for reversely semi-deterministic channels, the optimal sum rate is achieved by minimizing the sum of the $\lambda$λ-sum-rates of the individual components over $\lambda \in [0,1]$λ∈[0,1]. Furthermore, the study compares Marton's inner bound against the UV outer bound, utilizing the Randomized Time-Division (RTD) strategy as a simpler achievable scheme that coincides with Marton's bound for binary input channels but behaves differently in the product setting.

Experiment

• Demonstrated that the tightest known outer bound is strictly sub-optimal for Marton's inner bound.
• Established a new outer bound for product broadcast channels that coincides with Marton's inner bound for specific channel classes with previously unknown capacity regions.
• Showed that the new outer bound strictly improves upon the previously known tightest outer bound for product broadcast channels.
• Provided additional results that facilitate the computation of Marton's inner bound.