Second-order converses via reverse hypercontractivity

Jingbo Liu, Ramon van Handel, Sergio Verdú

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

Abstract

A strong converse shows that no procedure can beat the asymptotic (as blocklength n ! 1) fundamental limit of a given information-theoretic problem for any fixed error probability. A second-order converse strengthens this conclusion by showing that the asymptotic fundamental limit cannot be exceeded by more than O. p1n /. While strong converses are achieved in a broad range of information-theoretic problems by virtue of the “blowing-up method” — a powerful methodology due to Ahlswede, Gács and Körner (1976) based on concentration of measure — this method is fundamentally unable to attain second-order converses and is restricted to finite-alphabet settings. Capitalizing on reverse hypercontractivity of Markov semigroups and functional inequalities, this paper develops the “smoothing-out” method, an alternative to the blowing-up approach that does not rely on finite alphabets and that leads to second-order converses in a variety of information-theoretic problems that were out of reach of previous methods.

Original languageEnglish (US)
Pages (from-to)103-163
Number of pages61
JournalMathematical Statistics and Learning
Volume2
Issue number2
DOIs
StatePublished - 2019

All Science Journal Classification (ASJC) codes

  • Computational Theory and Mathematics
  • Signal Processing
  • Statistics and Probability
  • Theoretical Computer Science

Keywords

  • Strong converse
  • blowing-up lemma
  • concentration of measure
  • information-theoretic inequalities
  • reverse hypercontractivity

Fingerprint

Dive into the research topics of 'Second-order converses via reverse hypercontractivity'. Together they form a unique fingerprint.

Cite this