Abstract
Calculating the channel capacity of a discrete memoryless channel (DMC) is a fundamental task in information theory, traditionally solved through iterative methods like the Arimoto-Blahut algorithm. This paper introduces a novel "projection algorithm" that leverages Information Geometry to find the capacity-achieving output distribution. By establishing a mathematical analogy between channel capacity and the Smallest Enclosing Circle (SEC) problem in Euclidean space, the authors develop a heuristic that offers linear computational complexity and high accuracy, effectively overcoming the limitations of traditional brute-force and iterative approaches.
Introduction
In information theory, capacity is defined as the maximum mutual information between the input and output of a channel. While the theoretical definition is clear, identifying the specific input distribution that achieves this maximum remains an optimization challenge, particularly for large input alphabets. Existing methods, such as Muroga’s method, often face exponential complexity, while the Arimoto-Blahut algorithm can encounter numerical instabilities when probabilities approach zero. This research proposes a geometric alternative that simplifies the search for optimal input symbols.
Geometric Analogy: The Smallest Enclosing Circle
The core innovation of this work lies in the application of Information Geometry, specifically Amari’s $\alpha$-geometry. The authors demonstrate that finding the capacity-achieving output distribution is mathematically analogous to finding the center of the Smallest Enclosing Circle (SEC) for a set of points.
In Euclidean space, the SEC center is the point that minimizes the maximum distance to a set of points. In the context of probability distributions, this distance is replaced by Kullback-Leibler (KL) divergence.
As shown in Figure 1, when points are in a specific configuration, the optimal center $Q^*$ is equidistant ($d^*$) from the boundary points. The authors use dual coordinate systems ($\eta$ and $\theta$) to ensure that Euclidean intuitions, such as the Pythagorean theorem, remain valid in this information-theoretic space.
The Projection Algorithm
The proposed "Projection Algorithm" iteratively refines the search for the optimal distribution. The process begins by finding an "equidistant point" relative to all input vectors. If this point yields negative barycentric coordinates (which map to input probabilities), it indicates the point lies outside the valid simplex.
In such cases, the algorithm projects the point onto affine subspaces, as illustrated in Figure 2. By removing the component with the "most negative" coordinate and repeating the projection, the algorithm efficiently narrows down the set of input symbols that should have positive probability. This heuristic approach avoids the $O(2^m)$ complexity of checking every possible subset of input symbols, reducing it to a linear $O(m-2)$ complexity.
Handling Real-World Data: Lifting Dimension
A significant technical hurdle in geometric algorithms is the assumption of "general position"—the idea that points are not perfectly aligned or redundant. To handle real-world channel matrices that may violate this, the authors introduce a "lifting" technique. By adding a tiny epsilon ($\epsilon$) perturbation, they lift the points into a higher-dimensional space. This ensures the algorithm remains robust and functional without requiring a prior rank check of the channel matrix.
Results and Performance
The algorithm was evaluated using 10,000 synthetic simulations for both SEC and Channel Capacity problems across various dimensions ($m$ inputs, $n$ outputs):
- Accuracy: The channel capacity heuristic (HC) achieved a success rate exceeding 99.5% in nearly all test cases (up to $m=10, n=20$).
- Efficiency: The computational overhead was significantly lower than brute-force methods, maintaining linear scaling relative to the number of inputs.
- Robustness: The lifting dimension method successfully processed matrices that would typically cause standard geometric algorithms to fail due to singularity or redundancy.
Conclusion and Future Work
The projection algorithm provides a powerful, intuitive framework for calculating channel capacity. While it is a heuristic and can fail in rare edge cases where the "most negative" removal strategy is too aggressive, its speed and accuracy make it a compelling alternative for high-dimensional problems. Future research aims to provide a general proof for an arbitrary number of points and explore the application of these geometric techniques to other information-theoretic functions, such as the rate-distortion function.
Summary updated