On the Computation of the Capacity Region of the Discrete MAC
On the Computation of the Capacity Region of the Discrete MAC
复制标题
离散MAC容量域的计算
DOI：
--
复制
发表时间：
2010
影响因子：
8.3
通讯作者：
J. Vidal
中科院分区：
文献类型：
--
作者：
E. Calvo;D. Palomar;J. Fonollosa;J. Vidal
离散无记忆信道容量的计算是一个凸问题，可以有效地解决使用Arimoto-Blahut（AB）迭代算法。然而，该算法的扩展计算的多终端网络的容量区域是不简单的，因为它会引起非凸问题。在这种情况下，AB算法已经成功地扩展到离散无记忆多址信道（DMAC）的总容量的计算。因此，整个容量区域的计算仍然需要使用计算要求高的搜索方法。在本文中，我们首先给出了一个替代的DMAC的容量区域的重新表述，它将所有的非凸性问题压缩成一个单一的秩一约束。然后，我们提出了有效的方法来计算两个用户的DMAC的容量区域上的外部和内部边界，通过解决一个放松的版本的问题，并将其解决方案投影到原来的可行集。针对数值结果，我们首先采用随机化方法。针对分析结果，我们研究了投影通过最小发散，这相当于边缘化的放松的解决方案。在这种情况下，我们得到的充分条件和必要条件和充分条件的界限是紧的。此外，我们能够表明，一类的边缘化界限完全匹配的容量区域的通道，包括所有的两个用户的二进制输入确定性DMACs以及其他非确定性的通道。然而，一般来说，这两种方法都能够计算非常严格的界限，如各种示例所示。
The computation of the channel capacity of discrete memoryless channels is a convex problem that can be efficiently solved using the Arimoto-Blahut (AB) iterative algorithm. However, the extension of this algorithm to the computation of capacity regions of multiterminal networks is not straightforward since it gives rise to non-convex problems. In this context, the AB algorithm has only been successfully extended to the calculation of the sum-capacity of the discrete memoryless multiple-access channel (DMAC). Thus, the computation of the whole capacity region still requires the use of computationally demanding search methods. In this paper, we first give an alternative reformulation of the capacity region of the DMAC which condenses all the non-convexities of the problem into a single rank-one constraint. Then, we propose efficient methods to compute outer and inner bounds on the capacity region of the two-user DMAC by solving a relaxed version of the problem and projecting its solution onto the original feasible set. Targeting numerical results, we first take a randomization approach. Focusing on analytical results, we study projection via minimum divergence, which amounts to the marginalization of the relaxed solution. In this case we derive sufficient conditions and necessary and sufficient conditions for the bounds to be tight. Furthermore, we are able to show that the class of channels for which the marginalization bounds match exactly the capacity region includes all the two-user binary-input deterministic DMACs as well as other non-deterministic channels. In general, however, both methods are able to compute very tight bounds as shown for various examples.