Efficient Approximation of Channel Capacities

Abstract

We propose an iterative method for approximately computing the capacity of discrete memoryless channels, possibly under additional constraints on the input distribution. Based on duality of convex programming, we derive explicit upper and lower bounds for the capacity. The presented method requires $O(M^{2}N\sqrt{\log N}/\epsilon )$ to provide an estimate of the capacity to within $\epsilon$, where $N$ and $M$ denote the input and output alphabet size; a single iteration has a complexity $O(MN)$. We also show how to approximately compute the capacity of memoryless channels having a bounded continuous input alphabet and a countable output alphabet under some mild assumptions on the decay rate of the channel's tail. It is shown that discrete-time Poisson channels fall into this problem class. As an example, we compute sharp upper and lower bounds for the capacity of a discrete-time Poisson channel with a peak-power input constraint.

32 pages, 3 figures, revised version

References in corpus (2)

• Continuity of quantum channel capacities
• Squeezing the Arimoto-Blahut algorithm for faster convergence

Cited by in corpus (8)

• Efficient Approximation of Quantum Channel Capacities
• Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory
• Efficient accessible bounds to the classical capacity of quantum channels
• Bounding the Classical Capacity of Multilevel Damping Quantum Channels
• Analytical calculation formulas for capacities of classical and classical-quantum channels
• On Simultaneous Information and Energy Transmission through Quantum Channels
• Computing the channel capacity of a communication system affected by uncertain transition probabilities
• Capacity of Random Channels with Large Alphabets