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.

The Tension Common Information and the entanglement are read off the same 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