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:

The Wyner Common Information \(\C{\cdot}\) is the smallest common rate \(R_0\) on the minimum sum-rate face.
The Gács-Körner Common Information \(\K{\cdot}\) is the largest common rate incurring no sum-rate penalty.
The Exact Common Information \(\G{\cdot}\) and Kamath-Anantharam Common Information \(\operatorname{U}(\cdot)\) are further extreme points.

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 [LEG18].

Warning

dit follows the coordinate ordering of [PP14] and [LEG18], 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 [LEG18] 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 [LEG18].

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();

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.

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

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 [LEG18] 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

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_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

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

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

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.

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

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

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

plot()[source]

Plot the shape function.

Returns:: fig – The resulting figure.
Return type:: plt.Figure

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

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 [LEG18]. 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 [LEG18]. 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 [LEG18]. 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

Support spectrum

support_biadjacency(dist, rvs=None, crvs=None)[source]

The 0/1 biadjacency matrix of the support graph of a pair.

Parameters:

dist (Distribution) – The distribution of interest.
rvs (list of lists, None) – The two variables. If None, all variables of dist are used.
crvs (list, None) – Variables to condition on. Conditioning variables are folded into both sides, so the support graph is that of the coalesced pair.

Returns:

matrix – The 0/1 matrix, with a one wherever the pair has positive probability.

Return type:

np.ndarray

support_singular_values(dist, rvs=None, crvs=None)[source]

The singular values of the support graph’s biadjacency matrix.

Parameters:

dist (Distribution) – The distribution of interest.
rvs (list of lists, None) – The two variables. If None, all variables of dist are used.
crvs (list, None) – Variables to condition on.

Returns:

sigmas – The singular values, in decreasing order.

Return type:

np.ndarray

Examples

The Fano plane’s point-line incidence graph is biregular of degree three, so its top singular value is three:

>>> import numpy as np
>>> from dit import Distribution
>>> lines = ['012', '034', '056', '136', '145', '235', '246']
>>> outcomes = [(str(p), str(i)) for i, line in enumerate(lines) for p in line]
>>> fano = Distribution(outcomes, [1 / 21] * 21)
>>> float(np.round(support_singular_values(fano)[0], 10))
3.0

spectral_entanglement_bound(dist, rvs=None, crvs=None)[source]

The nominal spectral lower bound on the entanglement.

Matveev & Romashchenko [MR26b] bound the entanglement of a pair uniform on its support from below by

\[E(X, Y) \geq \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. This function returns the nominal term min{I, 2 log(lambda_1 / lambda_2)} only.

Warning

The suppressed O(log H[XY]) slop is not a formality; it dominates at small alphabets. The uniform distribution on an 8-cycle has entanglement about 0.67 bits against a nominal bound of 1.00. Use this to compare pairs or to reason asymptotically, never as a pointwise certificate.

Parameters:

dist (Distribution) – The distribution of interest.
rvs (list of lists, None) – The two variables. If None, all variables of dist are used.
crvs (list, None) – Variables to condition on.

Returns:

bound – The nominal bound, in bits. Infinite spectral gap (a support with only one nonzero singular value, i.e. a complete bipartite graph on each component) returns the mutual information.

Return type:

float