E_γ-Resolvability

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_QUI(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.