TY - JOUR
T1 - Dispersion Bound for the Wyner-Ahlswede-Körner Network via a Semigroup Method on Types
AU - Liu, Jingbo
N1 - Funding Information:
Manuscript received September 12, 2018; revised June 8, 2020; accepted November 24, 2020. Date of publication December 3, 2020; date of current version January 21, 2021. This work was supported in part by the NSF under Grant CCF-1350595, Grant CCF-1016625, Grant CCF-0939370, and Grant DMS-1148711; in part by the ARO under Grant W911NF-15-1-0479, Grant W911NF-14-1-0094, and Grant AFOSR FA9550-15-1-0180; and in part by the Center for Science of Information. This article was presented in part at the 2018 IEEE International Symposium on Information Theory (ISIT).
Publisher Copyright:
© 1963-2012 IEEE.
PY - 2021/2
Y1 - 2021/2
N2 - We revisit the Wyner-Ahlswede-Körner network, focusing especially on the converse part of the dispersion analysis, which is known to be challenging. Using the functional-entropic duality and the reverse hypercontractivity of the transposition semigroup, we lower bound the error probability for each joint type. Then by averaging the error probability over types, we lower bound the c-dispersion (which characterizes the second-order behavior of the weighted sum of the rates of the two compressors when a nonvanishing error probability is small) as the variance of the gradient of inf PU|X cH(Y|U)+ I( U;X) with respect to QXY , the per-letter side information and source distribution. In comparison, using standard achievability arguments based on the method of types, we upper-bound the c-dispersion as the variance of c Y|U(Y|U)+U;X U; X) , which improves the existing upper bounds but has a gap to the aforementioned lower bound. Our converse analysis should be immediately extendable to other distributed source-type problems, such as distributed source coding, common randomness generation, and hypothesis testing with communication constraints. We further present improved bounds for the general image-size problem via our semigroup technique.
AB - We revisit the Wyner-Ahlswede-Körner network, focusing especially on the converse part of the dispersion analysis, which is known to be challenging. Using the functional-entropic duality and the reverse hypercontractivity of the transposition semigroup, we lower bound the error probability for each joint type. Then by averaging the error probability over types, we lower bound the c-dispersion (which characterizes the second-order behavior of the weighted sum of the rates of the two compressors when a nonvanishing error probability is small) as the variance of the gradient of inf PU|X cH(Y|U)+ I( U;X) with respect to QXY , the per-letter side information and source distribution. In comparison, using standard achievability arguments based on the method of types, we upper-bound the c-dispersion as the variance of c Y|U(Y|U)+U;X U; X) , which improves the existing upper bounds but has a gap to the aforementioned lower bound. Our converse analysis should be immediately extendable to other distributed source-type problems, such as distributed source coding, common randomness generation, and hypothesis testing with communication constraints. We further present improved bounds for the general image-size problem via our semigroup technique.
KW - Markov semigroups
KW - Shannon theory
KW - concentration of measure
KW - converse bounds
KW - distributed systems
KW - functional inequalities
KW - hypercontractivity
UR - http://www.scopus.com/inward/record.url?scp=85097945361&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85097945361&partnerID=8YFLogxK
U2 - 10.1109/TIT.2020.3041791
DO - 10.1109/TIT.2020.3041791
M3 - Article
AN - SCOPUS:85097945361
SN - 0018-9448
VL - 67
SP - 869
EP - 885
JO - IRE Professional Group on Information Theory
JF - IRE Professional Group on Information Theory
IS - 2
M1 - 9279290
ER -