An Upgrading Algorithm With Optimal Power Law
Or Ordentlich, Ido Tal · IEEE Transactions on Information Theory · 2021
Consider a channel$W$along with a given input distribution$P_{X}$. In certain settings, such as in the construction of polar codes, the output alphabet of$W$is ‘too large’, and hence we replace$W$by a channel$Q$having a smaller output alphabet. We say that$Q$is upgraded with respect to$W$if$W$is obtained from$Q$by processing its output. In this case, the mutual information$I(P_{X},W)$between the input and output of$W$is upper-bounded by the mutual information$I(P_{X},Q)$between the input and output of$Q$. In this paper, we present an algorithm that produces an upgraded channel$Q$from$W$, as a function of$P_{X}$and the required output alphabet size of$Q$, denoted$L$. We show that the difference in mutual informations is ‘small’. Namely, it is$O(L^{-2/(| \mathcal {X}|-1)})$, where$| \mathcal {X}|$is the size of the input alphabet. This power law of$L$is optimal. We complement our analysis with numerical experiments which show that the developed algorithm improves upon the existing state-of-the-art algorithms also in non-asymptotic setups.