An Upgrading Algorithm With Optimal Power Law

DOI10.1109/TIT.2021.3114375MaRDI QIDQ5032622zbMATH OpenOpenAlexWikidataFDO

Authors Or Ordentlich, Ido Tal

Publication date 17 February 2022

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

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

zbMATH Keywords

algorithmupgraded channel

Mathematics Subject Classification ID

Information theory (general) (94A15) Channel models (including quantum) in information and communication theory (94A40)

Abstract: 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/(|mathcalX|-1)})$, where $|mathcalX|$ 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.

Recommendations

• Algorithms for hierarchical power
• Optimal upgrading schemes for effective shortest paths in networks
• An Algorithm for Computing Optimal Exponent Pairs
• Greedy–Merge Degrading has Optimal Power-Law
• The optimality of upgrade pricing
• Optimal updating of ideal threshold schemes
• The power algorithm in max algebra
• A Generalization of Self-Improving Algorithms
• A Generalization of Self-Improving Algorithms

Cited in

(1)

• Algorithms for hierarchical power

This page was built for publication: An Upgrading Algorithm With Optimal Power Law

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