TY - JOUR

T1 - The price of uncertain priors in source coding

AU - Braverman, Mark

AU - Juba, Brendan

N1 - Funding Information:
Manuscript received December 17, 2015; revised April 26, 2017; accepted November 7, 2018. Date of publication December 19, 2018; date of current version January 18, 2019. M. Braverman was supported in part by NSF under Grant CCF-1525342, NSF under Grant CAREER CCF-1149888, in part by the Packard Fellowship in Science and Engineering, and in part by the Simons Collaboration on Algorithms and Geometry. B. Juba was supported in part by ONR under Grant N000141210358, in part by AFOSR Young Investigator Award, and in part by NSF under Grant CCF-1718380. This paper was presented in part at Allerton 2015.

PY - 2019/2

Y1 - 2019/2

N2 - 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. 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 + log 1/ + 1 bits, thus also establishing the nearly tight upper bound.

AB - 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. 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 + log 1/ + 1 bits, thus also establishing the nearly tight upper bound.

KW - Distributed adaptive compression

KW - Source coding

KW - Uncertain priors

UR - http://www.scopus.com/inward/record.url?scp=85058900487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85058900487&partnerID=8YFLogxK

U2 - 10.1109/TIT.2018.2888475

DO - 10.1109/TIT.2018.2888475

M3 - Article

AN - SCOPUS:85058900487

VL - 65

SP - 1165

EP - 1171

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 2

M1 - 8581454

ER -