## 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 Q_{X|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(Q_{X}\|\π_{X})+I(Q_{U},Q_{X|U})-E\is sufficient to approximate the output distribution π_{X}^{⊗n} using the channel Q_{X|U}^{⊗n}, where Q_{U}\to Q_{X|U}\to Q_{X}, and is also necessary in the case of finite U and X. In particular, a randomness rate of inf_{QU}I(Q_{U},Q_{X|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