TY - GEN
T1 - Universal covertness for Discrete Memoryless Sources
AU - Chou, Remi A.
AU - Bloch, Matthieu R.
AU - Yener, Aylin
N1 - Funding Information:
This work was supported in part by NSF under grants CIF-1319338, CNS-1314719, CCF-1320298, CIF-1527074, and by ANR with grant 13-BS03-0008
Publisher Copyright:
© 2016 IEEE.
PY - 2017/2/10
Y1 - 2017/2/10
N2 - Consider a sequence S of length n emitted by a Discrete Memoryless Source (DMS) with unknown distribution p. We wish to construct a lossless source code that maps S to a sequence S′ of minimal length m such that S′ approximates in terms of Kullback-Leibler divergence a sequence emitted by another DMS with known distribution q. Our main result is the existence of a coding scheme that performs such a task with an asymptotically optimal compression rate, i.e., such that the limit of m/n is H(p)/H(q) as n goes to infinity. Our coding scheme overcomes the challenges created by the lack of knowledge about p by relying on a sufficiently fine estimation of H(p), followed by an appropriately designed type-based compression that jointly performs source resolvability and universal lossless source coding. Our result recovers several previous results that either assume p uniform, or q uniform, or p known. The price paid for these generalizations is the use of common randomness with vanishing rate. We further determine that the length of the latter roughly scales as the square root of n, by an analysis of second order asymptotics and error exponents.
AB - Consider a sequence S of length n emitted by a Discrete Memoryless Source (DMS) with unknown distribution p. We wish to construct a lossless source code that maps S to a sequence S′ of minimal length m such that S′ approximates in terms of Kullback-Leibler divergence a sequence emitted by another DMS with known distribution q. Our main result is the existence of a coding scheme that performs such a task with an asymptotically optimal compression rate, i.e., such that the limit of m/n is H(p)/H(q) as n goes to infinity. Our coding scheme overcomes the challenges created by the lack of knowledge about p by relying on a sufficiently fine estimation of H(p), followed by an appropriately designed type-based compression that jointly performs source resolvability and universal lossless source coding. Our result recovers several previous results that either assume p uniform, or q uniform, or p known. The price paid for these generalizations is the use of common randomness with vanishing rate. We further determine that the length of the latter roughly scales as the square root of n, by an analysis of second order asymptotics and error exponents.
UR - http://www.scopus.com/inward/record.url?scp=85015196161&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85015196161&partnerID=8YFLogxK
U2 - 10.1109/ALLERTON.2016.7852275
DO - 10.1109/ALLERTON.2016.7852275
M3 - Conference contribution
AN - SCOPUS:85015196161
T3 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
SP - 516
EP - 523
BT - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016
Y2 - 27 September 2016 through 30 September 2016
ER -