Higher-order Common Information

Technical Summary: Higher-order Common Information

Problem Statement
Characterizing the information shared within a collection of $n$ random variables ($X_1, \dots, X_n$) remains a significant challenge for $n > 2$. While Shannon's mutual information $I(X_1; X_2)$ effectively quantifies pairwise dependence, no single canonical extension exists for higher-order interactions. Existing approaches often rely on pairwise summaries (e.g., the minimum pairwise mutual information), which can be misleading as they do not determine if the same piece of information is present in all variables simultaneously.

Other established notions of common information, such as Wyner's common information ($C_W$) and Gács–Körner common information ($C_{GK}$), have limitations. $C_W$ quantifies the randomness needed to simulate a joint distribution via a latent variable, often yielding values larger than mutual information. $C_{GK}$ captures only deterministic common parts, which can be zero even when variables are statistically dependent. Furthermore, many existing measures for continuous variables (like entropy-based common randomness) can diverge, and Partial Information Decomposition (PID) measures often require an external target variable or restrictive model assumptions (e.g., joint Gaussianity). There is a need for a measure that captures intrinsic, shared structure among $n$ variables without reference to an external target, is locally present in each variable, and remains meaningful for both discrete and continuous distributions.

Methodology
The paper introduces Higher-order Common Information (HCI), denoted as $R(X_1, \dots, X_n)$. The core methodology is an iterative information-bottleneck construction based on nested Markov constraints.

1. Iterative Construction: The definition begins by fixing a reference variable $X_i$ and an ordering of the remaining variables. An auxiliary variable $T$ is constructed through a sequence of stages. At each stage $\ell$, a new auxiliary $T_{\ell+1}$ is derived from the previous one $T_\ell$ such that:

   • Markov Constraint: $T_{\ell+1} - T_\ell - X$ holds (where $X$ is the set of all variables).
   • Information-Matching Constraint: The mutual information is preserved between the current auxiliary and the next variable in the sequence: $I(T_{\ell+1}; T_\ell) = I(T_\ell; X_{\pi(\ell)})$.
   • Optimization: The construction minimizes the mutual information between the new auxiliary and the entire set of variables $X$, effectively stripping away private information while retaining shared information.

2. Definition of HCI: The final HCI is defined by minimizing over all possible reference variables $X_i$ and supremizing over all permutations of the remaining variables and all valid terminal auxiliaries. Formally:
   $$R(X_1, \dots, X_n) \triangleq \min_i \sup_{T \in \mathcal{T}_i(X)} \min_j I(T; X_j)$$
   This ensures the measure is invariant to the choice of reference and captures the maximum rate at which a single compressed representation can simultaneously preserve information about all variables.

3. Approximation for General Sources: For arbitrary distributions where closed-form solutions are unavailable, the paper proposes a practical numerical procedure. This involves constructing degraded auxiliary variables by adding noise (e.g., Gaussian noise) to satisfy the information-matching constraints empirically. This yields a computable lower bound on the HCI.

Key Contributions and Results

• Closed-Form Expressions:

  • Gaussian Sources: For jointly Gaussian variables with correlation coefficients $\rho_{jk}$, the paper derives a closed-form expression involving the order statistics of the absolute correlations. Specifically, for a reference $i$, the HCI depends on the product of the smallest correlations in the set.
  • Bernoulli Sources: For binary sources generated by a common source $U$ corrupted by independent noise ($X_j = U \oplus N_j$), a closed-form expression is derived. Notably, for these sources, the Gács–Körner common information is zero, whereas the proposed HCI is strictly positive for all finite $n$, demonstrating its ability to capture statistical (non-deterministic) shared structure.
  • General Discrete Sources: For variables constructed from independent components, the HCI is shown to equal the entropy of the intersection of the component sets.

• Theoretical Properties:

  • Bounds: The paper establishes that $R(X_1, \dots, X_n) \leq I(X_i; X_j) \leq C_W(X_1, \dots, X_n)$ and $R(X_1, \dots, X_n) \leq DTC(X_1, \dots, X_n) \leq TC(X_1, \dots, X_n)$.
  • Consistency: For $n=2$, $R(X_1, X_2)$ reduces exactly to the standard mutual information $I(X_1; X_2)$.
  • Non-increasing: Adding more variables to the set cannot increase the HCI; $R(X_1, \dots, X_n) \leq R(X_1, \dots, X_{n-1})$.
  • Vanishing: If any pair of variables is independent, the HCI vanishes.

• Empirical Application (EEG Data):
  The authors applied the numerical approximation method to a real-world dataset involving 64-channel scalp EEG recordings during an auditory attention task. They analyzed the relationship between EEG signals (from temporal electrodes) and the envelopes of target and distractor speech streams.

  • Findings: The study demonstrated that the third-order common information ($R_3$) contains significant information about neural speech tracking responses that is not explained by the minimum of the pairwise mutual informations ($R_2$).
  • Statistical Significance: Regression analyses showed that $R_3$ explained significant variance in neural tracking responses beyond what was captured by $R_2$, confirming the presence of higher-order dependencies in the neural response to speech.

Significance
The paper claims that HCI provides a fundamentally local measure of shared structure that is intrinsic to the collection of variables, distinct from approaches relying on external targets or latent variable simulation. By strictly tightening the characterization of redundancy compared to existing bounds (specifically being strictly lower than pairwise mutual information and Wyner's common information in many cases), HCI reveals shared structure that existing measures miss. The ability to derive closed-form solutions for Gaussian and Bernoulli sources, combined with a practical estimation procedure for general data, offers a new tool for uncovering inherent multivariate dependencies in complex systems, as demonstrated by the analysis of neural data.