Abstract
The conventional channel resolvability refers to the minimum rate needed for an input process to approximate the channel output distribution in total variation distance. In this paper, we study Eγ-resolvability, in which total variation is replaced by the more general Eγ distance. A general one-shot achievability bound for the precision of such an approximation is developed. Let QX|U be a random transformation, n be an integer, and E (0,+\infty). We show that in the asymptotic setting where\γ = (nE), a (nonnegative) randomness rate above inf QU: D(QX|πX)≤ E\D(QX\|\πX)+I(QU,QX|U)-E\is sufficient to approximate the output distribution πX⊗n using the channel QX|U⊗n, where QU\to QX|U\to QX, and is also necessary in the case of finite U and X. In particular, a randomness rate of infQUI(QU,QX|U)-E is always sufficient. We also study the convergence of the approximation error under the high-probability criteria in the case of random codebooks. Moreover, by developing simple bounds relating Eγ and other distance measures, we are able to determine the exact linear growth rate of the approximation errors measured in relative entropy and smooth Rényi divergences for a fixed-input randomness rate. The new resolvability result is then used to derive: 1) a one-shot upper bound on the probability of excess distortion in lossy compression, which is exponentially tight in the i.i.d. setting; 2) a one-shot version of the mutual covering lemma; and 3) a lower bound on the size of the eavesdropper list to include the actual message and a lower bound on the eavesdropper false-alarm probability in the wiretap channel problem, which is (asymptotically) ensemble-tight.
Original language | English (US) |
---|---|
Article number | 7792173 |
Pages (from-to) | 2629-2658 |
Number of pages | 30 |
Journal | IEEE Transactions on Information Theory |
Volume | 63 |
Issue number | 5 |
DOIs | |
State | Published - May 2017 |
All Science Journal Classification (ASJC) codes
- Information Systems
- Computer Science Applications
- Library and Information Sciences
Keywords
- Resolvability
- broadcast channel
- mutual covering lemma
- source coding
- wiretap channel