TY - JOUR
T1 - Minoration via mixed volumes and Cover’s problem for general channels
AU - Liu, Jingbo
N1 - The author gratefully acknowledge Professor Ramon van Handel for very helpful comments on the initial version of the manuscript, especially for pointing out that Lemma already appeared in the work of Pajor []. The author is indebted to Professor Ayfer Ozgur for introducing Cover’s problem, discussions during our previous collaborative work [], and her guidance and support as a mentor in the IT society. The author also thanks Professor Shahar Mendelson for comments on some references about Rademacher complexity. The author thanks the anonymous reviewers for the careful reading and useful references. This work was supported by the start-up grant at the Department of Statistics, University of Illinois.
PY - 2022/6
Y1 - 2022/6
N2 - We give a complete solution to an open problem of Thomas Cover in 1987 about the capacity of a relay channel in the general discrete memoryless setting without any additional assumptions. The key step in our approach is to lower bound a certain soft-max of a stochastic process by convex geometry methods, which is based on two ideas: First, the soft-max is lower bounded in terms of the supremum of another process, by approximating a convex set with a polytope with bounded number of vertices. Second, using a result of Pajor, the supremum of the process is lower bounded in terms of packing numbers by means of mixed-volume inequalities (Minkowski’s first inequality).
AB - We give a complete solution to an open problem of Thomas Cover in 1987 about the capacity of a relay channel in the general discrete memoryless setting without any additional assumptions. The key step in our approach is to lower bound a certain soft-max of a stochastic process by convex geometry methods, which is based on two ideas: First, the soft-max is lower bounded in terms of the supremum of another process, by approximating a convex set with a polytope with bounded number of vertices. Second, using a result of Pajor, the supremum of the process is lower bounded in terms of packing numbers by means of mixed-volume inequalities (Minkowski’s first inequality).
KW - Convex geometry
KW - Empirical process theory
KW - High dimensional probability
KW - Minkowski’s inequality
KW - Multiuser information theory
UR - http://www.scopus.com/inward/record.url?scp=85123840709&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85123840709&partnerID=8YFLogxK
U2 - 10.1007/s00440-022-01111-6
DO - 10.1007/s00440-022-01111-6
M3 - Article
AN - SCOPUS:85123840709
SN - 0178-8051
VL - 183
SP - 315
EP - 357
JO - Probability Theory and Related Fields
JF - Probability Theory and Related Fields
IS - 1-2
ER -