06-04-2017 14:30  Communication and Information Theory

Greedy-Merge Degrading Optimal Power-Law

Consider a channel with a given input alphabet size and a given input distribution. Our aim is to degrade or upgrade it to a channel with at most L output letters. In this talk we will present four main results. The first result, from which the talk's title is derived, deals with the so called ``greedy-merge'' algorithm. We introduce an upper bound on the reduction in mutual information between input and output. This 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. The other main results deal with upgrading. The second result shows that a certain sequence of channels that was previously shown to be ``hard'' for degrading, displays the same hardness in the context of upgrading. That is, suppose we are given such a channel and a corresponding input distribution. If we upgrade (degrade) to a new channel with L output letters, we incur an increase (decrease) in mutual information between input and output. We show that a previously derived bound on the decrease in mutual information for the degrading case is also a lower bound on the increase for the upgrading case. The third result is an efficient algorithm for optimal upgrading, in the binary-input case. That is, we are given a channel and an input distribution. We must find an upgraded channel with L output letters, for which the increase in mutual information is minimal. We present a simple characterization of such a channel, which implies an efficient algorithm. The fourth result is an analog of the first result for the upgrading case, when the input is binary. That is, we first present a sub-optimal algorithm for the setting considered in the third result. The main advantage of the sub-optimal algorithm is that it is amenable to analysis. We show that the increase incurred in mutual information is within a constant factor of the lower bound derived in the second result.

Location: 1061
Speaker: Assaf Kartowsky
Affiliation: Dept. of Electrical Engineering Technion Back