A Newton Algorithm for Computing the Capacity of Discrete Memoryless Channels
Summary :
This paper presents an efficient algorithm for computing the capacity of discrete memoryless channels. The algorithm uses Newton's method which is known to be quadratically convergent. First, a system of nonlinear equations termed Kuhn-Tucker equations is formulated, which has the capacity as a solution. Then Newton's method is applied to the Kuhn-Tucker equations. Since Newton's method does not guarantee global convergence, a continuation method is also introduced. It is shown that the continuation method works well and the convergence of the Newton algorithm is guaranteed. By numerical examples, effectiveness of the algorithm is verified. Since the proposed algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E75-A No.11 pp.1583-1589
- Publication Date
- 1992/11/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Numerical Analysis and Self-Validation
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kiyotaka YAMAMURA, "A Newton Algorithm for Computing the Capacity of Discrete Memoryless Channels" in IEICE TRANSACTIONS on Fundamentals,
vol. E75-A, no. 11, pp. 1583-1589, November 1992, doi: .
Abstract: This paper presents an efficient algorithm for computing the capacity of discrete memoryless channels. The algorithm uses Newton's method which is known to be quadratically convergent. First, a system of nonlinear equations termed Kuhn-Tucker equations is formulated, which has the capacity as a solution. Then Newton's method is applied to the Kuhn-Tucker equations. Since Newton's method does not guarantee global convergence, a continuation method is also introduced. It is shown that the continuation method works well and the convergence of the Newton algorithm is guaranteed. By numerical examples, effectiveness of the algorithm is verified. Since the proposed algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e75-a_11_1583/_p
Copy
@ARTICLE{e75-a_11_1583,
author={Kiyotaka YAMAMURA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Newton Algorithm for Computing the Capacity of Discrete Memoryless Channels},
year={1992},
volume={E75-A},
number={11},
pages={1583-1589},
abstract={This paper presents an efficient algorithm for computing the capacity of discrete memoryless channels. The algorithm uses Newton's method which is known to be quadratically convergent. First, a system of nonlinear equations termed Kuhn-Tucker equations is formulated, which has the capacity as a solution. Then Newton's method is applied to the Kuhn-Tucker equations. Since Newton's method does not guarantee global convergence, a continuation method is also introduced. It is shown that the continuation method works well and the convergence of the Newton algorithm is guaranteed. By numerical examples, effectiveness of the algorithm is verified. Since the proposed algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy.},
keywords={},
doi={},
ISSN={},
month={November},}
Copy
TY - JOUR
TI - A Newton Algorithm for Computing the Capacity of Discrete Memoryless Channels
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1583
EP - 1589
AU - Kiyotaka YAMAMURA
PY - 1992
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E75-A
IS - 11
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - November 1992
AB - This paper presents an efficient algorithm for computing the capacity of discrete memoryless channels. The algorithm uses Newton's method which is known to be quadratically convergent. First, a system of nonlinear equations termed Kuhn-Tucker equations is formulated, which has the capacity as a solution. Then Newton's method is applied to the Kuhn-Tucker equations. Since Newton's method does not guarantee global convergence, a continuation method is also introduced. It is shown that the continuation method works well and the convergence of the Newton algorithm is guaranteed. By numerical examples, effectiveness of the algorithm is verified. Since the proposed algorithm has local quadratic convergence, it is advantageous when we want to obtain a numerical solution with high accuracy.
ER -
English
