A Global Characterization of $f$-Divergences Yielding PSD Mutual-Information Matrices

Technical Summary: A Global Characterization of f-Divergences Yielding PSD Mutual-Information Matrices

Problem Statement
The paper addresses a fundamental question in dependence measures and kernel methods: Given $n$ random variables $X_1, \dots, X_n$, under what conditions does the matrix of pairwise $f$-mutual informations, defined as $M^{(f)}_{ij} := I_f(X_i; X_j)$, constitute a positive semidefinite (PSD) kernel?

While mutual information is widely used in factor analysis, independence testing, and feature extraction, the PSD property of the resulting matrix is not guaranteed for all $f$-divergences. The paper distinguishes this problem from the metric properties of divergences between distributions (e.g., whether $\sqrt{JS}$ is a metric). Instead, it focuses on the PSD nature of the variable-indexed matrix $M^{(f)}$. The authors note that while $\chi^2$-divergence yields PSD matrices, Shannon mutual information (based on $f(t) = t \log t$) fails this requirement for $n \ge 4$, and this indefiniteness can occur even under arbitrarily weak pairwise dependence.

Methodology
The paper employs a combination of probabilistic constructions, functional analysis, and algebraic characterization to derive necessary and sufficient conditions.

1. Linear Transformation Invariance: The authors first establish that $f$-divergences are invariant under the linear transformation $f(t) \mapsto f(t) + c(t-1)$. Consequently, the characterization is performed on the normalized representative $\bar{f}(t)$ where $\bar{f}(1) = \bar{f}'(1) = 0$.
2. Sufficiency via Replica Embedding: To prove that a specific class of functions yields PSD matrices, the authors utilize a "replica embedding." They show that for monomial generators $f_m(t) = (t-1)^m$ with $m \ge 2$, the mutual information matrix can be realized as a Gram matrix of specific functions derived from independent copies (replicas) of the random variables. Since nonnegative mixtures of PSD matrices remain PSD, any function representable as a nonnegative mixture of these monomials is PSD-generating.
3. Necessity via Local Extraction and Global Propagation:
   • Local Extraction: The authors construct a biased latent-variable family (three-point kernels $H_a$) to extract local properties of $f$ at $t=1$. By applying the Belton–Guillot–Khare–Putinar (BGKP) theorem on low-rank Hankel positivity preservers, they demonstrate that if the matrix is PSD, the local Taylor expansion of $f$ at $t=1$ must have nonnegative coefficients for all orders $m \ge 2$.
   • Global Propagation: To extend this local condition to the entire domain $(0, \infty)$, the authors analyze "Bernoulli slices." They show that for Bernoulli variables with covariance $\rho$, the mutual information $H_p(\rho)$ is a linear combination of $f$ evaluated at shifted arguments. Using the fact that global PSD implies local analyticity via shifted BGKP tests, they algebraically solve for $f(t)$ to prove that $f$ must be analytic on $(0, \infty)$.
   • Radius of Convergence: Finally, the Vivanti–Pringsheim theorem is applied. Since the Taylor coefficients are nonnegative, a finite radius of convergence would imply a singularity at the positive boundary. However, the established analyticity on $(0, \infty)$ precludes such a singularity, forcing the radius of convergence to be infinite.

Key Contributions and Results
The main result is Theorem II.1, which provides a complete characterization of PSD-generating $f$-divergences for finite-alphabet families.

Theorem: Let $f: (0, \infty) \to \mathbb{R}$ be convex, finite, with $f(1)=0$ and finite boundary value $f(0)$. The matrix $M^{(f)}_{ij} = I_f(X_i; X_j)$ is PSD for every finite-alphabet family if and only if the normalized representative $\bar{f}(t) = f(t) + c(t-1)$ admits a globally convergent expansion on $(0, \infty)$:
$$\bar{f}(t) = \sum_{m \ge 2} a_m (t-1)^m, \quad \text{with } a_m \ge 0.$$

Implications and Examples:

• Success Cases: The $\chi^2$-divergence ($f(t) = (t-1)^2$) is PSD-generating. More generally, any nonnegative entire mixture of monomials $(t-1)^m$ for $m \ge 2$ (e.g., $f(t) = \cosh(t-1) - 1$) succeeds without requiring a "near-independence" restriction.
• Failure Cases:
  • Shannon Mutual Information: The generator $f(t) = t \log t$ expands to $(t-1) + \frac{1}{2}(t-1)^2 - \frac{1}{6}(t-1)^3 + \dots$. The negative cubic coefficient ($a_3 < 0$) violates the condition, explaining why Shannon MI matrices are not PSD for $n \ge 4$.
  • Jensen–Shannon Divergence: Similarly, its expansion contains a negative cubic term, ruling it out.
  • Non-Analytic Generators: Functions that are convex but non-analytic at $t=1$, such as Total Variation ($f(t) = \frac{1}{2}|t-1|$) or ReLU ($f(t) = (t-1)_+$), are excluded. The paper provides a specific counterexample using four variables where the resulting kernel matrix for Total Variation is indefinite.

Significance
The paper claims to resolve a "kernel characterization problem" distinct from metric properties. It explains the structural reasons behind the success of $\chi^2$-based measures and the failure of Shannon and Jensen–Shannon measures in kernel contexts. The result highlights that PSD generation for variable-indexed matrices is "exceptionally brittle" for information-theoretic dependence measures, requiring global analyticity and nonnegative Taylor coefficients, rather than just local convexity. The authors note that while the result is established for finite alphabets, extensions to continuous models would require additional measure-theoretic hypotheses, but the finite-alphabet obstruction already provides a clear theoretical boundary.