Analysis for the Slow Convergence in Arimoto Algorithm

Kenji Nakagawa, Yoshinori Takei, Kohei Watabe

Abstract

The Arimoto algorithm is a cornerstone of information theory, used to iteratively calculate the capacity of discrete memoryless channels. While generally efficient, its convergence speed can vary significantly between exponential and $1/N$ rates. This paper provides a rigorous mathematical analysis using Jacobian and Hessian matrices to identify the root cause of this slowdown. We demonstrate that "Type II" boundary conditions—where an input probability is zero but its contribution to mutual information is maximal—are the sole triggers for $1/N$ convergence.

Introduction

Calculating channel capacity ($C$) is essential for determining the maximum reliable transmission rate over a communication channel. The Arimoto algorithm (or Blahut-Arimoto algorithm) is the standard iterative method for this task. Despite its guaranteed convergence, practitioners have long noted inconsistent performance. In many scenarios, the algorithm converges at a fast exponential rate, but in specific "hard" cases, it slows to a $1/N$ crawl. Previous research primarily addressed interior solutions; this work focuses on boundary conditions to precisely predict and explain these performance shifts.

Methodology

The authors model a single step of the Arimoto algorithm as a differentiable mapping function, $F(\lambda)$. To analyze its behavior near the optimal solution ($\lambda^*$), they employ a Taylor expansion around the fixed point, incorporating both first-order (Jacobian) and second-order (Hessian) terms.

Central to the analysis is the classification of input indices based on Kuhn-Tucker conditions:

  • Type I: $\lambda_i^* > 0$. The input is actively used in the optimal distribution.
  • Type II: $\lambda_i^* = 0$, but the Kullback-Leibler (KL) divergence $D(P^i || \lambda^* \Phi) = C$. This represents a boundary case where the input is not used, yet it sits "on the edge" of the optimal set.
  • Type III: $\lambda_i^* = 0$ and $D(P^i || \lambda^* \Phi) < C$.

Eigenvalue analysis reveals that Type II indices result in a Jacobian eigenvalue of exactly 1. This mathematical property prevents exponential convergence, necessitating the use of the Hessian matrix to characterize the resulting $1/N$ rate.

Geometric Insights and Convergence Results

The paper translates these abstract types into geometric configurations of row vectors within the probability simplex.

Exponential Convergence (Type I)

When the optimal distribution lies within the interior of the simplex, or when only Type I and Type III indices are present, the algorithm maintains exponential speed. This is visualized as an "acute triangle" configuration in the output space.

Figure 1: Geometric configuration of Type I indices (Acute Triangle) resulting in exponential convergence.

Slow Convergence (Type II)

The presence of even a single Type II index causes the algorithm to lose its exponential speed. Geometrically, this corresponds to a "right triangle" configuration where the optimal point $Q^*$ lies exactly on the boundary of the segment formed by other input points.

Figure 2: Geometric configuration of a Type II boundary condition (Right Triangle) leading to slow 1/N convergence.

Numerical simulations validate these theoretical findings. For an input alphabet size of $m=3$, the authors derived an explicit limit formula for the convergence speed: $\lim_{N \to \infty} N \mu_i^N = \text{constant}$. In experimental tests, the theoretical limits derived from the Hessian analysis closely matched numerical results (e.g., a theoretical limit of $-0.503$ vs. a numerical result of $-0.510$ at $N=500$).

Conclusion

This research pinpoints Type II indices as the unique cause of slow convergence in the Arimoto algorithm. By moving beyond first-order Jacobian analysis to include the Hessian, the authors provide a framework for predicting $1/N$ convergence rates. While the detailed $1/N$ constant derivation is currently limited to $m=3$, the general principles of index classification and eigenvalue analysis offer a path toward accelerating the algorithm in high-dimensional boundary cases.

Summary updated

BibTeX
@inproceedings{nakagawa2018analysis,
  author = {Kenji Nakagawa and Yoshinori Takei and Kohei Watabe},
  title = {{Analysis for the Slow Convergence in Arimoto Algorithm}},
  booktitle = {ISITA},
  year = {2018},
  doi = {10.23919/isita.2018.8664307},
}
Figure