M.Sc Thesis

M.Sc StudentKartowsky Assaf
SubjectGreedy-Merge Degrading has Optimal Power-Law
DepartmentDepartment of Electrical and Computer Engineering
Supervisor ASSOCIATE PROF. Ido Tal
Full Thesis textFull thesis text - English Version


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.