The Price of Uncertain Priors in Source Coding

作     者：Braverman, Mark Juba, Brendan 

作者机构：Princeton Univ Dept Comp Sci Princeton NJ 08540 USA Harvard Univ Sch Engn & Appl Sci Cambridge MA 02138 USA Washington Univ St Louis Dept Comp Sci & Engn St Louis MO 63130 USA 

出 版 物：《IEEE TRANSACTIONS ON INFORMATION THEORY》 (IEEE信息论汇刊)

年 卷 期：2019年第65卷第2期

页      面：1165-1171页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：NSF [CCF-1525342, CAREER CCF-1149888, CCF-1718380] Packard Fellowship in Science and Engineering Simons Collaboration on Algorithms and Geometry ONR [N000141210358] AFOSR Young Investigator Award 

主　　题：Source coding uncertain priors distributed adaptive compression 

摘      要：We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a prior distribution that is known to be close to the source distribution, a problem first considered by Juba et al. We consider the question of how much longer the messages need to be in order to cope with the uncertainty about the receiver s prior and the source distribution, respectively, as compared with the standard source coding problem. We consider two variants of this uncertain priors problem: the original setting of Juba et al. in which the receiver is required to correctly recover the message with probability 1, and a setting introduced by Haramaty and Sudan, in which the receiver is permitted to fail with some probability epsilon. In both settings, we obtain lower bounds that are tight up to logarithmically smaller terms. In the latter setting, we furthermore present a variant of the coding scheme of Juba et al. with an overhead of log alpha + log 1/epsilon + 1 bits, thus also establishing the nearly tight upper bound.