Greedy–Merge Degrading has Optimal Power-Law.

Consider a channel with a given input alphabet size and input distribution. Our aim is to degrade or upgrade it to a channel with at most L output letters. Channel Q is degraded with respect to a channel W if Q can be obtained from W by processing the output of W. Upgrading is the inverse relation. This paper contains four main results. The first result, from which the paper title is derived, deals with the so called “greedy–merge” algorithm. We derive an upper bound on the reduction in mutual information between input and output, as a function of L. 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 (i.e. the power of L). The other main results deal with upgrading. The second result shows that a certain sequence of channels, which 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 give 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 carry out the analysis and show that the increase incurred in mutual information is within a constant factor of the lower bound derived in the second result. [ABSTRACT FROM AUTHOR]