M.Sc Thesis | |

M.Sc Student | Kartowsky Assaf |
---|---|

Subject | Greedy-Merge Degrading has Optimal Power-Law |

Department | Department of Electrical and Computer Engineering |

Supervisor | ASSOCIATE PROF. Ido Tal |

Full Thesis text |

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.

The thesis contains four main results. The first result, from which the thesis 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. 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 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.