The Gray-Wyner Network

Note

We use \(p\) to denote fixed probability distributions, and \(q\) to denote probability distributions that are optimized.

The Gray-Wyner network [GW74] is a simple source-coding network with one encoder and \(n\) decoders. The encoder observes a correlated source vector \((X_1, \dots, X_n) \sim p\) and emits one common message at rate \(R_0\), delivered to every decoder, together with \(n\) private messages, where message \(i\) (at rate \(R_i\)) is delivered only to decoder \(i\). Decoder \(i\) reconstructs \(X_i\) to within an average distortion \(D_i\).

The achievable rate region (lossless: [GW74]; lossy: [VAR14]) is the set of rate tuples \((R_0, R_1, \dots, R_n)\) for which there exists an auxiliary random variable \(W\) satisfying

\[\begin{split}R_0 &\ge \I{X_1, \dots, X_n : W} \\ R_i &\ge R_{X_i \mid W}(D_i) \qquad i = 1, \dots, n\end{split}\]

where \(R_{X_i \mid W}(D_i)\) is the conditional rate-distortion function of \(X_i\) given \(W\). In the lossless case (\(D_i = 0\) under a Hamming distortion) this reduces to \(R_i \ge \H{X_i \mid W}\).

The region is convex, so its lower boundary is traced by minimizing a weighted sum of rates over \(W\) (and, in the lossy case, the reconstruction test channels subject to the distortion budgets):

\[\min_{W} \quad \lambda_0 \I{X_{1:n} : W} + \sum_{i} \lambda_i R_{X_i \mid W}(D_i) ~.\]

Sweeping the weights \((\lambda_0, \dots, \lambda_n)\) sweeps the Pareto surface.

Common informations as operating points

Several of the common informations are particular operating points of the lossless Gray-Wyner region:

GrayWynerNetwork.corner_points returns these values by delegating to their canonical implementations.

Lossy common information

Generalizing the minimum-sum-rate operating point to positive distortion gives the lossy common information \(C(D_1, \dots, D_n)\) [VAR14], available as lossy_wyner_common_information(). For \(D_i = 0\) it coincides with Wyner’s common information.

Other coordinates on the same region

Several bodies studied independently in the literature turn out to be the lossless Gray-Wyner region written in different coordinates. Each records a different set of affine functions of the entropies of \((X_{0:n}, W)\), but all are generated by the same auxiliary variable.

\[\begin{split}\tau_i &= R_0 + R_i - \H{X_i} &&= \I{X_{-i} : W \mid X_i} \\ \tau_{res} &= R_0 + \sum_i R_i - \H{X_{0:n}} &&= \T{X_{0:n} \mid W} \\ v_i &= \H{X_i} - R_i &&= \I{X_i : W} \\ v_{joint} &= R_0 &&= \I{X_{0:n} : W}\end{split}\]

The first two identities are the chain rule and the definition of the conditional total correlation. The matrix carrying \((R_0, \dots, R_n)\) to \((\tau_0, \dots, \tau_{n-1}, \tau_{res})\) is unimodular, so nothing is lost in either direction.

Body

Coordinates

View

Gray-Wyner region

\((R_0, R_1, \dots, R_n)\)

.region()

Region of tension

\((\tau_0, \dots, \tau_{res})\)

.tension_region()

Extension profile

\((R_1, \dots, R_n, \tau_{res})\)

.extension_profile()

Mutual information

\((v_1, \dots, v_n, v_{joint})\)

.mutual_information_region()

The region of tension is due to Prabhakaran & Prabhakaran [PP14]; at \(n = 2\) the residual coordinate is \(\I{X : Y \mid W}\) and the map is their \(g_{X,Y}\). The extension profile is due to Matveev & Romashchenko [MR26a], and the mutual information region to Li & El Gamal [LEG18a].

Warning

dit follows the coordinate ordering of [PP14] and [LEG18a], in which coordinate \(i\) is \(\I{X_{-i} : W \mid X_i}\) — so for a pair, \((\I{Y : W \mid X}, \I{X : W \mid Y}, \I{X : Y \mid W})\). Csirmaz [Csi23] swaps the first two coordinates and omits the increasing hull, correspondingly using a cardinality bound of \(|X||Y| + 3\) where dit uses the Fenchel-Eggleston \(|X||Y| + 2\).

The region of tension proper is the increasing hull of the attainable points; the samplers report attainable points on its lower boundary. Its axis intercepts, .tension_intercepts(), are the \(T_i\) of [PP14]; the residual intercept satisfies \(T_{res} = \I{X : Y} - \K{X : Y}\).

The shape function

The support function of the extension profile is the shape function [MR26a]:

\[S(\alpha) = \sup_W \left( \sum_i \alpha_i \H{X_i \mid W} - \T{X_{0:n} \mid W} \right) = \H{X_{0:n}} - \min_W \left( R_0 + \sum_i (1 - \alpha_i) R_i \right)\]

so it too is a weighted rate query, with weights \((1, 1 - \alpha_1, \dots, 1 - \alpha_n)\). Those are non-negative exactly on the unit cube, which is where the shape function is studied.

Two envelopes depend only on the entropy profile. Evaluating at the deterministic probes \(W \in \{X_{0:n}, X_{-j}, \cdot\}\) gives the lower one, and convexity together with \(S(0) = 0\) and \(S(e_j) = \H{X_j \mid X_{-j}}\) gives the upper one:

\[\begin{split}S_{\min}(\alpha) &= \max\left\{ 0,\ \max_j \alpha_j \H{X_j \mid X_{-j}},\ \sum_i \alpha_i \H{X_i} - \T{X_{0:n}} \right\} \\ S_{\max}(\alpha) &= \max\left\{ \sum_j \alpha_j \H{X_j \mid X_{-j}},\ \sum_i \alpha_i \H{X_i} - \T{X_{0:n}} \right\}\end{split}\]

A pair attaining the lower envelope everywhere is rigid; one attaining the upper envelope has Gács-Körner extractable mutual information. ShapeFunction.rigidity() reports where a given pair sits between them.

For a pair, the Tension Common Information and the entanglement are read off the same region. For three or more sources they measure leftover dependence with the dual total correlation rather than the residual coordinate \(\tau_{res} = \T{X_{0:n} \mid W}\), so they are no longer a query on this region; see that page.

Note

Only the total-correlation residual is affine in the Gray-Wyner rates. Dual-total-correlation and CAEKL variants of the residual coincide with it at \(n = 2\) but would need their own optimizer for \(n \ge 3\), and are not implemented.

Extreme points of the mutual information region

Li & El Gamal [LEG18a] identify three quantities as extreme points of the mutual information region, each a maximization of the interaction information \(\I{X : Y \mid U} - \I{X : Y}\) under a different independence constraint:

\[\begin{split}\Gnni{X : Y} &= \max_{U} \I{X : Y \mid U} - \I{X : Y} \\ \Gpni{X \to Y} &= \max_{U \ind X} \I{X : Y \mid U} - \I{X : Y} \\ \Gppi{X : Y} &= \max_{U \ind X,\, U \ind Y} \I{X : Y \mid U} - \I{X : Y}\end{split}\]

They satisfy \(0 \le \Gppi{X : Y} \le \Gpni{X \to Y} \le \Gnni{X : Y} \le \min\{\H{X \mid Y}, \H{Y \mid X}\}\). The maximal interaction information vanishes exactly when the support graph contains no path of length three; the symmetric private interaction information vanishes exactly when the support graph is acyclic.

Because these maximize rates, they need signed weights, which GrayWynerOptimizer accepts via allow_signed=True. Signed weights optimize over the raw attainable point set rather than the upward-closed region, over which such a sum would be unbounded.

Note

Unlike the region of tension, which tensorizes exactly, the mutual information region is only superadditive [LEG18a].

Drawing the extension profile

For a pair, the extension profile [MR26a]

\[\mathrm{Ext}(X, Y) = \{(\H{X \mid W},\ \H{Y \mid W},\ \I{X : Y \mid W})\}\]

is a compact convex body. The Gray-Wyner region is its image under \((R_0, R_1, R_2) = (\H{XY} - x - y + z,\ x,\ y)\) together with everything above it, so ExtensionProfile places every operating point on one picture. Under that map the Pangloss plane \(R_0 + R_1 + R_2 = \H{XY}\) is exactly the bottom face \(z = 0\). Only directions \((\alpha, \beta, -1)\) with \(\alpha, \beta \le 1\) (non-negative rate weights) reach the boundary of the Gray-Wyner region; the rest of the body carries points that only the mutual information region [LEG18a] sees. ExtensionProfile computes:

  • the lower boundary, sampled over every downward direction written as \(\alpha + i\beta = r e^{i\theta}\), continuing each optimum along \(r\) and relaxing every grid point against its neighbours, with the bottom face snapped to \(z = 0\); and the upper boundary over upward directions;

  • the bounds \(\mathrm{Ext}_{\min}\) (the hull of \(W = XY, X, Y,\) const) and the Shannon outer bound \(\mathrm{Ext}_{\max}\) [MR26a];

  • realizer points of the Gács-Körner [GacsKorner73], Wyner [Wyn75], exact [KLEG14], functional and MSS [JC17] common informations, the Kamath edges [KA10] (whose far ends are the necessary-conditional-entropy points [CPC10]), and the entanglement [MMRV02];

  • the relaxed-Wyner [GS19] and \(\beta\)-common [YLC17] curves, and the information-bottleneck [TPB00] and privacy-funnel [MSFMedard14] arcs of the two zero-leakage faces;

  • the communication rate for distributed channel synthesis with common-randomness rate \(t\) [Cuf13], \(C(t, X \to Y) = \min_{X - U - Y} \max\{\I{X : U},\ \I{XY : U} - t\}\), whose optimal \(U\) runs along the bottom-face rim from the Wyner point to the Kamath point (hover shows the common randomness \(\I{Y : U \mid X}\) used and the decoder’s local randomness \(\H{Y \mid U}\)), and its public-channel counterpart \(C_{pub}(t, X \to Y) = \min_{X - U - Y,\ \I{XY : U} \le t} \I{X : U}\), which runs from the Wyner point (\(t = \C{X : Y}\)) to \(U = Y\) (\(t = \H{Y}\)). For the exact rate at a single \(t\), see Channel Synthesis;

  • the points invisible to the Gray-Wyner region [LEG18a]: the excess functional information [LEG18b] (excess_functional_information(), exact by a linear program over random functions \(f : \mathcal{X} \to \mathcal{Y}\)), Körner’s graph entropy [Korner73] (korner_graph_entropy()), the maximum rate for perfect privacy [RGunduz21] (the end of the privacy-funnel arc), and the three interaction informations, drawn as separate points; the asymmetric private one is the far end of the edge \(\{x = \H{X},\ z = y\}\) whose near end is the excess-functional-information corner.

ExtensionProfile.plot (or plot_extension_profile()) draws all of it as an interactive Plotly figure: drag to rotate, scroll to zoom, toggle features from the legend, and hover for coordinates and Gray-Wyner rates. Plotly is an optional dependency (pip install 'dit[optional]').

The same features can be drawn in two other coordinate systems. ExtensionProfile.plot_mutual_information_region (or plot_mutual_information_region()) draws the mutual information region \(\{(\I{X : W}, \I{Y : W}, \I{XY : W})\}\) [LEG18a]. It is the invertible affine image \((\H{X} - x,\ \H{Y} - y,\ \H{XY} - x - y + z)\) of the extension profile, so it carries exactly the same information. ExtensionProfile.plot_tension_region (or plot_tension_region()) draws the region of tension \(\{(\I{Y : W \mid X}, \I{X : W \mid Y}, \I{X : Y \mid W})\}\) plus the positive orthant [PP14]. Its axis intercepts are the necessary conditional entropies \(\H{Y \dagger X}\) and \(\H{X \dagger Y}\), and the Gács-Körner gap \(\I{X : Y} - \K{X : Y}\). Like the Gray-Wyner region, it sees only part of the shape function: directions with \(\alpha, \beta \geq 0\) and \(\alpha + \beta \leq 1\).

Note

Every plotted point is attained by an explicit \(W\), so the drawn hull is an inner approximation. The boundary searches are non-convex. The excess functional information and Körner graph entropy are exact. Both first apply exact reductions: for \(\Psi\), splitting on the Gács-Körner common part and reducing each variable to its minimal sufficient statistic about the other; for \(H_K\), merging twins and recursing through disjoint unions and joins of the characteristic graph. They then enumerate the \(|\mathcal{Y}|^{|\mathcal{X}|}\) functions of each reduced block, or the maximal independent sets of each prime graph, and return None when those are still too many.

Spectral diagnostics

For a distribution uniform on a biregular support, the singular values of the 0/1 biadjacency matrix of the support graph recover part of the entropy profile exactly [MR26b]:

\[\log \lambda_1 = \H{XY} - \tfrac{1}{2}\left( \H{X} + \H{Y} \right), \qquad \frac{\lambda_2}{\lambda_1} = \rho_m(X : Y)\]

where \(\rho_m\) is the maximal correlation. Both identities fail off biregular supports. These are available as support_singular_values().

The spectral gap bounds the entanglement of a uniform pair from below by \(\min\{\I{X : Y},\ 2\log(\lambda_1/\lambda_2)\} - O(\log \H{XY})\), which is what certifies that expander-like supports are maximally non-extractable. spectral_entanglement_bound() returns the nominal term only.

Warning

The suppressed slop is not a formality. The uniform distribution on an 8-cycle has an entanglement of about \(0.67\) bits against a nominal bound of \(1.00\). Use the nominal term to compare pairs or to reason asymptotically, never as a pointwise certificate.

Example

The trade-off between the common rate and the total private rate is traced by GrayWynerCurve:

In [1]: from dit.rate_distortion import GrayWynerCurve

In [2]: d = dit.Distribution(['00', '01', '10', '11'], [0.4, 0.1, 0.1, 0.4])

In [3]: GrayWynerCurve(d, s_num=21).plot();

The named corner points and the lossy common information:

In [4]: from dit.rate_distortion import GrayWynerNetwork, lossy_wyner_common_information

In [5]: from dit.rate_distortion.gray_wyner import hamming_matrix

In [6]: GrayWynerNetwork(d).corner_points()

In [7]: dm = [hamming_matrix(2), hamming_matrix(2)]

In [8]: lossy_wyner_common_information(d, bounds=[0.1, 0.1], distortions=dm)

The tension region and the shape function:

In [9]: from dit.rate_distortion import ShapeFunction

In [10]: GrayWynerNetwork(d).tension_intercepts()

In [11]: ShapeFunction(d, num=21).rigidity()

In [12]: ShapeFunction(d, num=21).plot();

The extension profile, with every distinguished point:

In [13]: from dit.rate_distortion import ExtensionProfile

In [14]: ep = ExtensionProfile(d, seed=0)

In [15]: features = ep.compute()

In [16]: ep.excess_functional_information, ep.korner

In [17]: ep.plot(features).show()

APIs

class GrayWynerNetwork(dist, rvs=None, crvs=None, distortions=None, bounds=None, bound=None)[source]

The generalized Gray-Wyner network for a source distribution.

Parameters:

  • dist (Distribution) – The source distribution.

  • rvs (list of lists, None) – The source groups X_1, ..., X_n. If None, each variable of dist is its own source.

  • crvs (list, None) – Variables to condition the network on. If None, none.

  • distortions (list, None) – Per-decoder distortion matrices, or None entries for lossless decoders. If None, every decoder is lossless.

  • bounds (list, None) – Per-decoder distortion budgets D_i. If None, all zero (lossless).

  • bound (int, None) – Optional cap on the cardinality of the common auxiliary W.

rate_point(lambdas, niter=None, maxiter=1000, polish=1e-06, rng=None, **kwargs)[source]

Compute the Gray-Wyner rate point supporting a weight vector.

Parameters:

  • lambdas (iterable of float) – The weights (lambda_0, lambda_1, ..., lambda_n).

  • niter (int, None) – Number of basin hops.

  • maxiter (int) – Inner optimizer iterations.

  • polish (float) – Polishing cutoff; if falsey, no polishing.

  • kwargs (dict) – Additional keyword arguments for GrayWynerOptimizer, such as allow_signed or rate_equalities.

Returns:

point – The supporting (common, private) rate point.

Return type:

GrayWynerPoint

region(num=20, niter=None, maxiter=1000, seed=None)[source]

Sample the lower boundary of the achievable rate region.

Weight vectors are drawn on the (n + 1)-simplex (the vertices, plus random Dirichlet samples) and the supporting rate point of each is computed.

Parameters:

  • num (int) – The number of random weight vectors to sample (in addition to the n + 1 simplex vertices).

  • niter (int, None) – Number of basin hops per point.

  • maxiter (int) – Inner optimizer iterations.

  • seed (int, None) – Seed for the random weight sampler.

Returns:

points – The sampled boundary points.

Return type:

list of GrayWynerPoint

tension_point(lambdas, **kwargs)[source]

Compute a point of the region of tension supporting a weight vector.

Parameters:

  • lambdas (iterable of float) – The Gray-Wyner weights (lambda_0, lambda_1, ..., lambda_n).

  • kwargs (dict) – Additional keyword arguments for rate_point().

Returns:

point – The supporting point, in tension coordinates.

Return type:

TensionPoint

tension_region(num=20, niter=None, maxiter=1000, seed=None)[source]

Sample the lower boundary of the region of tension.

The region proper is the increasing hull of the attainable tension points [PP14]; the points returned here are attainable ones on its lower boundary.

Parameters:

  • num (int) – The number of random weight vectors to sample, in addition to the n + 1 simplex vertices.

  • niter (int, None) – Number of basin hops per point.

  • maxiter (int) – Inner optimizer iterations.

  • seed (int, None) – Seed for the random weight sampler.

Returns:

points – The sampled boundary points.

Return type:

list of TensionPoint

extension_profile(num=20, niter=None, maxiter=1000, seed=None)[source]

Sample the lower boundary of the extension profile.

The extension profile [MR26a] records (H[X_i | W], ..., T[X_{0:n} | W]); for a pair this is the (H[X|W], H[Y|W], I[X:Y|W]) body of that reference.

Parameters:

  • num (int) – The number of random weight vectors to sample, in addition to the n + 1 simplex vertices.

  • niter (int, None) – Number of basin hops per point.

  • maxiter (int) – Inner optimizer iterations.

  • seed (int, None) – Seed for the random weight sampler.

Returns:

points – The sampled boundary points.

Return type:

list of ExtensionPoint

mutual_information_region(num=20, niter=None, maxiter=1000, seed=None)[source]

Sample the lower boundary of the mutual information region.

The mutual information region [LEG18a] records (I[X_i : W], ..., I[X_{0:n} : W]). Unlike the region of tension, which tensorizes exactly, this region is only superadditive.

Parameters:

  • num (int) – The number of random weight vectors to sample, in addition to the n + 1 simplex vertices.

  • niter (int, None) – Number of basin hops per point.

  • maxiter (int) – Inner optimizer iterations.

  • seed (int, None) – Seed for the random weight sampler.

Returns:

points – The sampled boundary points.

Return type:

list of MutualInformationPoint

tension_intercepts(niter=None, maxiter=1000)[source]

The axis intercepts of the region of tension.

These are the T_i of [PP14] (their equation 1): the smallest value each coordinate can take when every other coordinate is zero. They are constrained optima rather than supporting-hyperplane queries.

The residual intercept satisfies T_res = I[X:Y] - K[X:Y], which is the Gacs-Korner corollary of [PP14] (their Corollary 3.3); the source intercepts are the Wolf-Wullschleger monotones.

Parameters:

  • niter (int, None) – Number of basin hops per intercept.

  • maxiter (int) – Inner optimizer iterations.

Returns:

intercepts – Mapping from coordinate (source index, or 'residual') to the intercept value.

Return type:

dict

corner_points(niter=None, maxiter=1000)[source]

The named common-information operating points of the network.

For a lossless network the corners are the standard common informations, computed by delegating to their canonical implementations so the values stay consistent across dit. The returned values are the common-rate (R_0) coordinates of those operating points.

Parameters:

  • niter (int, None) – Number of basin hops (forwarded to the optimization-based measures).

  • maxiter (int) – Inner optimizer iterations (forwarded likewise).

Returns:

corners – A mapping from measure name to its R_0 value.

Return type:

dict

class GrayWynerCurve(dist, rvs=None, crvs=None, distortions=None, bounds=None, s_min=0.0, s_max=4.0, s_num=21, niter=None, maxiter=1000, bound=None)[source]

Compute the common-rate vs total-private-rate trade-off curve.

class ShapeFunction(dist, rvs=None, crvs=None, alphas=None, num=11, niter=None, maxiter=1000, bound=None)[source]

The shape function of a tuple of random variables.

alphas

The sampled directions, shape (num_points, n).

Type:

np.ndarray

values

The shape function at each direction.

Type:

np.ndarray

minima, maxima

The S_min and S_max envelopes at each direction.

Type:

np.ndarray

minimum(alpha)[source]

The S_min envelope, which depends only on the entropy profile.

Parameters:

alpha (array-like) – A direction, or an array of directions with n columns.

Returns:

value – The lower bound at each direction.

Return type:

np.ndarray

maximum(alpha)[source]

The S_max envelope, which depends only on the entropy profile.

Parameters:

alpha (array-like) – A direction, or an array of directions with n columns.

Returns:

value – The upper bound at each direction.

Return type:

np.ndarray

evaluate(alpha, niter=None, maxiter=1000, rng=None)[source]

Evaluate the shape function in a single direction.

Parameters:

  • alpha (array-like) – A direction with n entries, each in [0, 1].

  • niter (int, None) – Number of basin hops.

  • maxiter (int) – Inner optimizer iterations.

Returns:

value – The shape function in that direction.

Return type:

float

compute(niter=None, maxiter=1000)[source]

Evaluate the shape function at every sampled direction.

Parameters:

  • niter (int, None) – Number of basin hops per direction.

  • maxiter (int) – Inner optimizer iterations.

rigidity(tol=0.001)[source]

Where the shape function sits between its two envelopes.

A fraction of zero at every direction means the pair is rigid: its extension profile is as small as the entropy profile permits. A fraction of one means the mutual information is Gacs-Korner extractable.

Parameters:

tol (float) – Directions where S_max - S_min is below this are Shannon-forced and are excluded from the summary.

Returns:

summary – The min, mean, and max of the normalized position, plus booleans reporting rigidity and maximality.

Return type:

dict

plot()[source]

Plot the shape function.

Returns:

fig – The resulting figure.

Return type:

plt.Figure

class ExtensionProfile(dist, rvs=None, bound=None, seed=None)[source]

The extension profile of a pair and its distinguished points.

The lower boundary is sampled over every downward direction \((\alpha, \beta, -1)\), written as \(\alpha + i\beta = r e^{i\theta}\); for each \(\theta\) the optimum is continued along \(r\) (from \(r \to 0\), the rim of the bottom face \(I[X:Y|W] = 0\), to \(r \to \infty\), the silhouette), then every grid point is re-solved from its neighbours until none improves. Points with negligible \(I[X:Y|W]\) are snapped to the bottom face. The upper boundary is sampled over upward directions. All of these are attained points, so their hull is an inner approximation of the body.

Parameters:

  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two variables [X, Y]. If None, the two variables of dist.

  • bound (int, None) – Cardinality of the auxiliary W in the boundary optimizations. If None, min(support + 2, 8).

  • seed (int, None) – Seed for the optimizers’ random starts.

support_point(direction, starts=8)[source]

A point of the extension profile maximizing direction . (x, y, z).

Parameters:

  • direction (array-like) – The direction (any length; it need not be normalized).

  • starts (int) – Number of random starts.

Returns:

point – The supporting point (H[X|W], H[Y|W], I[X:Y|W]).

Return type:

np.ndarray

lower_boundary(num_theta=48, num_radii=33, r_min=1e-05, r_max=1000.0, max_passes=6)[source]

Sample the lower (downward-facing) boundary.

Parameters:

  • num_theta (int) – Number of angles round the circle.

  • num_radii (int) – Number of radii, geometrically spaced in [r_min, r_max].

  • r_min (float) – The radial range; small radii resolve the bottom-face rim.

  • r_max (float) – The radial range; small radii resolve the bottom-face rim.

  • max_passes (int) – Maximum neighbour-relaxation passes.

Returns:

points – Shape (num_theta, num_radii, 3).

Return type:

np.ndarray

upper_boundary(num=300, starts=4)[source]

Sample the upper (upward-facing) boundary in num directions.

Returns:

points – Shape (m, 3).

Return type:

np.ndarray

wyner(niter=None)[source]

The Wyner point [Wyn75], the realizer of the Wyner common information.

exact(niter=None)[source]

The point of a realizer of the exact common information [KLEG14].

relaxed_wyner(num=25)[source]

The relaxed-Wyner curve [GS19]: the diagonal alpha = beta in (0, 1/2].

beta_common(betas=None, niter=None)[source]

Realizer points of the beta-common information [YLC17] for each beta.

information_bottleneck(num=60)[source]

Both information-bottleneck arcs [LEG18a, TPB00]: the lower arcs of the zero-leakage faces x - z = H[X|Y] (U generated from Y) and its mirror, from W = const to the Kamath point.

Returns:

arcs – [X -> Y, Y -> X].

Return type:

list of np.ndarray

privacy_funnel(num=60)[source]

Both privacy-funnel arcs [LEG18a, MSFMedard14]: the upper arcs of the zero-leakage faces, from W = Y (or X) to perfect privacy.

Returns:

arcs – [X -> Y, Y -> X].

Return type:

list of np.ndarray

public_channel_synthesis(lower, num=45)[source]

The communication rate for distributed channel synthesis over a public channel with common-randomness rate t [Cuf13],

\[C_{pub}(t, X \to Y) = \min_{X - U - Y,\ I[XY:U] \le t} I[X:U].\]

The public message must look independent of the synthesized pair, so the common randomness must cover all of \(I[XY:U]\): the curve starts at the Wyner point, t equal to the Wyner common information, and reaches C = I[X:Y] at U = Y, where t = H[Y]. In the mutual information region it is the lower edge of the bottom face’s projection onto the \((I[X:U], I[XY:U])\) plane.

Parameters:

  • lower (np.ndarray) – Lower-boundary points (from lower_boundary); their z = 0 subset gives the rim.

  • num (int) – Number of values of t.

Returns:

  • ts (np.ndarray) – The common-randomness rates.

  • curves (list of (np.ndarray, np.ndarray)) – [(values, points) for X -> Y, (values, points) for Y -> X].

channel_synthesis(lower, num=45)[source]

The communication rate for distributed channel synthesis with common-randomness rate t [Cuf13, LEG18a],

\[C(t, X \to Y) = \min_{X - U - Y} \max\{I[X:U],\ I[XY:U] - t\},\]

a minimization over the bottom face of the extension profile. Its optimal U runs along the bottom-face rim from the Wyner point (t = 0) towards the Kamath point, where C(t) = I[X:Y]. This interpolates the rim for plotting; for the rate at a single t, optimized directly, use dit.multivariate.channel_synthesis_rate.

In region-of-tension coordinates, \(I[X:U] = I[X:Y] + \tau_2\) and the common randomness used at a corner point is \(I[Y:U|X] = \tau_1\), so \(C(t) = I[X:Y] + \min_{\tau_3 = 0} \{\tau_2 + (\tau_1 - t)^+\}\). The decoder needs local randomness \(H[Y|U]\), the extension-profile y coordinate.

Parameters:

  • lower (np.ndarray) – Lower-boundary points (from lower_boundary); their z = 0 subset gives the rim.

  • num (int) – Number of values of t, from 0 to a little past the rate at which C(t) = I[X:Y] (the necessary conditional entropy).

Returns:

  • ts (np.ndarray) – The common-randomness rates.

  • curves (list of (np.ndarray, np.ndarray)) – [(values, points) for X -> Y, (values, points) for Y -> X].

compute(lower=None, upper=None, curves=None, slow=True, niter=None)[source]

Compute the boundary and every distinguished point.

Parameters:

  • lower (dict, None) – Keyword arguments for lower_boundary, upper_boundary and the arc methods (num).

  • upper (dict, None) – Keyword arguments for lower_boundary, upper_boundary and the arc methods (num).

  • curves (dict, None) – Keyword arguments for lower_boundary, upper_boundary and the arc methods (num).

  • slow (bool) – Whether to run the non-convex realizer optimizations (Wyner, exact, beta).

  • niter (int, None) – Basin hops for those optimizations.

Returns:

features – Everything plot_extension_profile draws.

Return type:

dict

plot(features=None, **kwargs)[source]

Draw the extension profile with Plotly. See plot_extension_profile.

Parameters:

  • features (dict, None) – Output of compute. If None, it is computed with defaults.

  • kwargs (dict) – Passed to plot_extension_profile.

Returns:

fig – The interactive figure.

Return type:

plotly.graph_objects.Figure

plot_mutual_information_region(features=None, **kwargs)[source]

Draw the mutual information region [LEG18a] with Plotly. See plot_mutual_information_region.

plot_tension_region(features=None, **kwargs)[source]

Draw the region of tension [PP14] with Plotly. See plot_tension_region.

plot_extension_profile(profile, features, show_upper=True, show_gray_wyner_rates=True, height=850)[source]

Draw an extension profile [MR26a] and its distinguished points.

The lower boundary is shaded by height (it includes the flat bottom face \(I[X:Y|W] = 0\)); the upper boundary, the inner bound \(\mathrm{Ext}_{\min}\) and the Shannon outer bound \(\mathrm{Ext}_{\max}\) are drawn for context. Every feature is a legend entry that can be toggled, and hovering shows its coordinates and, optionally, its Gray-Wyner rates \((R_0, R_1, R_2) = (I[XY:W], H[X|W], H[Y|W])\) [GW74].

Parameters:

  • profile (ExtensionProfile) – The profile (for its entropies).

  • features (dict) – The output of ExtensionProfile.compute.

  • show_upper (bool) – Whether to draw the sampled upper boundary.

  • show_gray_wyner_rates (bool) – Whether hover text includes the Gray-Wyner rates.

  • height (int) – Figure height in pixels.

Returns:

fig – The interactive figure.

Return type:

plotly.graph_objects.Figure

plot_mutual_information_region(profile, features, show_upper=True, height=850)[source]

Draw the mutual information region of [LEG18a],

\[\mathscr{I}_{XY} = \{(I[X:U],\ I[Y:U],\ I[XY:U])\},\]

with every distinguished point. It is the extension profile under the invertible affine map \((H[X] - x,\ H[Y] - y,\ H[XY] - x - y + z)\), so every trace of plot_extension_profile is mapped across. The planes \(v_X + v_Y - v_{XY} = I[X:Y]\) (the image of the bottom face), \(v_Y = v_{XY}\) (\(X - Y - U\)) and \(v_X = v_{XY}\) (\(Y - X - U\)) can be toggled from the legend.

Parameters:

  • profile (ExtensionProfile) – The profile.

  • features (dict) – The output of ExtensionProfile.compute.

  • show_upper (bool) – Whether to draw the image of the sampled upper boundary.

  • height (int) – Figure height in pixels.

Returns:

fig – The interactive figure.

Return type:

plotly.graph_objects.Figure

plot_tension_region(profile, features, height=850)[source]

Draw the region of tension of [PP14], in the coordinates \(\tau = (I[Y:W|X],\ I[X:W|Y],\ I[X:Y|W])\) (the two leakages and the residual), i.e. \((H[Y|X] - y + z,\ H[X|Y] - x + z,\ z)\) in extension-profile coordinates.

The region is the image of the extension profile plus everything above it in \(\tau\)-space, so only directions \(\alpha, \beta \ge 0\), \(\alpha + \beta \le 1\) of the shape function reach its boundary. The surface drawn is that minimal boundary, clipped to \(\tau \le (H[Y|X], H[X|Y], I[X:Y])\); every feature of plot_extension_profile is mapped across, so those off the surface are the ones the region of tension does not see. Its axis intercepts are marked: \(\tau_3 = I[X:Y] - K[X:Y]\) (the Gács-Körner point) and \(\tau_1, \tau_2\) the necessary conditional entropies (the Kamath points).

The channel-synthesis curve lies on the face \(\tau_3 = 0\), where \(C(t, X \to Y) = I[X:Y] + \min_{\tau_3 = 0} \{\tau_2 + (\tau_1 - t)^+\}\) [Cuf13]: its common-randomness rate is read off the \(\tau_1\) axis, from the Wyner point to the \(\tau_1\) intercept \(H[Y \dagger X]\).

Parameters:

  • profile (ExtensionProfile) – The profile.

  • features (dict) – The output of ExtensionProfile.compute.

  • height (int) – Figure height in pixels.

Returns:

fig – The interactive figure.

Return type:

plotly.graph_objects.Figure

excess_functional_information(pxy, max_functions=200000, reduce=True)[source]

The excess functional information [LEG18b]

\[\Psi(X \to Y) = \inf_{W \perp X} H[Y|W] - I[X:Y],\]

computed exactly. Refining any \(W\) independent of \(X\) by a random function \(F: \mathcal{X} \to \mathcal{Y}\) independent of \(X\) only lowers \(H[Y|W]\), and \(H[Y | F = f] = H[f(X)]\), so the infimum is a linear program over distributions on functions with \(P(f(x) = y) = p(y|x)\).

Three exact reductions shrink that program first:

  • Common part. With \(g\) the Gács-Körner common part (the connected components of the support), a \(W\) independent of \(X\) is independent of \(g\) and of \(X\) given \(g\), and per-block auxiliaries combine into one, so \(\inf H[Y|W] = H[g] + \sum_k p(k) \inf H[Y|W, g = k]\).

  • X to its minimal sufficient statistic about Y. Merging values with identical \(p(y|x)\) leaves the infimum unchanged: an auxiliary for the merged variable lifts by resampling \(X\) given its class independently of \((Y, W)\).

  • Y to its minimal sufficient statistic about X. Merging values with proportional \(p(x|y)\) also leaves it unchanged: given its class \(Y\) is independent of \(X\), so \(W\) can carry an independent draw of \(Y\) for every class.

Parameters:

  • pxy (np.ndarray) – The joint pmf p(x, y), shape (|X|, |Y|).

  • max_functions (int) – Give up (return None) if a reduced block still has more functions than this.

  • reduce (bool) – Whether to apply the reductions (False solves the raw program, for testing).

Returns:

  • psi (float, None) – The excess functional information.

  • inf_h (float, None) – \(\inf_{W \perp X} H[Y|W] = I[X:Y] + \Psi\), the height of the corner \((H[X], I + \Psi, I + \Psi)\) of the extension profile.

korner_graph_entropy(pxy, max_sets=5000, iters=5000, reduce=True)[source]

Körner’s graph entropy [Korner73] of the characteristic graph of \(X\) (two values are adjacent when some \(y\) is compatible with both),

\[H_K(X) = \min_{X \in U \in \Gamma} I[X:U],\]

with \(\Gamma\) the maximal independent sets. In the extension profile it fixes the point \((x, H[Y|X] + x, x)\) with \(x = H[X] - H_K(X)\) on the edge \(U - X - Y\), \(H[X|Y, U] = 0\) [LEG18a].

The graph is first reduced by substitution [Korner73]: values with the same support set are adjacent twins, so each class collapses to one vertex at a cost of \(p(\text{class}) H[X|\text{class}]\); a disconnected graph contributes the weighted entropies of its components, and a join (disconnected complement) adds the entropy of the part masses. Only prime graphs enumerate maximal independent sets, on which the convex minimization is solved by Blahut-Arimoto style alternating minimization.

Parameters:

  • pxy (np.ndarray) – The joint pmf p(x, y).

  • max_sets (int) – Give up (return None) if a prime graph has more maximal independent sets.

  • iters (int) – Alternating-minimization iterations.

  • reduce (bool) – Whether to apply the reductions (False enumerates on the full graph, for testing).

Returns:

h_k – The graph entropy.

Return type:

float, None

lossy_wyner_common_information(dist, bounds=None, distortions=None, rvs=None, crvs=None, niter=None, maxiter=1000, bound=None)[source]

The lossy Wyner common information C(D_1, ..., D_n).

This is the minimum common rate R_0 = I(X_{1:n} : W) over auxiliary variables W that place the network on its minimum sum-rate face while meeting every distortion budget (Viswanatha, Akyol, & Rose 2014). For D_i = 0 (lossless) it coincides with the standard Wyner common information.

Parameters:

  • dist (Distribution) – The source distribution.

  • bounds (list, None) – Per-decoder distortion budgets D_i. If None (or all zero), the lossless Wyner common information is returned.

  • distortions (list, None) – Per-decoder distortion matrices (None entries are lossless).

  • rvs (list of lists, None) – The source groups. If None, each variable is its own source.

  • crvs (list, None) – Variables to condition on.

  • niter (int, None) – Number of basin hops.

  • maxiter (int) – Inner optimizer iterations.

  • bound (int, None) – Optional cap on the cardinality of W.

Returns:

C – The lossy Wyner common information.

Return type:

float

maximal_interaction_information(dist, rvs=None, crvs=None, niter=None, maxiter=1000, bound=None)[source]

Compute the maximal interaction information.

\[G_{NNI}(X : Y) = \max_U I[X{:}Y|U] - I[X{:}Y]\]

the largest amount by which a probe can increase the dependence between X and Y [LEG18a]. It vanishes exactly when the support graph contains no path of length three, equivalently when p(x|y) = 1 or p(y|x) = 1 at every outcome of positive probability, and is bounded above by min{H[X|Y], H[Y|X]}.

Parameters:

  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two sources. If None, all variables of dist are used.

  • crvs (list, None) – Variables to condition on.

  • niter (int, None) – Number of basin hops to perform during the optimization.

  • maxiter (int) – The number of iterations of the optimization subroutine to perform.

  • bound (int, None) – Bound the size of the probe variable.

Returns:

G – The maximal interaction information.

Return type:

float

asymmetric_private_interaction_information(dist, rvs=None, crvs=None, niter=None, maxiter=1000, bound=None)[source]

Compute the asymmetric private interaction information.

\[G_{PNI}(X \to Y) = \max_{U \perp X} I[X{:}Y|U] - I[X{:}Y]\]

the maximal interaction information achievable by a probe independent of the first source [LEG18a]. Operationally, if Alice holds X and must generate Y using only public randomness W, the least leakage I[Y:W] she can achieve is H[Y|X] - G_PNI(X -> Y).

It vanishes exactly when the maximal interaction information does. This quantity is not symmetric; swap rvs for the other direction.

Parameters:

  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two sources, in the order [X, Y]. If None, all variables of dist are used.

  • crvs (list, None) – Variables to condition on.

  • niter (int, None) – Number of basin hops to perform during the optimization.

  • maxiter (int) – The number of iterations of the optimization subroutine to perform.

  • bound (int, None) – Bound the size of the probe variable.

Returns:

G – The asymmetric private interaction information.

Return type:

float

symmetric_private_interaction_information(dist, rvs=None, crvs=None, niter=None, maxiter=1000, bound=None)[source]

Compute the symmetric private interaction information.

\[G_{PPI}(X : Y) = \max_{U \perp X,\, U \perp Y} I[X{:}Y|U] - I[X{:}Y] = \max_{U \perp X,\, U \perp Y} I[XY{:}U]\]

the most that can be disclosed about the pair while telling an eavesdropper holding either source alone nothing [LEG18a]. It vanishes exactly when the support graph is acyclic.

Parameters:

  • dist (Distribution) – The distribution of interest.

  • rvs (list of lists, None) – The two sources. If None, all variables of dist are used.

  • crvs (list, None) – Variables to condition on.

  • niter (int, None) – Number of basin hops to perform during the optimization.

  • maxiter (int) – The number of iterations of the optimization subroutine to perform.

  • bound (int, None) – Bound the size of the probe variable.

Returns:

G – The symmetric private interaction information.

Return type:

float

class GrayWynerOptimizer(dist, lambdas, rvs=None, crvs=None, distortions=None, bounds=None, markov=False, bound=None, allow_signed=False, rate_equalities=None)[source]

Minimize a weighted sum of Gray-Wyner rates over the common auxiliary variable W (and reconstruction test channels for lossy decoders).

Coordinate transforms

rates_to_tension(point, marginal_entropies, joint_entropy)[source]

Convert a Gray-Wyner rate point to tension coordinates.

Parameters:

  • point (GrayWynerPoint) – The rate point (R_0, (R_1, ..., R_n)).

  • marginal_entropies (iterable of float) – The marginal entropies H[X_i].

  • joint_entropy (float) – The joint entropy H[X_{0:n}].

Returns:

tension – The corresponding point of the region of tension.

Return type:

TensionPoint

tension_to_rates(tension, marginal_entropies, joint_entropy)[source]

Convert tension coordinates back to a Gray-Wyner rate point.

Inverts rates_to_tension(). Summing the per-source tensions and subtracting the residual eliminates the private rates and leaves (n - 1) R_0, which is why at least two sources are required.

Parameters:

  • tension (TensionPoint) – The point of the region of tension.

  • marginal_entropies (iterable of float) – The marginal entropies H[X_i].

  • joint_entropy (float) – The joint entropy H[X_{0:n}].

Returns:

point – The corresponding Gray-Wyner rate point.

Return type:

GrayWynerPoint

rates_to_extension(point, joint_entropy)[source]

Convert a Gray-Wyner rate point to extension-profile coordinates.

The private rates are the conditional entropies H[X_i | W], so this map only computes the residual coordinate.

Parameters:

  • point (GrayWynerPoint) – The rate point (R_0, (R_1, ..., R_n)).

  • joint_entropy (float) – The joint entropy H[X_{0:n}].

Returns:

extension – The corresponding point of the extension profile.

Return type:

ExtensionPoint

extension_to_rates(extension, joint_entropy)[source]

Convert extension-profile coordinates back to a Gray-Wyner rate point.

Inverts rates_to_extension().

Parameters:

  • extension (ExtensionPoint) – The point of the extension profile.

  • joint_entropy (float) – The joint entropy H[X_{0:n}].

Returns:

point – The corresponding Gray-Wyner rate point.

Return type:

GrayWynerPoint

rates_to_mutual_information(point, marginal_entropies)[source]

Convert a Gray-Wyner rate point to mutual information coordinates.

Parameters:

  • point (GrayWynerPoint) – The rate point (R_0, (R_1, ..., R_n)).

  • marginal_entropies (iterable of float) – The marginal entropies H[X_i].

Returns:

info – The corresponding point of the mutual information region.

Return type:

MutualInformationPoint

mutual_information_to_rates(info, marginal_entropies)[source]

Convert mutual information coordinates back to a Gray-Wyner rate point.

Inverts rates_to_mutual_information().

Parameters:

  • info (MutualInformationPoint) – The point of the mutual information region.

  • marginal_entropies (iterable of float) – The marginal entropies H[X_i].

Returns:

point – The corresponding Gray-Wyner rate point.

Return type:

GrayWynerPoint

The support-spectrum helpers used above (support_biadjacency, support_singular_values, spectral_entanglement_bound) live in dit.algorithms; see the API reference.