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.

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)

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

rate_point(lambdas, niter=None, maxiter=1000, polish=1e-06, rng=None)[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.

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

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.

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

class GrayWynerOptimizer(dist, lambdas, rvs=None, crvs=None, distortions=None, bounds=None, markov=False, bound=None)[source]: Minimize a weighted sum of Gray-Wyner rates over the common auxiliary variable W (and reconstruction test channels for lossy decoders).