Greedy–Merge Degrading has Optimal Power-Law

DOI10.1109/TIT.2018.2879802MaRDI QIDQ4615351zbMATH OpenOpenAlexWikidataFDO

Authors Assaf Kartowsky, Ido Tal

Publication date 28 January 2019

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

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

Mathematics Subject Classification ID

Measures of information, entropy (94A17)

Abstract: Consider a channel with a given input distribution. Our aim is to degrade it to a channel with at most L output letters. One such degradation method is the so called "greedy-merge" algorithm. We derive an upper bound on the reduction in mutual information between input and output. For fixed input alphabet size and variable L, the upper bound is within a constant factor of an algorithm-independent lower bound. Thus, we establish that greedy-merge is optimal in the power-law sense.

Cited in

(1)

• An Upgrading Algorithm With Optimal Power Law

This page was built for publication: Greedy–Merge Degrading has Optimal Power-Law

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