Source-linked AI summary
On Maximal Correlation, Hypercontractivity, and the Data Processing Inequality studied by Erkip and Cover
Venkat Anantharam, Amin Gohari, Sudeep Kamath, Chandra Nair
TL;DR
The paper addresses geometric characterizations of maximal correlation and the hypercontractivity ribbon, alongside an incorrect data processing inequality claimed by Erkip and Cover. It characterizes the quantities through convexity of an entropy-based function and supplies a counterexample plus a tight corrected constant. The resulting framework also recovers known properties and clarifies the distinction between local convexity and contact with the lower convex envelope.
Problem
The paper targets limited geometric characterizations of maximal correlation and the chordal slope of the hypercontractivity ribbon, as well as an incorrect Erkip–Cover data processing inequality.
Method
The paper studies tλ(X)=H(Y)−λH(X), characterizing maximal correlation through positive-semidefinite Hessians and s∗(X;Y) through contact with its lower convex envelope.
Results
The geometric characterizations recover known properties, while a counterexample disproves the Erkip–Cover inequality and establishes a corrected tight constant.
Takeaways & Limitations
Maximal correlation corresponds to a local-convexity threshold, whereas s∗(X;Y) corresponds to the threshold for lying on the lower convex envelope.
Abstract
from arXiv · showhide
In this paper we provide a new geometric characterization of the Hirschfeld-Gebelein-Rényi maximal correlation of a pair of random $(X,Y)$, as well as of the chordal slope of the nontrivial boundary of the hypercontractivity ribbon of $(X,Y)$ at infinity. The new characterizations lead to simple proofs for some of the known facts about these quantities. We also provide a counterexample to a data processing inequality claimed by Erkip and Cover, and find the correct tight constant for this kind of inequality.
I. INTRODUCTION
The paper studies maximal correlation and hypercontractivity through geometric properties of entropy-based functions, while correcting an erroneous data processing inequality attributed to Erkip and Cover.
- Dependence measures: Maximal correlation is defined through centered, unit-variance functions of X and Y, measuring dependence beyond linear correlation.The admissible functions satisfy zero means and unit second moments.
- Scope and setup: The paper restricts attention to finite-valued discrete random variables with strictly positive marginal probabilities.
- Hypercontractivity: The hypercontractivity function q∗X;Y(p) is defined as the smallest q satisfying ||E[g(Y)|X]||p ≤ ||g(Y)||q for every real-valued g.
- Known properties: For fixed p > 1, q∗X;Y(p) is at least 1, with equality exactly when X and Y are independent, and it decreases monotonically with p.
- Paper contributions: The paper introduces geometric characterizations of maximal correlation and s∗, then identifies the claimed Erkip–Cover inequality as incorrect and promises a counterexample with a tight replacement constant.The geometric framework uses entropy-based functions and their convexity properties.
A. Alternate characterizations of the Hirschfeld-Gebelein-R´enyi maximal correlation
This section reviews alternate characterizations of Hirschfeld-Gebelein-Rényi maximal correlation established in prior work.
- The paper introduces the section as a review of known alternate characterizations of maximal correlation.
1) R´enyi’s characterization:
Rényi’s characterization reduces maximal correlation to optimizing conditional expectations over one function. The paper also uses this characterization to establish a Markov-chain identity.
- Rényi’s characterization: Rényi’s alternate characterization expresses maximal correlation through a single function of one random variable.
- Rényi’s characterization: Fixing normalized mean-zero f, the maximizing choice is g(Y)=αE[f(X)|Y], with α chosen to normalize its second moment.The proof follows from the Cauchy–Schwarz inequality.
- Rényi’s characterization: If X−Y−X′ is Markov and (X,Y) has the same distribution as (X′,Y), then conditional expectations of f(X) and f(X′) given Y coincide.
- Rényi’s characterization: Under these conditions, E[E[f(X)|Y]^2] equals E[f(X)f(X′)], using the Markov property to factor conditional expectations.
3) Singular value characterization:
The paper reviews the singular-value characterization of maximal correlation and its consequences, including tensorization and applications to distributed decisions and side-information problems.
- Singular value characterization: For finite-valued variables, maximal correlation is the second-largest singular value of the normalized joint-probability matrix Q.
- Singular value characterization: When one variable is binary, the relevant second-largest eigenvalue can be obtained from the trace after subtracting the largest eigenvalue, 1.
- Singular value characterization: Witsenhausen’s theorem states that maximal correlation tensorizes for independent pairs.
- Singular value characterization: For independent pairs, Q is a Kronecker product, so its second-largest singular value is max{ρm(X1;Y1),ρm(X2;Y2)}.
- Singular value characterization: The paper discusses an incorrect data processing inequality claimed by Erkip and Cover for maximal correlation in an investment problem with rate-limited side information.
- Singular value characterization: Maximal correlation has been applied to non-interactive simulation, distributed source and channel coding, and quantum common-randomness distillation.
C. Alternate characterization and properties of q∗X;Y (p)
This section characterizes the hypercontractivity ribbon through norm inequalities and reviews its tensorization properties, including an asymmetric slope parameter and an asymmetric erasure-channel example.
- Hypercontractivity ribbon: The hypercontractivity ribbon consists of exponent pairs satisfying forward or reverse norm inequalities for functions of X and Y.
- Hypercontractivity ribbon: The ribbon characterization is equivalent to an earlier definition through a proof based on Hölder’s inequality.
- Hypercontractivity ribbon: The ribbons R_X;Y and R_Y;X can differ, but they are connected by a duality relationship between the forward and reverse inequalities.
- Hypercontractivity ribbon: The paper gives an alternate proof of slope tensorization using the function tλ(X), convexity of relative entropy, and a supremum over alternative distributions.
- Hypercontractivity ribbon: The slope parameter s∗(X;Y) need not equal s∗(Y;X); one example gives 0.045... versus 0.029....
- Hypercontractivity ribbon: For independent pairs, the full hypercontractivity ribbon tensorizes by intersection, and s∗ tensorizes by taking the maximum of the component slopes.
- Asymmetric erasure channel: Figure 2 depicts the asymmetric erasure channel used in the paper’s example.
II. MAIN RESULTS
The paper corrects Erkip and Cover’s claimed data processing inequality by giving a counterexample, identifying a gap in their proof, and finding the tight replacement constant.
- The paper provides a counterexample to Erkip and Cover’s claimed data processing inequality.
A. Counterexample to the Erkip-Cover data processing inequality
The claimed inequality fails for an asymmetric erasure-channel example: a constructed auxiliary variable yields an information ratio above squared maximal correlation. The paper then locates the proof gap and identifies s∗(X; Y ) as the correct replacement constant.
- The paper constructs a counterexample to Erkip and Cover’s claims and identifies s∗(X; Y ) as the correct replacement for ρ2_m(X; Y ).
- 0.6108... exceeds 0.6 = ρ2_m(X; Y ) for the asymmetric erasure-channel construction.Here I(U; Y ) = 0.055770... and I(U; X) = 0.09130....
- The proof error arises because a Taylor expansion may expand around a zero probability, where the derivative is infinite and the expansion is invalid.
- Related work using Erkip and Cover’s incorrect result is affected, and a similar claim in another work is also false.
B. A geometric characterization of ρ2
The paper characterizes maximal correlation and s∗(X; Y ) geometrically through the function tλ(X)=H(Y)−λH(X): the former is a local curvature threshold, while the latter is a convex-envelope threshold.
- The paper gives geometric interpretations of ρ2_m(X; Y ) and s∗(X; Y ) through the behavior of tλ(X).
- ρ2_m(X; Y ) is the minimum λ for which tλ(X) has a positive semidefinite Hessian at p(x).
- s∗(X; Y ) is the minimum λ for which tλ(X) touches its lower convex envelope at p(x).
- For every Markov chain U−X−Y with I(U; X)>0, the supremum ratio I(U; Y )/I(U; X) equals s∗(X; Y ).
- The quantities ρ2_m(X; Y ) and s∗(X; Y ) are generally asymmetric in the ordered pair (X, Y ).
- The asymmetric erasure-channel plot illustrates that ρ2_m(X; Y ) captures local convexity rather than membership on the convex envelope.
2. The straight
The figure compares the curve p(x) 7→H(Y )−0.6H(X) with the chord joining its endpoint values, illustrating the distinction between local convexity and convex-envelope contact.
- The straight line connects the curve values at P(X = 0)=0 and P(X = 0)=1 rather than representing a tangent at the interior point.
- The figure supports interpreting ρ2_m(X; Y ) as a local-convexity condition, not the condition for lying on the convex envelope.
- For fixed p(y|x), the relevant convexity condition can be expressed through convexity of p(x) 7→H(Y )−λH(X).
C. Alternate proof for the tensorization of s∗(X; Y )
The paper proves tensorization of s*(X;Y) by combining the product-channel entropy decomposition with the lower convex envelope characterization. This yields equality with the larger component value.
- Tensorization: Setting λ := max(s*(X1;Y1), s*(X2;Y2)) reduces the nontrivial direction to proving tλ(X1,X2) = K[tλ](X1,X2) at the product input distribution.Here tλ(X1,X2) denotes H(Y1,Y2) − λH(X1,X2), with the product channel specified by the component channels.
- Tensorization: For any W satisfying W−X1X2−Y1Y2, the key inequality holds for all λ and all p(x1,x2), not only the selected product distribution.This general inequality supplies the convex-envelope comparison needed at the specific λ.
- Tensorization: At the product distribution, tλ(X1,X2) decomposes as tλ(X1)+tλ(X2), and each component equals its lower convex envelope.The resulting chain gives tλ(X1,X2) ≤ K[tλ](X1,X2), completing the reverse inequality for tensorization.
- Tensorization: The product channel satisfies s*(X1X2;Y1Y2) = max{s*(X1;Y1), s*(X2;Y2)}.The easy direction follows directly from the definition, while the proof establishes the reverse inequality.
III. CONCLUSION
The paper develops geometric characterizations of maximal correlation and the hypercontractivity ribbon’s asymptotic chordal slope, then uses them to recover known results and correct a data processing inequality. It also identifies an open direction concerning connections between the associated curve and the full ribbon.
- Contributions: The paper gives a new geometric characterization of maximal correlation ρm(X;Y) for finite-set discrete random variables.The characterization applies to pairs of discrete random variables taking values in finite sets.
- Contributions: It also characterizes the chordal slope s*(X;Y) of the nontrivial hypercontractivity-ribbon boundary at infinity.This is presented as a second geometric characterization for finite-set discrete pairs.
- Contributions: The new characterizations provide simple proofs of some known results about maximal correlation and the chordal slope.
- Contributions: The paper corrects an Erkip–Cover data processing inequality whose error had produced knock-on effects in the literature.
- Open direction: The authors leave open whether further connections exist between the curve tλ(X) and the entire hypercontractivity ribbon as p(x) varies.