Efficient Approximation of Channel Capacities

DOI10.1109/TIT.2015.2401002MaRDI QIDQ2978670zbMATH OpenOpenAlexFDO

Authors Tobias Sutter, David Sutter, Peyman Mohajerin Esfahani, John Lygeros

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1407.7629

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Channel models (including quantum) in information and communication theory (94A40)

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}NsqrtlogN/varepsilon)$ to provide an estimate of the capacity to within $varepsilon$, 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.

Recommendations

• A practical method for approaching the channel capacity of constrained channels
• Efficient Approximation of Quantum Channel Capacities
• scientific article; zbMATH DE number 4191549
• Uniform finite-dimensional approximation of basic capacities of energy-constrained channels
• Capacity of dimension-limited channels
• On the capacity of a cascade of channels
• scientific article; zbMATH DE number 3453478
• Approaching capacity of a continuous channel by discrete input distributions
• Computation of channel capacity based on self-concordant functions

Cited in

(10)

• Capacity of random channels with large alphabets
• scientific article; zbMATH DE number 3956962 (Why is no real title available?)
• A practical method for approaching the channel capacity of constrained channels
• Progress Towards Achieving Channel Capacity
• Constrained Capacities for Faster-Than-Nyquist Signaling
• Sharp Analytical Capacity Upper Bounds for Sticky and Related Channels
• Generalized maximum entropy estimation
• Convergence in capacity and applications
• Distortion based potential game for distributed coverage control
• Reverse EM-problem based on Bregman divergence and its application to classical and quantum information theory

This page was built for publication: Efficient Approximation of Channel Capacities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2978670)