SOURCE MATCHING PROBLEMS REVISITED

The source matching problem is to find the minimax codes that minimize the maximum redundancies over classes of sources where relative entropy (cross entropy, discrimination information) is adopted as a criterion to measure the redundancy. The convergence of a simple approach different from Davisson and Leon-Garcia's algorithm for finding such minimax codes is presented and shown. This approach is applied as an example to the class of first-order discrete Markov sources. The sufficient statistic previously used by Lee is corrected in his attempt to produce results for the first-order Markov source matching problem. A computational complexity analysis and a numerical study further demonstrates that this simple algorithm significantly reduces the required computing time, when compared to Davisson and Leon-Garcia's algorithm.