Skip to main content

The Price of Uncertain Priors in Source Coding

Author(s): Braverman, Mark; Juba, Brendan

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorBraverman, Mark-
dc.contributor.authorJuba, Brendan-
dc.identifier.citationBraverman, Mark, and Brendan Juba. "The Price of Uncertain Priors in Source Coding." IEEE Transactions on Information Theory 65, no. 2 (2018): pp. 1165-1171. doi:10.1109/TIT.2018.2888475en_US
dc.description.abstractWe 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.en_US
dc.format.extent1165 - 1171en_US
dc.relation.ispartofIEEE Transactions on Information Theoryen_US
dc.rightsAuthor's manuscripten_US
dc.titleThe Price of Uncertain Priors in Source Codingen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
PriceUncertainPriorsSourceCoding.pdf173.47 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.