The Price of Uncertain Priors in Source Coding

DOI10.1109/TIT.2018.2888475zbMATH Open1427.94068arXiv1811.08976OpenAlexW2900548824MaRDI QIDQ4615378

Author name not available (Why is that?)

Publication date: 28 January 2019

Published in: (Search for Journal in Brave)

Abstract: 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 to 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 $logalpha+log1/epsilon+1$ bits, thus also establishing the nearly tight upper bound.

Full work available at URL: https://arxiv.org/abs/1811.08976

Mathematics Subject Classification ID

No records found.

This page was built for publication: The Price of Uncertain Priors in Source Coding

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4615378)