Greedy–Merge Degrading has Optimal Power-Law
From MaRDI portal
Publication:4615351
DOI10.1109/TIT.2018.2879802zbMATH Open1427.94059arXiv1701.02119OpenAlexW2899742260WikidataQ128912276 ScholiaQ128912276MaRDI QIDQ4615351FDOQ4615351
Authors: Assaf Kartowsky, Ido Tal 
Publication date: 28 January 2019
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1701.02119
Cited In (1)
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)
