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 -