{'fraction_non_alphanumeric': 0.050149091894822445, 'fraction_numerical': 0.01210806903406524, 'mean_word_length': 4.188935771214252, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lower bound on Wyner's Common Information

An important notion of common information between two random variables is due to Wyner. In this paper, we derive a lower bound on Wyner's common information for continuous random variables. The new bound improves on the only other general lower bound on Wyner's common information, which is the mutual information. We also show that the new lower bound is tight for the so-called"Gaussian channels"case, namely, when the joint distribution of the random variables can be written as the sum of a single underlying random variable and Gaussian noises. We motivate this work from the recent variations of Wyner's common information and applications to network data compression problems such as the Gray-Wyner network.


I. INTRODUCTION
Extracting and assessing common features amongst multiple variables is a natural task occurring in many different problem settings. Wyner's common information [1] provides one answer to this, which was originally defined for finite alphabets as follows For a pair of random variables, it seeks to find the most compact third variable that makes the pair conditionally independent. Compactness is measured in terms of the mutual information between the pair and the third variable. In [1], Wyner also identifies two operational interpretations. The first concerns a source coding network often referred to as the Gray-Wyner network. For this scenario, Wyner's common information characterizes the smallest common rate required to enable two decoders to recover X and Y, respectively, in a lossless fashion. The second operational interpretation pertains to the distributed simulation of common randomness.
Here, Wyner's common information characterizes the smallest number of random bits that need to be shared between the processors. In subsequent work, Wyner's common information was extended to continuous random variables and was computed for a pair of Gaussian random variables [2], [3] and for a pair of additive "Gaussian channel" distributions [4]. Other related works include [5], [6]. Wyner's common information has many applications, including to communication networks [1], to caching [7, Section III.C], to source coding [8], and to feature extraction [9]. In this paper, we derive a new lower bound on Wyner's common information for continuous random variables. The proof is based on a method known as factorization of convex envelopes, which was originally introduced in [10]. The proof strategy is fundamentally different from the techniques that were used to solve Wyner's original common information problem. Specifically, for the latter, the generic approach is to first characterize the class of variables that enable conditional independence, and then inside this class to find the optimal variable. By contrast, we lower bound the Wyner's common information problem by a convex problem, which we can then solve via optimizing.
We illustrate the promise of the new lower bound by considering Gaussian mixture distributions and Laplace distributions. We also establish that the new lower bound is tight for a simple case of the so-called "Gaussian channels" distribution.
Here, X and Y can be written as the sum of a single arbitrary random variable and jointly Gaussian noises. We note that for this special case, Wyner's common information was previously found, using different methods, in [4]. We use the following notation. Random variables are denoted by uppercase letters X, Y, Z and their realizations by lowercase letters x, y, z. For the cross-covariance matrix of X and Y , we use the shorthand notation K XY , and for the covariance matrix of a random vector X we use the shorthand notation K X := K XX . Let p X (x) denote the probability density function of random variable X at realisation x. Let N (m, σ 2 ) be the Gaussian probability density function with mean m and variance σ 2 .

II. MAIN RESULT
Here we present our lower bound on Wyner's common information. The bound is given in terms of the entropy of the pair, entropy and Wyner's common information for Gaussian random variables. The theorem says: Theorem 1: Let (X, Y ) have probability density function p (X,Y ) that satisfy the covariance constraint K (X,Y ) . Let, where and ρ is the correlation coefficient between X and Y . The proof is given in Section V. A similar argument is used for the max-entropy bound where the probability density functions have covariance constraints. Interestingly, once we plug in Gaussian random variables and additive "Gaussian channel" distributions, then the bound is attained with equality.
Remark 1: In [1], it is showed that C(X; Y ) ≥ I(X; Y ). In Section III-IV we show that our lower bound from Theorem 1 can be tighter.
Remark 2: The bound of Theorem 1 can be expressed equivalently as Remark 3: The bound of Theorem 1 can be negative (if not for the correction). If we choose X and Y to be independent, then X g and Y g will be independent as well. Thus, the bound in (4) becomes that is a negative bound from the positivity of the Kullback-Leibler divergence.
In the latter section, we provide pairs of random variable and compute our lower bounds on Wyner's common information to verify the usefulness of the derived bound.

III. ADDITIVE "GAUSSIAN CHANNEL" DISTRIBUTIONS
In this section, we consider the distributions that are described as follows. Let (X,Ŷ ) be a Gaussian distribution with mean zero and covariance matrix Then, we consider the two-dimensional source given by Let (A, B) be arbitrary random variables with mean zero and covariance where For this particular distribution, we evaluate our lower bound in (1) and also provide an upper bound.

A. Lower Bound
We have that Therefore, the formula given in Theorem 1 evaluates to where (13) follows from substituting for K (X,Y ) and (14) follows from substituting for ρ computed in (11).

B. Upper Bound
Next we give an upper bound on Wyner's common information for the example of this section. To accomplish this, rewrite the pair (X,Ŷ ) aŝ where V, Z x , Z y are mutually independent, V ∼ N (0, 1) and Z x , Z y ∼ N (0, 1 −ρ). Then, a valid choice to make X and Y conditionally independent on W is W = ( √ρ V + A, √ρ V + B). By combining (7) and (15) we can rewrite the pair (X, Y ) as where W is independent of Z x and Z y . So we have where (18) follows by subtracting the parts that are in the conditioning by recalling that W = ( follows from independence of W and (Z x , Z y ) and (20) follows from the independence of Z x and Z y .
where (21) follows from the definition of C(X; Y ) where W satisfies X − W − Y , (22) follows by rewriting the mutual information, (23) follows from subtracting the parts that are in the conditioning and (24) follows from independence of W and (Z x , Z y ).
C. Example 1 Lemma 1: For the additive "Gaussian channel" distributions described in (7) and A = B, we have The proof follows from the fact that the lower bound (14) and upper bound (25) coincide when A = B, which means r = 1. The same result is derived by a different approach in [4]. To illustrate Lemma 1, let A be binary ±σ A with uniform probability. Then, we get Figure 1. . Note that for these choices, the covariance matrix of A and B is given by Equation (8). If we select A = B or r = 1, this model is precisely the model studied in Example 1. A numerical evaluation is shown in Figure 2.

IV. LAPLACE DISTRIBUTIONS
In this section, we consider the case when (X, Y ) is distributed according to the bivariate Laplace distribution described [11,Section 5.1.3] by where K 0 is the modified Bessel function of the second kind described by The variances of X and Y are unity and the correlation coefficient is ρ ℓ . Define the entropy power of (X, Y ) as Then, the bound of Theorem 1 can be expressed as Computation of the joint entropy h(X, Y ) as well as the mutual information I(X; Y ) leads to the curves in Figure 3, further illustrating the potential of the new bound.

A. Preliminary
Theorem 2 (Theorem 2 in [12]): For K 0, 0 < λ < 1, there exists a 0 K ′ K and (X ′ , Y ′ ) ∼ N (0, K ′ ) such that (X, Y ) have distribution p (X,Y ) with covariance constraint K, the following inequality holds Proof 1: The theorem is a consequence of [12, Theorem 2], for a specific choice of p = 1 λ + 1. The proof regarding the existence of the infimum that is missing in [12] is given in [13]. Before we jump into details it is important to realise that inf W h(Y |W ) + h(X|W ) − (1 + λ)h(X, Y |W ) is indeed the lower convex envelope of h(Y ) + h(X) − (1 + λ)h(X, Y ) by thinking of W as a time sharing random variable. In other words, we are taking the infimum over all convex envelopes such that for a covariance constraint on the pair (X, Y ) it satisfies the following The next lemma that is an optimization problem on the covariance matrix constraint for Gaussian random variables is needed for the proof of the theorems.

B. Lower bound on (relaxed) Wyner's common information
Here, we consider a slightly more general case that is, we give a lower bound on relaxed Wyner's common information in Theorem 3. Thus, as a special case we obtain Theorem 1. Let us define the relaxed Wyner's common information as in [13], [14]. For jointly continuous random variables X and Y with joint distribution p(x, y), we define where the constraint of conditional independence is relaxed into an upper bound on the conditional mutual information. For γ = 0, we have C 0 (X; Y ) = C(X; Y ), the standard Wyner's common information. A lower bound on relaxed Wyner's common information is given in the following theorem. Theorem 3: Let (X, Y ) have probability density functions p (X,Y ) that satisfy the covariance constraint K (X,Y ) . Let, (X g , Y g ) ∼ N (0, K (X,Y ) ), then where and ρ is the correlation coefficient between X and Y . Proof 3: Note that the mean of the random variables does not affect the Wyner's common information and its relaxed variant thus, we assume mean zero for both X and Y . Also, the relaxed Wyner's common information is invariant to scaling of X and Y . Thus, without loss of generality we assume X and Y to be mean zero, unity variance and correlation coefficient ρ, so we proceed as follows where (38) follows from weak duality and the bound is valid for all µ ≥ 0; (39) follows from simplification; (40) follows from Theorem 2 under the assumption that µ > 1 where (X ′ , Y ′ ) ∼ N (0, K ′ ); (41) follows from Lemma 2 under the assumption µ ≥ 1 ρ and (42) follows by maximizing the function for µ ≥ 1 ρ . Now we need to solve max µ≥ 1 ρ g(µ). The function g is concave in µ, and by studying the monotonicity we obtain Since the function is concave, the maximum is attained when the first derivative vanishes. That leads to the optimal solution µ * = 1 √ 1−e −2γ , where µ * has to satisfy µ * ≥ 1 ρ . Substituting for the optimal solution we get = h(X, Y ) − h(X g , Y g ) + C γ (X g ; Y g ). (47)

VI. VECTOR WYNER'S COMMON INFORMATION
It is well-known that for n independent pairs of random variables, we have C(X n ; Y n ) = n i=1 C(X i ; Y i ). (48)