Ribbons from Independence Structure: Hypercontractivity, Φ \Phi -Mutual Information, and Matrix Φ \Phi -Entropy

Chenyu Wang, Amin Gohari · 2026

Read Ribbons from Independence Structure: Hypercontractivity, Φ \Phi -Mutual Information, and Matrix Φ \Phi -Entropy by Chenyu Wang, Amin Gohari (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-18516.txt.

Introduction

Chenyu Wang and Amin Gohari study how fast a joint set of facts can be squeezed when some of its parts stand free of the rest. In maths, a band marks the range in which a shrink step is sure to boost how tight the facts bind. The band shifts when parts of the set do not lean on each other. A chart of which parts are free can be drawn as a web with links for shared groups.

The pair find tight bounds for that band in some plain cases. For the wide case they give a clear inner bound built from a blend of the web's marks. Their bounds tell coders how much gain a shrink step can promise. That gain sets the cost of codes that send facts with less waste. Firm bounds may guide fresh codes for speech, shots, and text.

Catalog record

CREATORChenyu Wang, Amin Gohari
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE52 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-18516

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Ribbons from Independence Structure: Hypercontractivity, Φ \Phi -Mutual Information, and Matrix Φ \Phi -Entropy Chenyu Wang, Amin Gohari Abstract We study the hypercontractivity ribbon and the Φ \Phi -ribbon for joint distributions that obey a given independence structure, obtaining tight bounds in some basic regimes. For general independence structures, modeled as a hypergraph whose hyperedges specify mutually independent subcollections of random variables, we provide an explicit inner bound on the Φ \Phi -ribbon described by a simple convex hull of incidence vectors. We also provide a new multipartite generalization version and a Φ \Phi -mutual information analogue of the Zhang–Yeung inequality, which implies nontrivial points in the hypercontractivity ribbon and the Φ \Phi -ribbon respectively. Finally, we propose the matrix Φ \Phi -ribbon based on matrix Φ \Phi -entropy and establish the tensorization and data processing properties, together with the calculation of an exact matrix SDPI constant for the doubly symmetric binary source. 1 Introduction Given a joint distribution p_{X^{n}} on n random variables X^{n}=(X_{1},\dots,X_{n}) , the hypercontractivity (HC) ribbon is defined as \mathfrak{R}(X_{1};\dots;X_{n})\triangleq\left\{(\lambda_{1},\dots,\lambda_{n})\in[0,1]^{n}\colon\sum_{i=1}^{n}\lambda_{i}I(U;X_{i})\leq I(U;X^{n}),\quad\forall U\right\}. The following two facts are well understood. First, for any p_{X^{n}} , one always has \left\{(\lambda_{1},\dots,\lambda_{n})\in[0,1]^{n}\colon\sum_{i=1}^{n}\lambda_{i}\leq 1\right\}\subseteq\mathfrak{R}(X_{1};\dots;X_{n}). The above inclusion is tight when X_{1}=\cdots=X_{n} , in which case the HC ribbon is exactly the simplex \sum_{i}\lambda_{i}\leq 1 . At the other extreme, if X_{1},\dots,X_{n} are mutually independent, the HC ribbon equals the full cube [0,1]^{n} . These facts about the two extreme regimes (full dependence and full independence) continue to hold for the \Phi -ribbon [ 1 ] (which generalizes the HC ribbon). But what about the intermediate regime between the two extremes in which the variables satisfy some partial independence constraint? This paper is motivated by the following question: when the independence of X_{1},\dots,X_{n} is only partially constrained, which (\lambda_{1},\dots,\lambda_{n}) are guaranteed to lie in the ribbon for every distribution consistent with that pattern? Our first contribution provides sharp answers in basic regimes and a general sufficient region for arbitrary independence structures. In particular, if X_{1},\dots,X_{n} are only assumed to be k -wise independent (any k of the variables are mutually independent), we show that the guaranteed \Phi -ribbon becomes \displaystyle\Bigl\{(\lambda_{1},\dots,\lambda_{n})\in[0,1]^{n}:\ \sum_{i=1}^{n}\lambda_{i}\leq k\Bigr\}, and this description is tight for the HC ribbon. We establish optimality by explicit counterexamples outside this set. To treat general independence structures, we model the constraints using a hypergraph H=(V,E) on V=[n]\triangleq\{1,\dots,n\} , where each hyperedge S\in E indicates that \{X_{i}:i\in S\} are mutually independent. For this setting, we give an explicit inner bound on the ribbon described by the convex hull of the origin, the singleton incidence vectors, and the incidence vectors of hyperedges. Next, we provide a connection between the non-Shannon information inequalities and the HC ribbon. In particular, the celebrated Zhang–Yeung inequality [ 2 ] yields nontrivial points in the HC ribbon under a specific case where there are no direct independence structures. A multipartite extension of the Zhang–Yeung inequality was given in [ 3 ] . We show how such inequalities fit naturally into our framework, provide a streamlined derivation via our general bounds, and present another multipartite extension of the Zhang–Yeung inequality. Moreover, we develop a \Phi -mutual information analogue of the Zhang–Yeung inequality, which yields nontrivial \Phi -ribbon points. Finally, we introduce the matrix \Phi -ribbon by replacing scalar \Phi -entropy with matrix \Phi -entropy in the sense of Chen and Tropp [ 4 ] . To the best of our knowledge, this matrix \Phi -ribbon notion has not appeared previously. We establish the tensorization and the data processing properties for the matrix \Phi -ribbon and we compute the exact strong data processing inequality (SDPI) constant for the doubly symmetric binary source (DSBS). Moreover, some of the results from the previous sections can be extended to the matrix \Phi -ribbon. 2 Preliminaries 2.1 \Phi -ribbon The \Phi -divergence (usually called f -divergence in the literature) was originally proposed by Ali and Silvey [ 5 ] as well as Csiszár [ 6 , 7 ] : \displaystyle D_{\Phi}(q_{X}\|p_{X}) \displaystyle\triangleq\sum_{x}p(x)\Phi\left(\frac{q(x)}{p(x)}\right)-\Phi(1). Similarly, the \Phi -mutual information can be defined as \displaystyle I_{\Phi}(X;Y)\triangleq D_{\Phi}(p_{XY}\|p_{X}p_{Y})=\sum_{x,y}p(x)p(y)\Phi\left(\frac{p(x,y)}{p(x)p(y)}\right)-\Phi(1). The concept of \Phi -mutual information is related to \Phi -entropy, defined as follows: given a convex function \Phi on some domain \mathcal{D} , a function f:\mathcal{X}\rightarrow\mathcal{D} , and a random variable X on \mathcal{X} , the \Phi -entropy of f is defined to be (refer to [ 8 , 9 , 10 ] ) \displaystyle H_{\Phi}(f) \displaystyle=\mathbb{E}[\Phi(f)]-\Phi(\mathbb{E}[f]). Given some arbitrary p(x,y) , define f_{x}(y)=\frac{p(x,y)}{p(x)p(y)} . Then I_{\Phi}(X;Y)=\sum_{x}p(x)H_{\Phi}(f_{x}) where H_{\Phi}(f_{x}) is calculated using p(y) for every x . Moreover, I_{\Phi}(X;Y)=\sum_{x}p(x)D_{\Phi}(p_{Y|x}\|p_{Y}) . Thus the \Phi -entropy, the \Phi -divergence and the \Phi -mutual information are related when \mathbb{E}[f]=1 and f\geq 0 . Given a function f_{XY} of two random variables (X,Y) , we define \displaystyle H_{\Phi}(f|Y) \displaystyle=\mathbb{E}[\Phi(f)]-\mathbb{E}_{Y}[\Phi(\mathbb{E}[f|Y])] \displaystyle=\sum_{y}p(y)\big(\mathbb{E}[\Phi(f)|Y=y]-\Phi(\mathbb{E}[f|Y=y])\big). (1) Then we have the chain rule H_{\Phi}(f)=H_{\Phi}(\mathbb{E}[f|Y])+H_{\Phi}(f|Y) . Definition 1 . We define \mathscr{F} to be the class of smooth convex functions \Phi , whose domain is a convex subset of \mathbb{R} , that are not affine (not of the form at+b for some constants a and b ) and satisfy one of the following equivalent conditions (see [ 11 , Exercise 14.2] ): 1. (s,t)\mapsto p\Phi(s)+(1-p)\Phi(t)-\Phi\!\bigl(ps+(1-p)t\bigr) , for any p\in[0,1] , is jointly convex. 2. (s,t)\mapsto\Phi(s)-\Phi(t)-\Phi^{\prime}(t)(s-t) is jointly convex. 3. (s,t)\mapsto\bigl(\Phi^{\prime}(s)-\Phi^{\prime}(t)\bigr)(s-t) is jointly convex. 4. (s,t)\mapsto\Phi^{\prime\prime}(s)t^{2} is jointly convex. 5. 1/\Phi^{\prime\prime} is concave. 6. \Phi^{\prime\prime\prime\prime}\,\Phi^{\prime\prime}\geq 2\bigl(\Phi^{\prime\prime\prime}\bigr)^{2} . The class \mathscr{F} implies the subadditivity of the \Phi -entropy [ 1 ] . Suppose \Phi\in\mathscr{F} . If X_{1},\dots,X_{n} are mutually independent, for any f , we have \displaystyle H_{\Phi}(f)\leq\sum_{i=1}^{n}H_{\Phi}\left(f|X_{\widehat{i}}\right) where X_{\widehat{i}}=(X_{1},\dots,X_{i-1},X_{i+1},\dots,X_{n}) . For \Phi\in\mathscr{F} , the \Phi -ribbon [ 1 ] of random variables X_{1},\dots,X_{n} is defined as the set of all (\lambda_{1},\dots,\lambda_{n})\in[0,1]^{n} that \displaystyle\sum_{i=1}^{n}\lambda_{i}H_{\Phi}(\mathbb{E}[f|X_{i}]) \displaystyle\leq H_{\Phi}(f), for any function f . When we restrict that f\geq 0 and \mathbb{E}[f]=1 , the above region is equivalent to \displaystyle\mathfrak{R}_{\Phi}(X_{1};\dots;X_{n})\triangleq\bigg\{(\lambda_{1},\dots,\lambda_{n})\in[0,1]^{n}:\sum_{i=1}^{n}\lambda_{i}I_{\Phi}(U;X_{i})\leq I_{\Phi}(U;X^{n})\quad\forall U\bigg\} (see [ 1 , Theorem 14] ). In this paper, we will adopt the definition \mathfrak{R}_{\Phi}(X_{1};\dots;X_{n}) as the \Phi -ribbon since the use of the auxiliary U aligns with the HC ribbon. We can recover the HC ribbon when \Phi(t)=t\log t . The following results for the \Phi -ribbon are given in [ 1 , Example 10, Proposition 11, Theorem 14] : Proposition 1 . For \Phi\in\mathscr{F} , we have 1. \{(\lambda_{1},\dots,\lambda_{n}):\sum_{i=1}^{n}\lambda_{i}\leq 1\} is always a subset of the \Phi -ribbon for any p_{X^{n}} . Moreover, when X_{1}=\dots=X_{n} the above set is exactly the \Phi -ribbon. 2. If X_{1},\dots,X_{n} are mutually independent, the \Phi -ribbon is exactly [0,1]^{n} . 2.2 Matrix \Phi -entropy Tropp and Chen [ 4 ] extend the \Phi -entropy to the matrix-valued functions. Consider \boldsymbol{F}:\mathcal{X}\to\mathbb{M}^{+} which is a matrix-valued function. For the diagonal matrix \boldsymbol{S}=\operatorname{diag}(s_{1},\dots,s_{d}) , define \Phi(\boldsymbol{S})\triangleq\operatorname{diag}(\Phi(s_{1}),\dots,\Phi(s_{d})) . The positive semidefinite matrix A admits the diagonalization \boldsymbol{A}=\boldsymbol{U}\boldsymbol{S}\boldsymbol{U}^{\ast} . Then define \Phi(\boldsymbol{A})\triangleq\boldsymbol{U}\Phi(\boldsymbol{S})\boldsymbol{U}^{\ast} . Let \mathbb{M}^{\operatorname{sa}} be the set of Hermitian matrices and \mathbb{M}^{+} be the set of positive semi-definite matrices (PSD). A matrix valued function \Phi is differentiable at \boldsymbol{A}\in\mathbb{M}^{\operatorname{sa}} if there exists a linear operator \mathsf{D}\Phi(\boldsymbol{A})(\cdot) such that for all \boldsymbol{H}\in\mathbb{M}^{\operatorname{sa}} , \displaystyle\|\Phi(\boldsymbol{A}+\boldsymbol{H})-\Phi(\boldsymbol{A})-\mathsf{D}\Phi(\boldsymbol{A})(\boldsymbol{H})\|=o(\|\boldsymbol{H}\|). The linear operator \mathsf{D}\Phi(\boldsymbol{A})(\cdot) is called the Frechét derivative of \Phi at \boldsymbol{A} . Let \mathsf{D}\Phi(A)(\cdot,\cdot) denote the second order Frechét derivative. In [ 4 ] , the

Read the complete text