Linear Programming Based Finite Blocklength Converses in Information Theory

摘要

A linear programming based framework is presented to derive finite blocklength converses for coding problems in information theory which is also extendable to network settings. In the point-to-point setting, the LP based framework recovers and in fact improves on almost all well-known finite blocklength converses for lossy joint source-channel coding, lossy source coding and channel coding. Moreover, the LP based framework is shown to be asymptotically tight for the averaged and compound channels under the maximum probability of error criterion. Further, for multiterminal Slepian-Wolf source coding problem, a systematic approach to synthesize new converses from considering point-to-point lossless source coding (with side-information at decoder) sub-problems is introduced. The method derives new finite blocklength converse for Slepian- Wolf coding which significantly improves on the converse of Miyake and Kanaya.