Eγ-Resolvability

Jingbo Liu, Paul Cuff, Sergio Verdu

Research output: Contribution to journalArticlepeer-review

42 Scopus citations

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 languageEnglish (US)
Article number7792173
Pages (from-to)2629-2658
Number of pages30
JournalIEEE Transactions on Information Theory
Volume63
Issue number5
DOIs
StatePublished - 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

Fingerprint

Dive into the research topics of 'Eγ-Resolvability'. Together they form a unique fingerprint.

Cite this