Year: 2021

Abstract:
We study an extension of lossy compression where the reconstruction distribution is different from the source distribution in order to account for distributional shift due to processing. We formulate this as a generalization of optimal transport with an entropy bottleneck to account for the rate constraint due to compression. We provide expressions for the tradeoff between compression rate and the achievable distortion with and without shared common randomness between the encoder and decoder. demonstrate We study the examples of binary, uniform and Gaussian sources (in an asymptotic setting) in detail and demonstrate that shared randomness can strictly improve the tradeoff. For the case without common randomness and squared-Euclidean distortion, we show that the optimal solution partially decouples into the problem of optimal compression and transport and also characterize the penalty associated with fully decoupling them. We provide experimental results by training deep learning end-to-end compression systems for performing denoising on SVHN and super-resolution on MNIST, and demonstrate consistency with our theoretical results.

text: We study an extension of lossy compression where the reconstruction distribution is different from the source distribution in order to account for distributional shift due to processing. We formulate this as a generalization of optimal transport with an entropy bottleneck to account for the rate constraint due to compression. We provide expressions for the tradeoff between compression rate and the achievable distortion with and without shared common randomness between the encoder and decoder. demonstrate We study the examples of binary, uniform and Gaussian sources (in an asymptotic setting) in detail and demonstrate that shared randomness can strictly improve the tradeoff. For the case without common randomness and squared-Euclidean distortion, we show that the optimal solution partially decouples into the problem of optimal compression and transport and also characterize the penalty associated with fully decoupling them. We provide experimental results by training deep learning end-to-end compression systems for performing denoising on SVHN and super-resolution on MNIST, and demonstrate consistency with our theoretical results.

heading: 1 INTRODUCTION
text: Using deep neural networks for lossy image compression has proven to be effective, with ratedistortion performance capable of dominating general-purpose image codecs like JPEG, WebP or BPG (Rippel & Bourdev, 2017; Agustsson et al., 2017; Mentzer et al., 2018). More recently, many of these works have included generative aspects within the compression to synthesize realistic elements when the rate is otherwise too low to represent fine-grained details (Tschannen et al., 2018; Agustsson et al., 2019; Mentzer et al., 2020). Though this has been found to deteriorate ratedistortion performance, it has generally resulted in more perceptually-pleasing image reconstruction by reducing artifacts such as pixelation and blur. Using a distributional constraint as a proxy for perceptual measure, several works have subsequently formalized this in a mathematical framework known as the rate-distortion-perception tradeoff (Blau & Michaeli, 2018; 2019; Matsumoto, 2018; 2019; Theis & Wagner, 2021; Yan et al., 2021; Zhang et al., 2021). As is conventional in lossy compression, these works address the scenario in which both low distortion, whereby each individual image reconstruction resembles the ground truth image, and closeness in distribution in which it is not easy to discriminate between image samples from the data-generating distribution and reconstruction distribution, are desirable.
The underlying ideal in conventional compression systems is to have perfect reconstruction with respect to some ground truth input. However this is not the case in applications such as denoising, deblurring, or super-resolution (SR), which require restoration from a degraded input image. In fact, in these cases a ground truth may not even be available. In such applications naturally the reconstruction distribution must match the original source rather than the degraded input distribution. A large body of literature has been devoted to various image restoration tasks, including several methods based on deep learning including both supervised (e.g., (Blau & Michaeli, 2018)) and unsupervised learning methods (e.g., (Wang et al., 2021b)). Although most of the literature exclusively treats compression and restoration separately, in many application they can co-occur. For example, the encoder which records a degraded image may not be co-located with the decoder, but must transmit a compressed version of the image over a digital network. In turn, the decoder must perform both decompression and restoration simultaneously.
To that end, we study an extension of lossy compression in which the reconstruction distribution is different than the source distribution to account for distributional shift due to processing. The problem can be described as a transformation from some source domain to a new target domain under a rate constraint, which generalizes optimal transport. This readily extends other works which view image restoration under the perception-distortion tradeoff (Blau & Michaeli, 2018) or under optimal transport (Wang et al., 2021b). It also provides a generalization of the rate-distortion-perception problem (Blau & Michaeli, 2019) where the reconstruction distribution must be close to the input distribution. Following (Theis & Agustsson, 2021; Theis & Wagner, 2021), we also utilize common randomness as a tool for compression in our setting. Our results are summarized as follows:
• We provide a formulation of lossy compression with distribution shift as a generalization of optimal transport with an entropy constraint and identify the tradeoff between the compression rate and minimum achievable distortion both with and without common randomness at the encoder and decoder. We identify conditions under which the structure of the optimal solution partially decouples the problems of compression and transport, and discuss their architectural implications. We study the examples of binary, uniform and Gaussian sources (in asymptotic regime) in detail and demonstrate the utility of our theoretical bounds.
• We train deep learning end-to-end compression systems for performing super-resolution on MNIST and denoising on SVHN. Our setup is unsupervised and to the best of our knowledge the first to integrate both compression and restoration at once using deep learning. We first demonstrate that by having common randomness at the encoder and decoder the achievable distortion-rate tradeoffs are lower than when such randomness is not present. Furthermore, we provide experimental validation of the architectural principle suggested by our theoretical analysis.
2 THEORETICAL FORMULATION
We consider a setting where an input X ∼ pX is observed at the encoder, which is a degraded (e.g., noisy, lower resolution, etc) version of the original source. It must be restored to an output Y ∼ pY at the decoder, where pY denotes the target distribution of interest. For example, if X denotes a noise-corrupted image and Y denotes the associated clear reconstruction, then pY can be selected to match the distribution of the original source. We will assume pX and pY are probability distributions over X ,Y ⊆ Rn and require X and Y to be close with respect to some fidelity metric, which will be measured using a non-negative cost function d(x, y) over X × Y . We will refer to d(·, ·) as the distortion measure and assume that it satisfies d(x, y) = 0 if and only if x = y. We further assume that X cannot be directly revealed to the decoder, but instead must be transmitted over a bit interface with an average rate constraint. Such a scenario occurs naturally in many practical systems when the encoder and decoder are not co-located such as communication systems or storage systems. As one potential application, when aerial photographs are produced for remote sensing purposes, blurs are introduced by atmospheric
turbulence, aberrations in the optical system and relative motion between camera and ground. In such scenarios unsupervised restoration is preferred as it is often intractable to accurately model such degradation processes and collection of paired training data can be time consuming or require significant human intervention. Unsupervised image restoration has been studied recently in Zhang et al. (2017); Pan et al. (2021); Wang et al. (2021b); Menon et al. (2020). These works also fix the reconstruction distribution Y ∼ pY and propose to minimize a distortion metric between the output and the degraded input as in our present work, but do not consider compression.

heading: 2.1 OPTIMAL TRANSPORT AND EXTENSIONS
text: Definition 1 (Optimal Transport). Let Γ(pX , pY ) be the set of all joint distributions pX,Y with marginals pX and pY . The classical optimal transport problem is defined as
D(pX , pY ) = inf pX,Y ∈Γ(pX ,pY )
E[d(X,Y )], (1)
where we refer to each pX,Y ∈ Γ(pX , pY ) as a transport plan.
Operationally the optimal transport plan in (1) minimizes the average distortion between the input and output while keeping the output distribution fixed to pY . This may generate a transport plan with potentially unbounded entropy, which may not be amenable in a rate-constrained setting. We therefore suggest a generalization to Definition 1 which constrains the entropy of the transport plan. It turns out that having common randomness at the encoder and decoder can help in this setting, so we will distinguish between when it is available and unavailable.
Definition 2 (Optimal Transport with Entropy Bottleneck — no Common Randomness). Let Mncr(pX , pY ) denote the set of joint distributions pX,Z,Y compatible with the given marginal distributions pX , pY satisfying pX,Z,Y = pXpZ|XpY |Z . The optimal transport from pX to pY with an entropy bottleneck of R and without common randomness is defined as
Dncr(pX , pY , R) , inf pX,Z,Y ∈Mncr(pX ,pY ) E[d(X,Y )]
s.t. H(Z) ≤ R, (2)
where H(·) denotes the Shannon entropy of a random variable.
We note that when the rate constraintR is sufficiently large such that one can select Z = X or Z = Y in (2), then Dncr(pX , pY , R) = D(pX , pY ) in (1). More generally, D(pX , pY ) serves as a lower bound for Dncr(pX , pY , R) for any R > 0. Definition 2 also has a natural operational interpretation in our setting. We can view the encoder as implementing the conditional distribution pZ|X to output a representation Z given the input X , and the decoder as implementing the conditional distribution pY |Z to output the reconstruction Y given the representation Z. The entropy constraint H(Z) ≤ R essentially guarantees that the representation Z can be losslessly transmitted at a rate close to R1.
It turns out that when we specialize to the squared Euclidean distance, we can without loss of optimality impose a more structured architecture for implementing the encoder and the decoder. Let W 22 (·, ·) be the squared quadratic Wasserstein distance, by setting d(X,Y ) = ||X − Y ||2 in Definition 1.
Theorem 1. Let
Dmse(pX , pY , R) , inf pX̂|X ,pŶ |Y E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] +W 22 (pX̂ , pŶ )
s.t. E[X|X̂] = X̂, E[Y |Ŷ ] = Ŷ , H(X̂) ≤ R, H(Ŷ ) ≤ R, (3)
and Dmse(pX , R) , inf
pX̂|X E[‖X − X̂‖2]
s.t. H(X̂) ≤ R. (4)

heading: Moreover, let
text: Dncr(pX , pY , R) , Dmse(pX , R) +Dmse(pY , R) +W 2 2 (pX̂∗ , pŶ ∗), (5)
Dncr(pX , pY , R) , Dmse(pX , R) +Dmse(pY , R), (6)
where pX̂∗ and pŶ ∗ are the marginal distributions induced by the minimizers pX̂∗|X and pŶ ∗|Y that attain Dmse(pX , R) and Dmse(pY , R), respectively (assuming the existence of such minimizers). Then under the squared Eucledian distortion measure,
Dncr(pX , pY , R) = Dmse(pX , pY , R). (7)
In addition, we have
Dncr(pX , pY , R) ≥ Dncr(pX , pY , R) ≥ Dncr(pX , pY , R), (8)
and both inequalities are tight when pX = pY .
1The source coding theorem guarantees that any discrete random variable Z can be losslessly compressed using a variable length code with average length of no more than H(Z) + 1 bits.
Theorem 1 deconstructs Z into the quantizations X̂ of X and Ŷ of Y , and decomposes the overall distortion in (2) in terms of the losses due to quantization, transport, and dequantization in (3). It also suggests a natural architecture that partially decouples compression and transport without loss of optimality. First, the sender uses the distribution pX̂|X to produce the compressed representation X̂
from X . This is then passed through a “converter” pŶ |X̂ to transform X̂ to an optimal representation
Ŷ of Y . Finally, the receiver maps Ŷ back to Y using the conditional distribution pY |Ŷ . This is illustrated in Figure 1. The entropy constraint H(X̂) ≤ R in (2) essentially guarantees that X̂ can be losslessly transmitted to the decoder where the converter can be applied to map X̂ to Ŷ before outputting Y . Alternately the constraint H(Ŷ ) ≤ R guarantees that the converter could also be implemented at the encoder and then Ŷ can be compressed and transmitted to the decoder. Finally note that our proposed architecture is symmetric2 with respect to the encoder and the decoder and in particular the procedure to transport Y to X would simply be the inverse of transporting X to Y , and indeed the distortion incurred by dequantizing pY |Ŷ is the same as the distortion incurred by quantizing pŶ |Y .
For the special case of same source and target distribution, we have Dmse(pX , pX , R) = 2Dmse(pX , R), implying that the rate required to achieve distortion D under no output distribution constraint (and with the output alphabet relaxed to Rn) achieves distortion 2D under the constraint that Y equals X in distribution. This recovers the result of Theorem 2 in Yan et al. (2021) for the one-shot setting. More generally, (8) shows that we may lower bound Dmse(pX , pY , R) by the distortion incurred when compressing X and Y individually, each at rate R, through ignoring the cost of transport. On the other hand, the upper bound corresponds to choosing the optimal rate-distortion representations X̂∗, Ŷ ∗ for X,Y , then considering transport between them. The advantage of this approach is that knowledge of the other respective distribution is not necessary for design. Although not optimal in general, we will, in fact, provide an example where this is optimal in Section 2.2.
Finally, the following result implies that under mild regularity conditions, the optimal converter pŶ |X̂ can be realized as a (deterministic) bijection, and in the scalar case it can basically only take the form as illustrated in Figure 1.
Theorem 2. Assume that Dncr(pX , pY , R) is a strictly decreasing function in a neighborhood of R = R∗ and Dncr(pX , pY , R∗) is attained by pX,Z,Y . Let X̂ , E[X|Z] and Ŷ , E[Y |Z]. Then
H(X̂) = H(Ŷ ) = R∗, (9)
E[‖X̂ − Ŷ ‖2] = W 22 (pX̂ , pŶ ), (10) and there is a bijection between X̂ and Ŷ .
We remark that in general computing the optimal transport map is not straightforward. For the case of binary sources we can compute an exact characterization for Dncr as discussed in Section 2.2. Furthermore as discussed in Appendix A.6, W 22 (pX̂ , pŶ ) can be computed in closed form when X̂ and Ŷ are scalar valued, which can be used to obtain upper bounds on Dncr. In our experimental results in Section 3 we use deep learning based methods to learn approximately optimal mappings.
So far we have focused on the setting when there is no shared common randomness between the encoder and the decoder. We will now consider the setting when a shared random variable denoted by U is present at the encoder and decoder. We assume that the variable U is independent of the input X so that the decoder has no apriori information of the input. In practice the sender and receiver can agree on a pseudo-random number generator ahead of time and some kind of seed could be transmitted, after which both sides can generate the same U . We further discuss how shared randomness is used in practice in the experimental section.
Definition 3 (Optimal Transport with Entropy Bottleneck — with Common Randomness). Let Mcr(pX , pY ) denote the set of joint distributions pU,X,Z,Y compatible with the given marginal
2We say that the problem is symmetric if it is invariant under reversing pX , pY with a new distortion measure defined by reversing the arguments of d(·, ·).
distributions pX , pY and satisfying pU,X,Z,Y = pUpXpZ|X,UpY |Z,U , where pU represents the distribution of shared randomness. The optimal transport from pX to pY with entropy bottleneck R and common randomness is defined as
Dcr(pX , pY , R) , inf pU,X,Z,Y ∈Mcr(pX ,pY ) E[d(X,Y )]
s.t. H(Z|U) ≤ R. (11)
Note that we optimize over pU (the distribution associated with shared randomness), in addition to pZ|X,U and pY |Z,U in (11). Furthermore, Dcr(pX , pY , R) ≤ Dncr(pX , pY , R) in general, as we do not have access to shared randomness in Definition 2. Also from the same argument that was made following Definition 2, we have that Dcr(pX , pY , R) ≥ D(pX , pY ) in Definition 1. As with Definition 2, we can also provide a natural operational interpretation. In particular, given the input X and common randomness U the encoder can output a compressed representation Z using the conditional distribution pZ|X,U . The representation Z can be losslessly compressed approximately to an average rate of R again by exploiting the shared randomness U . Finally the decoder, given Z and U can output the reconstruction Y using the conditional distribution pY |Z,U . An interesting difference with Definition 2 is that the setup is no longer symmetric between encoder and decoder, as X is independent of U but Y is not. The following result provides a simplification to the architecture in Definition 3. Theorem 3. Let Qcr(pX , pY ) denote the set of joint distributions pU,X,Y compatible with the given marginals pX , pY satisfying pU,X,Y = pUpXpY |U,X as well as H(Y |U,X) = 0. Then
Dcr(pX , pY , R) = inf pU,X,Y ∈Qcr(pX ,pY )
E[d(X,Y )]
s.t. H(Y |U) ≤ R. (12)
Before discussing the implications of Theorem 3 we remark on a technical point. Because the Shannon entropy is defined only for discrete random variables, U must be chosen in a way such that Y |U = u is discrete for each u, even for continuous (X,Y ). This is known to be possible, e.g., Li & El Gamal (2018) have provided a general construction for a U with this property, with additional quantitative guarantees to ensure that U is informative of Y . In the finite alphabet case we show in Appendix A.3 that optimization of U can be formulated as a linear program.
We next discuss the implication of Theorem 3. First note that the problem can be modelled with only pY |U,X producing a reconstruction Y without the need for the intermediate representation Z, much like the conventional optimal transport in Definition 1. The condition H(Y |U,X) = 0 also implies that the transport plan is deterministic when conditioned on the shared randomness, which plays the role of stochasticity. Furthermore in this architecture the encoder should compute the representation Y given the sourceX and the shared random-variable U (which corresponds to the transport problem) and then compress it losslessly at a rate close to H(Y |U) (which corresponds to the compression problem). The receiver only needs to decompress and reconstruct Y . This is in contrast to the case without common randomness in Theorem 1 where the reconstruction Y must be generated at the decoder.

heading: 2.2 NUMERICAL EXAMPLES
text: We present how the results in Theorem 1 & 3 can be evaluated for some specific source models. We first consider the example of Binary sources. Let X ∼ B(qX) and Y ∼ B(qY ) be two Bernoulli
random variables with qX , qY ∈ (0, 1), and let d(·, ·) be the Hamming distortion measure dH(·, ·) (i.e., dH(x, y) = 0 if x = y and dH(x, y) = 1 otherwise), which coincides with the squared error distortion in Theorem 1 for binary variables. The explicit expressions of Dcr(B(qX),B(qY ), R), Dncr(B(qX),B(qY ), R) as well as Dncr(B(qX),B(qY ), R) and Dncr(B(qX),B(qY ), R) are provided by Theorem 4 in Appendix A.4, from which the following observations can be made. In general, we have Dncr(B(qX),B(qY ), R) > Dcr(B(qX),B(qY ), R), i.e., common randomness strictly improves the distortion-rate tradeoff (except at some extreme point(s)). Moreover, as long as B(qX) and B(qY ) are biased toward the same symbol (namely, qX , qY ≤ 1/2 or qX , qY ≥ 1/2), the upper bound Dncr(B(qX),B(qY ), R) is tight, which implies that blindly using optimal quantizer and dequantizer in the conventional rate-distortion sense incurs no penalty, and the cross-domain knowledge is only needed for optimal transport from the quantizer output and the dequantizer input. Some illustrative examples are shown in Figure 3.
In Appendix A.6 we consider the case when X and Y are continuous valued sources from a uniform distribution and establish an upper bound on Dncr(·) that is shown to be tight as the rate R → ∞. For Gaussian distributions in the asymptotic optimal transport setting (see Appendix A.7 for relevant definitions and results) we present results qualitatively similar to the binary case in Appendix A.8.

heading: 3 EXPERIMENTAL RESULTS
text: We use two sets of results to illustrate that the principles derived from our theoretical results are applicable to practical compression with deep learning. Importantly, we assume an unsupervised setting in which we have only unpaired noisy and clean images available to us, as in Wang et al. (2021b). Our first experiment is, to the best of our knowledge, the first in which restoration and compression are performed jointly using deep learning. We will furthermore demonstrate the utility of common randomness in this setting. Stochasticity was necessary in our theoretical results both with and without common randomness. In practice, we will use generative models to induce domain shift, and stochasticity is necessary to train an effective (rate-constrained) generative model at low rates to produce variety in the reconstructions. The first set of experiments compare the rate-distortion tradeoffs achieved by quantization schemes with and without common randomness using a rate constrained architecture designed for image denoising and super resolution tasks.
The second set of experiments are designed on the principle of Theorem 1. In addition to the generator trained from our first experiment, we will construct a helper network to allow us to estimate the decomposition (3). This is then compared with the direct loss between the noisy image and rate-constrained denoising reconstruction. If the losses are close, this would suggest that the decomposition is not only without loss of optimality but also effective in practice.

heading: 3.1 RATE-DISTORTION COMPARISON WITH COMMON RANDOMNESS
text: Let pX be a degraded source distribution that we wish to restore and pY be the target distribution. Our goal is to compress X so that the reconstruction semantically resembles X within target distribution pY . For our application, we will use MSE loss as a fidelity criterion. Let f be an encoder, Q a quantizer, and g a decoder. For a given rate R with common randomness U available, we have a
problem of the form
min f,g,Q
‖X − g(Q(f(X,U)))‖22
s.t. pg(Q(f(X,U))) = pY , H(Q(f(X,U))|U) ≤ R,
which uses parameterized neural networks to implement (11). We also fix Q such that a hard constraint on the rate is satisfied and assume f and g are sufficiently expressive to map to these fixed quantization points. Let Ỹ ∆= g(Q(f(X,U))). We will use a penalty on the Wasserstein-1 distance between pỸ and pY in accordance with the Wasserstein GAN (Arjovsky et al., 2017) framework, so that our system is a stochastic rate-constrained autoencoder with GAN regularization. Specifically, we follow the network shown in Figure 4(a) which in addition to f , Q, and g contains critic h.
For the realization of common randomness in Definition 3, we adopt the universal quantization scheme of Ziv (1985); Theis & Agustsson (2021). Given trained f and g and degraded image X , we generate restored image Ỹ through
Ỹ = g(Q(f(X) + U)− U), (13)
where U is the stochastic noise shared by the sender and receiver. Details about the quantization are provided in Appendix B.2. To find an appropriate f and g, we use the relaxed objective
L1 = E[‖X − Ỹ ‖2] + λW1(pY , pỸ ), (14)
which is the sum of the MSE and Wasserstein-1 losses weighted by λ. By optimizing our network using this objective, we see two favorable properties. First, the Wasserstein-1 loss ensures the distribution of output is close to that of target images, i.e. pỸ ≈ pY for sufficiently large λ. Moreover, the MSE loss that pushes the output Ỹ to input X ensures that the output structurally resembles X . Consequently, the training objective allows the output Ỹ to be clear and preserves content from input.
To generate a rate-distortion trade-off curve, we modify the encoder to produce a different number of symbols ranging from low bit rate to high bit rate and record the MSE distortion loss between noisy inputs and denoised outputs. Figure 5(a) and Figure 5(c) show the curves for image super-resolution and image denoising. We also show some qualitative results in Figure 5(b) and 5(d). As the rate increases, the generated high-quality images are clearer.
As exemplified by the numerical results in Section 2.2, common randomness can help reduce the rate that is needed for reconstruction given a specific distortion. Equivalently, given a fixed rate, a system with common randomness can perform better than one without common randomness. To demonstrate this in practice, we conduct the following experiment. We remove the common randomness setup from the framework in Section 3.1 and alternatively add two independent noises U1 and U2 to the encoder and decoder sides. Concretely, under the new setting, (13) becomes
Ỹ = g(Q(f(X) + U1)− U2) (15)
Then we conduct training using the objective (14) as in the common randomness. The tradeoff curve without common randomness for both tasks are shown in Figure 5(a) and 5(c) with orange dots. Performance of the framework is better when there is common randomness.

heading: 3.2 ARCHITECTURAL PRINCIPLE
text: In the case without common randomness, Theorem 1 implies that (under the rate constraint) the overall distortion E[‖X − Y ‖2] can be decomposed to the summation of the three distortion terms
E[‖X − Y ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] +W 22 (pX̂ , pŶ ), (16)
where X̂ and Ŷ are some representations of X and Y under MSE distortion. The chosen ratedistortion representations X̂ for X and Ŷ for Y must not only be representative of X and Y , but also enjoy low cost of transport between one another. We now seek to estimate the overhead of this decomposition in practice.
However, due to the nature of the deep learning framework, the distortion measure between images and compressed representations cannot be explicitly measured. Thus, we alternatively develop a two-branch network to compare the summation of the three distortion components (16) to the overall distortion. First, we take trained f and g from the previous experiment and freeze their weights. Given noisy input X , we encode it through f , then decoder g1 is trained to minimize the distortion with X , and decoder g2 is trained to minimize the distortion with Ỹ = f(g(X)) which distributionally approximates a clean restoration (we use Ỹ instead of ground truth because we assume an unsupervised setting). Let
Ỹ1 = g1(f(X)), Ỹ2 = g2(f(X)).
The idea here is that Ỹ1 is a rate-constrained reconstruction of X and Ỹ2 is a rate-constrained reconstruction of Ỹ , both of which are produced from compressing X using f . We assume this is reasonable as in light of Theorem 2, there is no loss of optimality in doing so given sufficiently expressive neural networks. The overall decomposed loss is then given by
L2 = E[‖X − Ỹ1‖2]︸ ︷︷ ︸ (a) +E[‖Ỹ − Ỹ2‖2]︸ ︷︷ ︸ (b) +E[‖Ỹ1 − Ỹ2‖2]︸ ︷︷ ︸ (c) , (17)
in which Ỹ1 approximates X̂ and Ỹ2 approximates Ŷ . Training is performed jointly over g1 and g2.
One additional point is that g1 and g2 can also be trained separately, although in this case we can no longer assume that f can be reused without loss of optimality, as this objective would not be equivalent to minimizing (17) (there is no control over (c)). We develop an additional experiment in which we optimize encoder-decoder pairs f1, g1 to minimize (a) and f2, g2 to minimize (b), where now Ỹ1 is produced using f1, g1 and Ỹ2 using f2, g2. In this setting, we aim to approximate the rate-distortion optimal X̃∗ and Ỹ ∗ corresponding to Dncr(pX , pY , ·) from Theorem 1 using Ỹ1 and Ỹ2, and in doing this separate optimization it is clear that we will drive down (a) and (b) but increase (c). As it turns out, the resultant values (a) and (b) obtained during joint optimization are not much worse than the values from separate optimization. This provides evidence that in practice, the optimal rate-distortion representations (i.e. under objective (4)) can be leveraged for the general objective (17) without much loss of optimality, which further suggests that the encoder f1 can be potentially trained without knowledge of pY without much performance loss. These can be viewed in Table 2.

heading: 4 RELATED WORKS

heading: 5 CONCLUSION AND FUTURE WORK
text: We consider the setting of lossy compression in which we compress across different source and target distributions. We formulate this as an entropy-constrained optimal transport problem and provide expressions for characterizing the tradeoff between compression rate and the minimum achievable distortion with and without shared common randomness. We also develop a number of architectural principles through our theoretical results and provide experimental validations by training deep learning models for super-resolution and denoising tasks over compressed representations. On the theory side it will be interesting to consider the case where there are either rate constraints on the amount of shared common randomness between the encoder and decoder or consider the case when the shared randomness is correlated with the source input, which can arise in many practical applications. On the practical side it will be interesting to experimentally study the a broader set of cross-domain tasks where our theory could be applicable.

heading: A THEORETICAL RESULTS

heading: A.1 DISTORTION-RATE VS RATE-DISTORTION FORMULATION
text: In addition to Definitions 2 and 3, we can equivalently define
Rncr(pX , pY , D) , inf pX,Z,Y ∈Mncr(pX ,pY ) H(Z)
s.t. E[d(X,Y )] ≤ D, (18)
Rcr(pX , pY , D) , inf pU,X,Z,Y ∈Mcr(pX ,pY ) H(Z|U)
s.t. E[d(X,Y )] ≤ D. (19)
Dncr/cr(pX , pY , R) and Rncr/cr(pX , pY , D) are monotonically decreasing in R and D, respectively, so they are the inverse of each other. Sometimes it is more convenient to work with this rate-distortion formulation.

heading: A.2 PROOFS OF THEORETICAL RESULTS
text: Proof of Theorem 1. For any pX,Z,Y ∈Mncr(pX , pY ) with H(Z) ≤ R,
E[‖X − Y ‖2] = E[‖X − E[X|Z]‖2] + E[‖Y − E[Y |Z]‖2] + E[‖E[X|Z]− E[Y |Z]‖2] ≥ Dmse(pX , pY , R),
where the last inequality follows from the definition of Dmse(pX , pY , R) and the fact that
max{H(E[X|Z]), H(E[Y |Z]} ≤ H(Z) ≤ R.
As a consequence, we must have Dncr(pX , pY , R) ≥ Dmse(pX , pY , R). On the other hand, for any pX̂|X , pŶ |Y with E[X|X̂] = X̂ , E[Y |Ŷ ] = Ŷ , H(X̂) ≤ R, and H(Ŷ ) ≤ R, we can construct a joint distribution pX,X̂,Ŷ ,Y such that X ↔ X̂ ↔ Ŷ ↔ Y form a Markov chain, pX,X̂ = pXpX̂|X , pY,Ŷ = pY pŶ |Y , and pX̂,Ŷ satisfying E[‖X̂ − Ŷ ‖2] = W 22 (pX̂ , pŶ ). Note that
E[‖X − Y ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] +W 22 (pX̂ , pŶ ). (20)
Let Z , X̂ . It can be verified that pX,Z,Y ∈ Mncr(pX , pY ) and H(Z) = H(X̂) ≤ R, which, together with (20), implies Dncr(pX , pY , R) ≤ Dmse(pX , pY , R). This completes the proof of (7).
Dropping the term W 22 (pX̂ , pŶ ) in (3) yields
Dncr(pX , pY , R) ≥ D̃mse(pX , R) + D̃mse(pY , R),
where
D̃mse(pX , R) , inf pX̂|X
E[‖X − X̂‖2]
s.t. E[X|X̂] = X̂, H(X̂) ≤ R.
and D̃mse(pY , R) is definely analogously. On the other hand, choosing pX̂|X = pX̂′|X and pŶ |Y = pŶ ′|Y in (3) gives
Dncr(pX , pY , R) ≤ D̃mse(pX , R) + D̃mse(pY , R) +W 22 (pX̂′ , pŶ ′),
where pX̂′|X and pŶ ′|Y are the minimizers that attain D̃mse(pX , R) and D̃mse(pY , R) respectively while pX̂′ and pŶ ′ are their induced marginal distributions. It is clear that pX̂′|X and pŶ ′|Y coincide
with pX̂∗|X and pŶ ∗|Y respectively as the constraints E[X|X̂] = X̂ and E[Y |Ŷ ] = Ŷ are automatically satisfied by pX̂∗|X and pŶ ∗|Y . This proves (8). For the special case pX = pY , we have pX̂∗|X = pŶ ∗|Y and consequently the upper bound and the lower bound in (8) coincide.
Note that due to the involvement of conditional expectation, X̂ is not necessarily defined over X if X is a strict subset of Rn (for the same reason, Ŷ is not necessarily defined over Y). In other words, the output of the quantizer is not consrained to the input alphabet and needs to be relaxed to Rn. As such, Dmse(pX , R) should be interpreted as the one-shot distortion-rate function with the reconstruction alphabet being Rn, which is in general strictly below its counterpart with the reconstruction alphabet being X (also known as the distortion-rate-perception function with an inactive perception constraint) if X is a strictly subset of Rn. This subtle issue, which is often overlooked in the literature, arises when one deals with discreteX and Y (see the binary example in Section 2.2 and Appendix A.4).
Proof of Theorem 2. We have that max{H(X̂), H(Ŷ )} ≤ R∗. If one of them, say H(Y ), is less than R∗, this will lead to a contradiction by the following argument. Note that
D∗ = E[‖X − Y ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2],
which depends on pX,X̂,Ŷ ,Y only through pX,X̂ , pX̂,Ŷ , and pY,Ŷ . We can construct a new joint distribution pX,X̂′,Ŷ ′,Y such that pX,X̂′ = pX,X̂ , pX̂′,Ŷ ′ = pX̂,Ŷ , pY,Ŷ ′ = pY,Ŷ , and X ↔ X̂ ′ ↔ Ŷ ′ ↔ Y form a Markov chain. Denote X̂ ′ by Z ′. It is clear that the induced pX,Z′,Y belongs to Mncr(pX , pY ), preserves E[‖X − Y ‖2], and H(Z ′) < R∗, which is contradictory with the fact that Dncr(pX , pX̂ , R) is a strictly decreasing function in a neighborhood of R = R
∗ since R can be set slightly below R∗ without violating the constraint H(Z ′) ≤ R. This proves (9), which futher implies the existence of a bijection between X̂ and Ŷ .
It remains to prove (10). If (10) does not hold, then we can find some pX̂′′,Ŷ ′′ with pX̂′′ = pX̂ and pŶ ′′ = pŶ such that E[‖X̂ ′′− Ŷ ′′‖2] < E[‖X̂− Ŷ ‖2]. Leverage this pX̂′′,Ŷ ′′ to construct a new joint distribution pX,X̂′′,Ŷ ′′,Y such that pX,X̂′′ = pX,X̂ , pY,Ŷ ′′ = pY,Ŷ , and X ↔ X̂ ′′ ↔ Ŷ ′′ ↔ Y form a Markov chain. Denote X̂ ′′ by Z ′′. It is clear that the induced pX,Z′′,Y belongs to Mncr(pX , pY ), H(Z ′′) = R∗, and
E[‖X − Y ‖2] = E[‖X − X̂ ′′‖2] + E[‖Y − Ŷ ′′‖2] + E[‖X̂ ′′ − Ŷ ′′‖2] < E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2] = D∗,
which is contradictory with the fact that Rncr(pX , pY , D) is a strictly decreasing function in a neighborhood of D = D∗ , Dncr(pX , pX̂ , R
∗) since D can be set slightly below D∗ without violating the constraint E[‖X − Y ‖2] ≤ D. So in conclusion, the converter is a one-to-one mapping, which induces an optimal coupling that attains W 22 (pX̂ , pŶ ).
Proof of Theorem 3. Choosing pU,X,Y from W 22 (pX , pY ) and setting Z = Y shows that
Dcr(pX , pY , R) ≤ inf pU,X,Y ∈W (pX ,pY ) E[d(X,Y )]
s.t. H(Y |U) ≤ R.
So it remains to prove that this upper bound is tight. In the light of the functional representation lemma, for any (U,X,Z, Y ) with pU,X,Z,Y ∈Mcr(pX , pY ), there exist V1, independent of (U,X), and V2, independent of (U,X, V1), as well as determintic mappings φ1 and φ2 such that Z = φ2(U,X, V1) and Y = φ2(Z, V2). Let U ′ , (U, V1, V2). Clearly, pU ′,X,Y = pU ′pXpY |U ′,X and H(Y |U ′, X) = 0. Moreover, we have
H(Z|U) ≥ H(Z|U ′) ≥ H(Y |U ′),
where the last inequality is due to the fact that Y is determined by (Z,U ′). Therefore,
Dcr(pX , pY , R) ≥ inf pU′,X,Y ∈W (pX ,pY ) E[d(X,Y )]
s.t. H(Y |U ′) ≤ R.
This completes the proof of (12).
Note that each realization of U is associated with a deterministic function from X to Y . As a consequence, the problem boils down to optimizing the probablity distribution defined over this collection of functions. For the finite alphabet case, there are totally |Y||X | such functions. In fact, a simple application of the support lemma shows that only |Y|+ 1 functions need to be assigned with a positive probability.

heading: A.3 LINEAR PROGRAM FORMULATION FOR COMMON RANDOMNESS
text: In the finite alphabet case, we can formulate Theorem 3 as follows:
Dcr(pX , pY , R) = min pU
∑ u∈U pU (u)E[d(X, fu(X))]
s.t. ∑
u∈U pU (u)H(fu(X)) ≤ R, ∑ u∈U pU (u)P(fu(X) = y) = pY (y), y ∈ Y,
where pU is defined over U , {1, 2, · · · , |Y||X |}, and {fu : u ∈ U} is the set of all distinct functions from X to Y . By the support lemma (Appendix C on page 631 of El Gamal & Kim (2011)), only |Y|+ 1 functions need to be assigned with a positive probability.

heading: A.4 BINARY CASE
text: LetD(B)min , |qX−qY | andD (B) max , qX +qY −2qXqY . Note thatD(B)min is the total variation distance between B(qX) and B(qY ), which is the minimum E[dH(X,Y )] achievable by coupling X and Y . On the other hand, we have E[dH(X,Y )] = D(B)max for X , Y independent. It is clear that D(B)min and D (B) max are the infimum and supremum ofDncr(B(qX),B(qY ), R) (as well asDcr(B(qX),B(qY ), R)), respectively.
Theorem 4. Assume Hamming distortion measure. Under no common randomness, we have
Dncr(B(qX),B(qY ), R) =    − 2(1−qX)(1−qY ) 1−H−1b (R) + 2− qX − qY , qX + qY ≤ 1,
− 2qXqY 1−H−1b (R)
+ qX + qY , qX + qY > 1, (21)
for R ∈ [0,min{Hb(qX), Hb(qY )}], and = D(B)min for R > min{Hb(qX), Hb(qY )}. Moreover,
Dncr(B(qX),B(qY ), R)
=    − 2(1−qX)(1−qY ) 1−H−1b (R) + 2− qX − qY , qX , qY ≤ 12 , − 2qXqY 1−H−1b (R) + qX + qY , qX , qY ≥ 12 , − (1−qX) 2+q2Y −(qY −qX+H−1b (R))2 1−H−1b (R) +H−1b (R)− 2qY (1−qX)H−1b (R) (1−H−1b (R))2 , qX < 1 2 , qY > 1 2 , − q 2 X+(1−qY )2−(qX−qY +H−1b (R))2
1−H−1b (R) +H−1b (R)− 2qX(1−qY )H−1b (R) (1−H−1b (R))2 , qX > 1 2 , qY < 1 2 ,
(22)
for R ∈ [0,min{Hb(qX), Hb(qY )}], and
Dncr(B(qX),B(qY ), R) =    − (1−qX) 2+(1−qY )2 1−H−1b (R) + 2− qX − qY , qX , qY ≤ 12 , − q 2 X+q 2 Y 1−H−1b (R) + qX + qY , qX , qY ≥ 12 , − (1−qX) 2+q2Y 1−H−1b (R) + 1− qX + qY , qX < 12 , qY > 1 2 ,
− q 2 X+(1−qY )2 1−H−1b (R) + 1 + qX − qY , qX > 12 , qY < 1 2 ,
(23)
for R ∈ [0,min{Hb(qX), Hb(qY )}]. Here, H−1b (R) denotes the inverse of the binary entropy function on [0, 1/2]. With common randomness,
Dcr(B(qX),B(qY ), R) = − 2(1− qX)qXR
Hb(qX) +D(B)max (24)
for R ∈ [0, ρHb(qX)], and = D(B)min for R > ρHb(qX). Here, ρ , min{qY /qX , (1−qY )/(1−qX)}.
Proof of (24). There are totally 4 distinct functions from {0, 1} to {0, 1}:
f1(x) = x, f2(x) = 1− x, f3(x) = 0, f4(x) = 1, x ∈ {0, 1}.
Therefore, we have ∑
u∈U pU (u)H(fu(X)) = Hb(qX)(pU (1) + pU (2)), ∑ u∈U pU (u)E[dH(X, fu(X))] = pU (2) + qXpU (3) + (1− qX)pU (4), ∑ u∈U pU (u)P(fu(X) = 1) = pU (1)qX + (1− qX)pU (2) + pU (4).
In light of Theorem 3,
Rcr(B(qX),B(qY ), D) = min pU (1),··· ,pU (4) Hb(qX)(pU (1) + pU (2))
s.t. pU (2) + qXpU (3) + (1− qX)pU (4) ≤ D, (25) qXpU (1) + (1− qX)pU (2) + pU (4) = qY , (26) pU (1) + pU (2) + pU (3) + pU (4) = 1, (27) pU (1), pU (2), pU (3), pU (4) ≥ 0. (28)
Note that
pU (2) + qXpU (3) + (1− qX)pU (4) = pU (2) + qXpU (3) + (1− qX)(1− pU (1)− pU (2)− pU (3)) (29) = −(1− qX)pU (1) + qXpU (2) + (2qX − 1)pU (3) + 1− qX , (30)
where (29) is due to (27). Moreover, it follows by (26) and (27) that
pU (3) = −(1− qX)pU (1)− qXpU (2) + 1− qY . (31)
Substituting (31) into (30) and invoking the fact that pU (2) ≥ 0 gives
pU (2) + qXpU (3) + (1− qX)pU (4) = −2(1− qX)qX(pU (1) + pU (2)) + 4(1− qX)qXpU (2) +D(B)max ≥ −2(1− qX)qX(pU (1) + pU (2)) +D(B)max,
which, together with (25), implies
pU (1) + pU (2) ≥ 1
2(1− qX)qX (D(B)max −D).
As a consequence, we must have
Rcr(B(qX),B(qY ), D) ≥ Hb(qX)
2(1− qX)qX (D(B)max −D).
One can readily verify that this lower bound is tight as it is attained by p∗U with
p∗U (1) = 1
2(1− qX)qX (D(B)max −D),
p∗U (2) = 0,
p∗U (3) = − 1
2qX (D(B)max −D) + 1− qY ,
p∗U (4) = − 1
2(1− qX) (D(B)max −D) + qY ,
which satisfies (25)–(28) for D ∈ [D(B)min, D (B) max]. The expression of Dcr(B(qX),B(qY ), R) can be obtained by taking the inverse of Rcr(B(qX),B(qY ), D).
Proof of (21). We will rely on some results which will come after this proof.
Note that Hamming distortion coincides with squared error distortion when X = Y = {0, 1}. So Theorem 1, Lemma 1, and Lemma 2 are applicable here. In particular, in light of Lemmas 1 and 2, for any R ≥ 0 and > 0, there exists a joint distribution pXX̂Ŷ Y compatible with the given marginal distributions pX and pY such that X̂ and Ŷ are deterministically related finite-support random variables with H(X̂) = H(Ŷ ) ≤ R and X ↔ X̂ ↔ Ŷ ↔ Y form a Markov chain; moreover, X̂ = E[X|X̂], Ŷ = E[Y |Ŷ ], and
E[‖X − X̂‖2] + E[‖Y − Ŷ ‖] + E[‖X̂ − Ŷ ‖2] ≤ Dncr(B(qX),B(qY ), R) + . (32)
Without loss of generality, we assume X̂ and Ŷ take value from {x̂i}Ni=1 and {ŷi}Ni=1, respectively, and Ŷ = ψ(X̂), where ψ is a bijection from {x̂i}Ni=1 to {ŷi}Ni=1 with ŷi = ψ(x̂i), i = 1, · · · , N . Let θi , pX̂(x̂i), or equivalently, θi , pŶ (ŷi), i = 1, · · · , N . Note that X̂ = E[X|X̂] and Ŷ = E[Y |Ŷ ] if and only if pX|X̂(1|x̂i) = x̂i and pY |Ŷ (1|ŷi) = ŷi for θi > 0, i = 1, · · · , N . So the constraints∑N i=1 pX̂(x̂i)pX|X̂(1|x̂i) = qX and
∑N i=1 pŶ (ŷi)pY |Ŷ (1|ŷi) = qY can be written equivalently as∑N
i=1 θix̂i = qX and ∑N i=1 θiŷi = qY . Moreover, it is easy to verify that
E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2]
=
N∑
i=1
θi(1− x̂i)x̂i + N∑
i=1
θi(1− ŷi)ŷi + n∑
i=1
θi(x̂i − ŷi)2
=
N∑
i=1
θi(x̂i + ŷi − 2x̂iŷi).
In light of Theorem 1 and (32), the following optimization problem (P) yields an upper bound on Dncr(pX , pY , R) with a gap at most :
min (θi,x̂i,ŷi,)Ni=1
N∑
i=1
θi(x̂i + ŷi − 2x̂iŷi) (P)
s.t. N∑
i=1
θi log 1
θi ≤ R,
N∑
i=1
θi = 1,
N∑
i=1
θix̂i = qX ,
N∑
i=1
θiŷi = qY ,
θi ≥ 0, x̂i ∈ [0, 1], ŷi ∈ [0, 1], i = 1, · · · , N.
Given (θi, ŷi)Ni , (P) degenerates to a linear programming problem with respect (x̂i) N i=1 over hyper-
rectangle [0, 1]N subject to the constraint ∑N i=1 θix̂i = qX , for which the minimum is attained at
a point on an edge of [0, 1]N . Therefore, it suffices to consider (x̂i)Ni=1 with at most one element different from 0 and 1. By a similar argument, it can be shown that there is no loss of optimality in assuming that at most one of ŷi, i = 1, · · · , N , takes value other than 0 or 1. Due to the merge of different elements, the one-to-one relationship might not be preserved. Nevertheless, by Lemma 2, we just need to consider deterministically related X̂ and Ŷ with support size at most 3. Applying the linear programming argument to (P) with N = 3 shows that, at the cost of potentially compromising the one-to-one relationship, at most one element in the support of X̂ as well as the support of Ŷ need to take value different from 0 and 1. In the case that the bijection is lost, X̂ or Ŷ must have a reduced support size. One can restore the bijection by invoking Lemma 2, then use the linear programming argument to assign extreme values to all but at most one element in the support. Following this line of reasoning, we can conclude that the attention can be restricted to deterministically related X̂ and Ŷ with support size at most 3 and at most one element in the support different from 0 and 1. Moreover, the following configurations can be excluded.
1. Support size = 3 and the existence of pairs (x̂, ŷ) and (x̂′, ŷ′) for some x̂ > x̂′ and ŷ < ŷ′
((x̂, ŷ) is said to be a pair if X̂ = x̂⇔ Ŷ = ŷ): Since
(x̂− ŷ)2 + (x̂′ − ŷ′)2 − (x̂− ŷ′)2 − (x̂′ − ŷ)2
= −2x̂ŷ − 2x̂′ŷ′ + 2x̂ŷ′ + 2x̂′ŷ = 2(x̂− x̂′)(ŷ′ − ŷ) > 0,
it follows that E[‖X̂−Ŷ ‖2] can be strictly reduced by moving the same amount of probability from {X̂ = x̂, Ŷ = ŷ} to {X̂ = x̂, Ŷ = ŷ′} and from {X̂ = x̂′, Ŷ = ŷ′} to {X̂ = x̂′, Ŷ = ŷ}. This modification does not affect pX̂ and pŶ , and consequently H(X̂), H(Ŷ ), E[‖X − X̂‖2], E[‖Y − Ŷ ‖2] remain the same. So the distortion-rate performance of this configuration is strictly suboptimal.
2. Support size = 2 and the existence of pairs (x̂, ŷ) and (x̂′, ŷ′) for some x̂ > x̂′ and ŷ < ŷ′: Same as configuration 1).
3. Support size = 2 and existence of pairs (x̂, 1) and (0, ŷ) for some x̂ ∈ (0, 1) and ŷ ∈ (0, 1): It follows by E[X|X̂] = X̂ and E[Y |Ŷ ] = Ŷ that
pX̂,Ŷ (x̂, 1) = qX x̂ , pX̂,Ŷ (0, ŷ) = 1− qX x̂ , ŷ = 1− 1− qY 1− qXx̂ .
Clearly, H(X̂) = H(Ŷ ) = Hb( qXx̂ ). Since x̂ ∈ (0, 1) and ŷ ∈ (0, 1), we must have qX < qX x̂ < qY , which implies H(X̂) = H(Ŷ ) > min{H(X), H(Y )}. Furthermore, it can be verified that
E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2]
= qX x̂ x̂(1− x̂) +
( 1− qX
x̂
) ŷ(1− ŷ) + qX
x̂ (1− x̂)2 +
( 1− qX
x̂
) ŷ2
= qY − qX .
However, this end-to-end distortion is obviously achievable when R = min{H(X), H(Y )}. So the rate-distortion performance of this configuration is strictly suboptimal.
4. Support size = 2 and the existence of pairs (x̂, 0) and (1, ŷ) for some x̂ ∈ (0, 1) and ŷ ∈ (0, 1): Same as configuration 3).
In view of the excluded configurations, we are left with the case where pX̂Ŷ assigns all probabilities to {X̂ = 0, Ŷ = 0}, {X̂ = 1, Ŷ = 1}, and {X̂ = x̂, Ŷ = ŷ} for some x̂ ∈ [0, 1] and ŷ ∈ [0, 1]. So it suffices to consider the N = 3 version of (P) with x̂1 = ŷ1 = 0, x̂3 = ŷ3 = 1, x̂2 = x̂, and ŷ2 = ŷ. The constraints ∑3 i=1 θi = 1, ∑3 i=1 θix̂i = qX , and ∑3 i=1 θiŷi = qY imply
θ1 = 1− qX − (1− x̂)θ, θ3 = qX − x̂θ, ŷ = qY − qX
θ + x̂.
In this way, we get a simplified optimization problem (P’):
min θ,x̂
2x̂(1− x̂)θ + (1− 2x̂)(qY − qX) (P’)
s.t. (1− qX − (1− x̂)θ) log 1
1− qX − (1− x̂)θ + θ log
1 θ + (qX − x̂θ) log
1
qX − x̂θ ≤ R,
x̂ ∈ [0, 1], θ ∈ [0, 1], (1− x̂)θ ∈ [qY − qX , 1− qX ], x̂θ ∈ [qX − qY , qX ].
Note that (P’) does not depend on and consequently yields the exact characterization of Dncr(B(qX),B(qY ), R). Therefore, Rncr(B(qX),B(qY ), D) is characterized by the following optimization problem (P”):
min θ,x̂
(1− qX − (1− x̂)θ) log 1
1− qX − (1− x̂)θ + θ log
1 θ + (qX − x̂θ) log
1
qX − x̂θ (P”)
s.t. 2x̂(1− x̂)θ + (1− 2x̂)(qY − qX) ≤ D, x̂ ∈ [0, 1], θ ∈ [0, 1], (1− x̂)θ ∈ [qY − qX , 1− qX ], x̂θ ∈ [qX − qY , qX ].
Given x̂, the objective function of (P”) is concave in θ and consequently its minimum is attained at an endpoint of [θ, θ], where
θ , max { 0, qY − qX
1− x̂ , qX − qY x̂
} ,
θ , min { 1,
1− qX 1− x̂ , qX x̂ , D − (1− 2x̂)(qY − qX) 2x̂(1− x̂)
} .
Without loss of generality, we assume qY ≥ qX and qX + qY ≤ 1. The following statements can be easily verified.
1. For x̂ ∈ [0, D+qX−qY2(1−qY ) ],
θ = qY − qX
1− x̂ ,
θ = 1− qX 1− x̂ .
2. For x̂ ∈ (D+qX−qY2(1−qY ) , qX+qY −D 2qY ],
θ = qY − qX
1− x̂ ,
θ = D − (1− 2x̂)(qY − qX)
2x̂(1− x̂) .
3. For x̂ ∈ ( qX+qY −D2qY , qX qY ],
θ = qY − qX
1− x̂ ,
θ = qX x̂ .
4. For x̂ > qXqY , [θ, θ] is empty.
Note that when x̂ ∈ [0, qXqY ] and θ = θ,
(1− qX − (1− x̂)θ) log 1
1− qX − (1− x̂)θ + θ log
1 θ + (qX − x̂θ) log
1
qX − x̂θ
= (1− qY ) log 1
1− qY + θ log
1 θ + (qX − x̂θ) log
1
qX − x̂θ ≥ Hb(qY ) = H(Y ).
So it suffices to consider the case x̂ ∈ [0, qXqY ] and θ = θ, for which (P”) is reduced to the following form:
min x̂∈[0, qXqY ] η(x̂),
where
η(x̂) ,    1−qX 1−x̂ log 1−x̂ 1−qX + qX−x̂ 1−x̂ log 1−x̂ qX−x̂ , x̂ ∈ [0, D+qX−qY 2(1−qY ) ], 2x̂−qX+(1−2x̂)qY −D 2x̂ log 2x̂ 2x̂−qX+(1−2x̂)qY −D +D−(1−2x̂)(qY −qX)2x̂(1−x̂) log 2x̂(1−x̂) D−(1−2x̂)(qY −qX) + qX+(1−2x̂)qY −D2(1−x̂) log 2(1−x̂) qX+(1−2x̂)qY −D , x̂ ∈ ( D+qX−qY 2(1−qY ) , qX+qY −D 2qY
], x̂−qX x̂ log x̂ x̂−qX + qX x̂ log x̂ qX , x̂ ∈ ( qX+qY −D2qY , qX qY ].
Note that η(x̂) is a continuous function over [0, qXqY ]. Moreover, η(x̂) decreases monotonically from Hb(qX) to Hb( D(B)max−D
2−qX−qY −D ) as x̂ varies from 0 to D+qX−qY 2(1−qY ) . Since η(x̂) is a concave function of
qX x̂ for x̂ ∈ [ qX+qY −D 2qY , qXqY ], it follows that
min x̂∈[ qX+qY −D2qY , qX qY ] η(x̂) = min
{ η( qX + qY −D
2qY ), η( qX qY )
} = min { Hb(
2qXqY qX + qY −D ), Hb(qY )
} .
So we have
min x̂∈[0,D+qX−qY
2(1−qY ) ]∪[ qX+qY −D2qY , qX qY ]
η(x̂)
= min { Hb(
D (B) max −D
2− qX − qY −D ), Hb( 2qXqY qX + qY −D ), Hb(qY )
}
= min { Hb(
D (B) max −D
2− qX − qY −D ), Hb( 2qXqY qX + qY −D )
} (33)
= min { η( D + qX − qY
2(1− qY ) ), η( qX + qY −D 2qY )
}
≥ min x̂∈[ D+qX−qY
2(1−qY ) , qX+qY −D 2qY ]
η(x̂),
where (33) is due to the fact that Hb(qY ) ≥ Hb(qX) ≥ Hb( D (B) max−D
2−qX−qY −D ) (with the first inequality being a consequence of qX ≤ qY and qX + qY ≤ 1). So the problem boils down to solving
min x̂∈[ D+qX−qY
2(1−qY ) , qX+qY −D 2qY ]
η(x̂).
It can be verified that the minimum is attained at x̂ = D+qX−qY2(1−qY ) . This completes the proof of (21). A graphical illustration of the entropy-constrained optimal transport plan for the binary case can be found in Figure 6.
Proof of (22). Note that
Dmse(B(qX), R) = 1
2 Dncr(B(qX),B(qX), R)
=    − (1−qX) 2 1−H−1b (R) + 1− qX , qX ≤ 12 ,
− q 2 X
1−H−1b (R) + qX , qX >
1 2 ,
R ∈ [0, Hb(qX)],
Dmse(B(qY ), R) = 1
2 Dncr(B(qY ),B(qY ), R)
=    − (1−qY ) 2 1−H−1b (R) + 1− qY , qY ≤ 12 ,
− q 2 Y
1−H−1b (R) + qY , qY >
1 2 ,
R ∈ [0, Hb(qY )].
Moreover, we have{ pX̂∗(
qX−H−1b (R) 1−H−1b (R) ) = 1−H−1b (R), pX̂∗(1) = H −1 b (R), R ∈ [0, Hb(qX)], qX ≤ 1 2 ,
{ pX̂∗(0) = H −1 b (R),
pX̂∗( qX 1−H−1b (R) ) = 1−H−1b (R),
R ∈ [0, Hb(qX)], qX ≥ 1
2 ,
{ pŶ ∗(
qY −H−1b (R) 1−H−1b (R) ) = 1−H−1b (R), pŶ ∗(1) = H −1 b (R), R ∈ [0, Hb(qY )], qY ≤ 1 2 ,
{ pŶ ∗(0) = H −1 b (R),
pŶ ∗( qY 1−H−1b (R) ) = 1−H−1b (R),
R ∈ [0, Hb(qY )], qY ≥ 1
2 .
So W 22 (pX̂∗ , pŶ ∗)
=    (qX−qY )2 1−H−1b (R) , qX , qY ≤ 12 or qX , qY ≥ 1 2 , (qY −qX+H−1b (R))2 1−H−1b (R) +H−1b (R)− 2qY (1−qX)H−1b (R) (1−H−1b (R))2 , qX < 1 2 , qY > 1 2 ,
(qX−qY +H−1b (R))2 1−H−1b (R) +H−1b (R)− 2qX(1−qY )H−1b (R) (1−H−1b (R))2 , qX > 1 2 , qY < 1 2 .
Based on the above expressions, one can easily verify (22) and (23). In particular, it is worth noting that when qX , qY ≤ 12 or qX , qY ≥ 1 2 ,
Dncr(B(qX),B(qY ), R) = Dncr(B(qX),B(qY ), R), R ∈ [0,min{Hb(qX), Hb(qY )}], i.e., there is no penalty for using optimal quantizer and dequantizer in the conventional rate-distortion sense.
Remark: It is easy to verify that
Dcr(B(qX), R) , min qY ∈[0,1] Dcr(B(qX),B(qY ), R)
=    qX ( 1− RHb(qX) ) , R ∈ [0, Hb(qX)], qX ≤ 12 , (1− qX) ( 1− RHb(qX) ) , R ∈ [0, Hb(qX)], qX > 12 ,
Dncr(B(qX), R) , min qY ∈[0,1] Dncr(B(qX),B(qY ), R)
=
{ qX −H−1b (R), R ∈ [0, Hb(qX)], qX ≤ 1 2 ,
1− qX −H−1b (R), R ∈ [0, Hb(qX)], qX > 1 2 ,
which are respectively the conventional one-shot distortion-distortion function (or equivalently, oneshot distortion-rate-perception function with an inactive perception constraint) for B(qX) with and without common randomness. In general, Dncr(B(qX), R) is different from Dmse(B(qX), R) (the former is strictly above the latter). The reason is as follows: even though the output distribution constraint is removed in the definition of Dncr(B(qX), R), the output alphabet remains to be {0, 1}; in contrast, for Dmse(B(qX), R), the output alphabet is relaxed to R.

heading: A.5 AUXILIARY RESULTS
text: Lemma 1 (Finite Support Approximation). For any R ≥ 0 and > 0, there exists a joint distribution pX,X̂,Ŷ ,Y compatible with the given marginal distributions pX and pY such that X ↔ X̂ ↔ Ŷ ↔ Y form a Markov chain and X̂ is a finite-support random variable with H(X̂) ≤ R (or Ŷ is a finitesupport random variable with H(Ŷ ) ≤ R); moreover, E[X|X̂] = X̂ , E[Y |Ŷ ] = Ŷ , and
E[‖X − X̂‖2] + E[‖Y − Ŷ ‖] + E[‖X̂ − Ŷ ‖2] ≤ Dncr(pX , pY , R) + .
Proof. In light of Theorem 1, we can find pX,X̂,Ŷ ,Y such that X ↔ X̂ ↔ Ŷ ↔ Y form a Markov chain, H(X̂) ≤ R, E[X|X̂] = X̂ , E[Y |Ŷ ], and
E[‖X − X̂‖2] + E[‖Y − Ŷ ‖] + E[‖X̂ − Ŷ ‖2] ≤ Dncr(pX , pY , R) + 2 . (34)
The proof is complete if X̂ is a finite-support random variable. So it suffices to consider the case where X̂ takes value from some countably infinite set {x̂i}∞i=1. Since E[‖X‖2] <∞ and E[‖Y ‖2] <∞, it follows that there exists a positive integer N such that
P{X̂ ∈ {x̂i}∞i=N}E[‖X‖2 + ‖Y ‖2|X̂ ∈ {x̂i}∞i=N ] ≤
4 .
Let X̂ ′ , X̂ if X̂ ∈ {x̂i}N−1i=1 and X̂ ′ , E[X|X̂ ∈ {x̂i}∞i=N ] if X̂ ∈ {x̂i}∞i=N . Note that
E[‖X − X̂ ′‖2] + E[‖X̂ ′ − Ŷ ‖2] = P{X̂ ∈ {x̂i}N−1i=1 }E[‖X − X̂
′‖2 + ‖X̂ ′ − Ŷ ‖2|X̂ ∈ {x̂i}N−1i=1 ] + P{X̂ ∈ {x̂i}∞i=N}E[‖X − X̂ ′‖2 + ‖X̂ ′ − Ŷ ‖2|X̂ ∈ {x̂i}∞i=N ]
= P{X̂ ∈ {x̂i}N−1i=1 }E[‖X − X̂‖ 2 + ‖X̂ − Ŷ ‖2|X̂ ∈ {x̂i}N−1i=1 ]
+ P{X̂ ∈ {x̂i}∞i=N}E[‖X − X̂ ′‖2 + ‖X̂ ′ − Ŷ ‖2|X̂ ∈ {x̂i}∞i=N ] ≤ P{X̂ ∈ {x̂i}N−1i=1 }E[‖X − X̂‖
2 + ‖X̂ − Ŷ ‖2|X̂ ∈ {x̂i}N−1i=1 ] + P{X̂ ∈ {x̂i}∞i=N}E[‖X − X̂ ′‖2 + 2‖X̂ ′‖2 + 2‖Ŷ ‖2|X̂ ∈ {x̂i}∞i=N ] ≤ P{X̂ ∈ {x̂i}N−1i=1 }E[‖X − X̂‖
2 + ‖X̂ − Ŷ ‖2|X̂ ∈ {x̂i}N−1i=1 ] + P{X̂ ∈ {x̂i}∞i=N}E[‖X‖2 + ‖X̂ ′‖2 + 2‖Ŷ ‖2|X̂ ∈ {x̂i}∞i=N ] ≤ E[‖X − X̂‖2 + ‖X̂ − Ŷ ‖2] + 2P{X̂ ∈ {x̂i}∞i=N}E[‖X‖2 + ‖Y ‖2|X̂ ∈ {x̂i}∞i=N ]
≤ E[‖X − X̂‖2] + E[‖X̂ − Ŷ ‖2] + 2 . (35)
Now define a new joint distribution pX,X̂′′,Ŷ ′′,Y such that pX,X̂′′ = pX,X̂′ , pX̂′′,Ŷ ′′ = pX̂′,Ŷ , pY,Ŷ ′′ = pY,Ŷ , and X ↔ X̂ ′′ ↔ Ŷ ′′ ↔ Y form a Markov chain. It is clear that X̂ ′′ is a finitesupport random variable with H(X̂ ′′) = H(X̂ ′) ≤ H(X̂) ≤ R, E[X|X̂ ′′] = X̂ ′′, E[Y |Ŷ ′′] = Ŷ ′′, and
E[‖X − X̂ ′′‖2] + E[‖Y − Ŷ ′′‖] + E[‖X̂ ′′ − Ŷ ′′‖2] ≤ E[‖X − X̂ ′‖2] + E[‖Y − Ŷ ‖] + E[‖X̂ ′ − Ŷ ‖2]
≤ E[‖X − X̂‖2] + E[‖Y − Ŷ ‖] + E[‖X̂ − Ŷ ‖2] + 2
(36)
≤ Dncr(pX , pY , R) + , (37)
where (36) and (37) are due to (34) and (35), respectively. This completes the proof of Lemma 1.
Lemma 2 (Deterministic on Finite Support). Let X ↔ X̂ ↔ Ŷ ↔ Y be a Markov chain with E[X|X̂] = X̂ , E[Y |Ŷ ] = Ŷ , and assume that X̂ (or Ŷ ) is a finite-support random variable. There exist deterministically related random variables X̂ ′ and Ŷ ′, with the support size no greater than that of
qX + qY ≤ 1), where pX̂(x̂) = pŶ (ŷ) = 1−H −1 b (R) with x̂ = qX−H−1b (R) 1−H−1b (R) and ŷ = qY −H −1 b (R) 1−H−1b (R) . It is interesting to note that the quantizer pX̂|X does not depend on pY while the dequantizer pY |Ŷ does not depend on pX . So they are decoupled in a certain sense. Moreover, pX̂|X and pY |Ŷ coincide respectively with optimal quantizer pX̂∗|X and dequantizer pY |Ŷ ∗ in the conventional rate-distortion sense when qX , qY ≤ 1/2.
X̂ and H(X̂ ′) = H(Ŷ ′) ≤ H(X̂) (or H(X̂ ′) = H(Ŷ ′) ≤ H(Ŷ )), such that X ↔ X̂ ′ ↔ Ŷ ′ ↔ Y form a Markov chain, E[X|X̂ ′] = X̂ ′, E[Y |Ŷ ′] = Ŷ ′, and
E[‖X − X̂ ′‖2] + E[‖Y − Ŷ ′‖] + E[‖X̂ ′ − Ŷ ′‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖] + E[‖X̂ − Ŷ ‖2].
Proof. Let Ỹ , E[Y |X̂]. Since Ỹ ↔ Ŷ ↔ Y form a Markov chain and E[Y |Ŷ ] = Ŷ , we have Ỹ = E[Ŷ |X̂]. Construct a new joint distribution pX,X̂′,Ŷ ′,Y such that pX,X̂′ = pX,X̂ , pX̂′,Ŷ ′ = pX̂,Ỹ , pY,Ŷ ′ = pY,Ỹ , and X ↔ X̂ ′ ↔ Ŷ ′ ↔ Y form a Markov chain. It is clear that E[X|X̂ ′] = X̂ ′, E[Y |Ŷ ′] = Ŷ ′, and
E[‖X − X̂ ′‖2] + E[‖Y − Ŷ ′‖2] + E[‖X̂ ′ − Ŷ ′‖2] = E[‖X − X̂‖2] + E[‖Y − Ỹ ‖2] + E[‖X̂ − Ỹ ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖Ŷ − Ỹ ‖2] + E[‖X̂ − Ỹ ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2],
where the last equality is due to Ỹ = E[Ŷ |X̂]. If the function that maps X̂ ′ to Ŷ ′ (or equivalently, maps X̂ to Ỹ ) is invertible, then X̂ , X̂ ′, Ŷ ′ have the same support size and H(X̂) = H(X ′) = H(Y ′), which completes the proof. Otherwise, the support size of Ŷ ′ must be strictly smaller than that of X̂ ′ (which is the same as that of X̂) and H(Ŷ ′) < H(X̂ ′) = H(X̂). We can alternately reduce the support sizes of X̂ ′ and Ŷ ′ using this argument until they are deterministically related (and consequently have the same support size and the same entropy). This can be accomplished in a finite number of steps because the reduction in support size cannot continue forever.

heading: A.6 UNIFORM DISTRIBUTION
text: Let X ∼ Unif[0, a] and Y ∼ Unif[0, b] be uniformly distributed random variables, where a, b > 0. Note that the density functions are given as: pX(x) = 1a , 0 ≤ x ≤ a and pY (y) = 1 b , 0 ≤ y ≤ b and pX(x) and pY (y) are zero outside these intervals. The cumulative density functions of X and Y are
given as follows:
CX(x) =   
0, x ≤ 0, x a , 0 ≤ x ≤ a, 1, x ≥ a,
CY (y) =   
0, y ≤ 0, y b , 0 ≤ y ≤ b, 1, y ≥ b.
Following Peyré & Cuturi (2019, Remark 2.30) we have that the optimal transport (without rate constraint) is given by:
W 22 (pX , pY ) =
∫ 1
0
(C−1X (r)− C −1 Y (r))
2dr = (b− a)2
3 , (38)
where C−1X (·) and C −1 Y (·) are the pseudo-inverse of the CDF functions for X and Y as defined in Peyré & Cuturi (2019, Remark 2.30).
We will next develop an upper bound on Dncr(pX , pY , R) using Theorem 1 when the rate is of the form R = log2(N) for any N ∈ {1, 2, . . .}, by considering the following choice for X̂ and Ŷ :
X̂ ∈ X̂ = { a
2N ,
3a 2N , 5a 2N , . . . , (2N − 1)a 2N
} , (39)
Ŷ ∈ Ŷ = { b
2N ,
3b
2N ,
5b
2N , . . . , (2N − 1)b 2N
} . (40)
To compute the upper bound we select pX̂|X to correspond to scalar quantization of X i.e., given X we select X̂ as a point in X̂ closest to X . The distribution pŶ |Y is defined in an analogous manner3 . Our upper bound can be computed as:
D+ncr(pX , pY , R) = E[(X − X̂)2] + E[(Y − Ŷ )2] +W 22 (pX̂ , pŶ ). (41)
Note that with ∆ = 1N we have that E[(X − X̂) 2] = a
2∆2 12 and E[(Y − Ŷ ) 2] = b 2∆2
12 . Thus we only need to compute the third term. Following Peyré & Cuturi (2019, Remark 2.28) we have that:
W 22 (pX̂ , pŶ ) = (b− a)2∆2
4N
N∑
i=1
(2i− 1)2 = (b− a) 2
3
( 1− ∆ 2
4
) . (42)
Thus using ∆2 = 2−2R, we have that
D+ncr(pX , pY , R) = (b− a)2 3 + a · b 6 2−2R. (43)
Note that the upper bound approaches the lower bound in (38) as R→∞, with exponential rate of convergence.
For the case of general R, we let N = d2Re and following Gyorgy & Linder (2000, Theorem 1), we select
X̂ ∈ X̂ =    ac
2︸︷︷︸ x̂1
, a ( c+ c′
2
)
︸ ︷︷ ︸ x̂2
, a ( c+ 3 c′
2
)
︸ ︷︷ ︸ x̂3
, . . . , a ( c+ (2N − 3)c ′
2
)
︸ ︷︷ ︸ x̂N
   ,
Ŷ ∈ Ŷ =    bc
2︸︷︷︸ ŷ1
, b ( c+ c′
2
)
︸ ︷︷ ︸ ŷ2
, b ( c+ 3 c′
2
)
︸ ︷︷ ︸ ŷ3
, . . . , b ( c+ (2N − 3)c ′
2
)
︸ ︷︷ ︸ ŷN
   ,
(44)
3Please note that we do not claim that the proposed choice is optimal with respect to Dmse in (4) although it is known to be optimal solution for a related problem - the entropy constrained scalar quantization (Gyorgy & Linder (2000)). As a result we cannot claim to compute the upper bound D̄ncr stated Theorem 1 but provide another upper bound.
where c is the unique solution in the interval (0, 1/N ] to the equation:
−c log c− (1− c) log (1− c) N − 1 = R,
and c′ = (1−c)N−1 holds. Note that the length of the first interval is c and the length of all other intervals is c′. In the special case where R = log2N we will have that c = c
′ = 1N and our construction for X̂ and Ŷ is consistent with the previous case.
As before we use pX̂|X and pŶ |Y to be the distributions associated with scalar quantization. Thus we have that:
E[(X − X̂)2] = ca 2c2 12 + (1− c)a
2c′2 12 , (45)
E[(Y − Ŷ )2] = cb 2c2 12 + (1− c)b
2c′2 12 . (46)
Furthermore using the result stated in Peyré & Cuturi (2019, Remark 2.30) we have that
W 22 (pX̂ , pŶ ) = c(x̂1 − ŷ1) 2 + c′
N∑
j=2
(x̂j − ŷj)2 (47)
= (b− a)2 c 3
4 + (b− a)2c′
N−1∑
j=1
( c+
2j − 1 2
c′ )2
(48)
= (b− a)2 ( c3
4 + c2c′(N − 1) + cc′2(N − 1)2 + 1 12 c′3(2N − 1)(2N − 3)(N − 1)
) .
(49)
Finally, the upper bound D+ncr(pX , pY , R) can be obtained by summing the right hand side of (45), (46) and (49). We provide a numerical evaluation of this upper bound in Fig. 7.

heading: A.7 ASYMPTOTIC OPTIMAL TRANSPORT
text: Let X1, X2, · · · and Y1, Y2, · · · be i.i.d. processes with marginal distributions pX and pY , respectively.
Definition 4 (Asymptotic Optimal Transport with Entropy Bottleneck — no common randomness). The asymptotic optimal transport from pX to pY with an entropy bottleneck of R and without common randomness is defined as
D(∞)ncr (pX , pY , R) , inf n≥1 D(n)ncr(pX , pY , R),
where
D(n)ncr(pX , pY , R) , inf pXn,Z,Y n∈Mncr(⊗ni=1pX ,⊗ni=1pY )
1
n
n∑
i=1
E[d(Xi, Yi)]
s.t. 1
n H(Z) ≤ R.
Remark: It is clear that D(1)ncr(pX , pY , R) = Dncr(pX , pY , R). Moreover, one can readily show that {nD(n)ncr(pX , pY , R)}∞n=1 is a subadditive sequence and consequently D (∞) ncr (pX , pY , R) = limn→∞D (n) ncr(pX , pY , R).
Theorem 5. We have
D(∞)ncr (pX , pY , R) = inf pX,Z,Y ∈Mncr(pX ,pY ) E[d(X,Y )]
s.t. max{I(X;Z), I(Y ;Z)} ≤ R.
Proof. This result can be specialized from Theorem 1 in Saldi et al. (2015b).
The following result is the counterpart of Theorem 1 in the asymptotic setting.
Theorem 6. Let
D(∞)mse (pX , pY , R) , inf pX̂|X ,pŶ |Y E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] +W 22 (pX̂ , pŶ )
s.t. E[X|X̂] = X̂, E[Y |Ŷ ] = Ŷ , I(X; X̂) ≤ R, I(Y ; Ŷ ) ≤ R, (50)
and Dmse(pX , R) , inf
pX̂|X E[‖X − X̂‖2]
s.t. I(X; X̂) ≤ R. (51)

heading: Moreover, let
text: D (∞) ncr (pX , pY , R) , D (∞) mse (pX , R) +D (∞) mse (pY , R) +W 2 2 (pX̂∗ , pŶ ∗), (52) D(∞)ncr (pX , pY , R) , D (∞) mse (pX , R) +D (∞) mse (pY , R), (53)
where pX̂∗ and pŶ ∗ are the marginal distributions induced by the minimizers pX̂∗|X and pŶ ∗|Y that attain D(∞)mse (pX , R) and D (∞) mse (pY , R), respectively (assuming the existence and uniqueness of such minimizers). Then under the squared Eucledian distortion measure,
D(∞)ncr (pX , pY , R) = D (∞) mse (pX , pY , R). (54)
In addition, we have
D (∞) ncr (pX , pY , R) ≥ D(∞)ncr (pX , pY , R) ≥ D (∞) ncr (pX , pY , R), (55)
and both inequalities are tight when pX = pY .
Proof. For any pX,Z,Y ∈Mncr(pX , pY ) with max{I(X;Z), I(Y ;Z)} ≤ R,
E[‖X − Y ‖2] = E[‖X − E[X|Z]‖2] + E[‖Y − E[Y |Z]‖2] + E[‖E[X|Z]− E[Y |Z]‖2]
≥ D(∞)mse (pX , pY , R),
where the last inequality follows from the definition of D(∞)mse (pX , pY , R) and the fact that
max{I(X;E[X|Z]), I(Y ;E[Y |Z]} ≤ max{I(X;Z), I(Y ;Z)} ≤ R.
In view of Theorem 5, we must have D(∞)ncr (pX , pY , R) ≥ D(∞)mse (pX , pY , R). On the other hand, for any pX̂|X , pŶ |Y with E[X|X̂] = X̂ , E[Y |Ŷ ] = Ŷ , I(X; X̂) ≤ R, and I(Y ; Ŷ ) ≤ R, we can construct a joint distribution pX,X̂,Ŷ ,Y such that X ↔ X̂ ↔ Ŷ ↔ Y form a Markov chain, pX,X̂ = pXpX̂|X , pY,Ŷ = pY pŶ |Y , and pX̂,Ŷ satisfying E[‖X̂ − Ŷ ‖2] = W 22 (pX̂ , pŶ ). Note that
E[‖X − Y ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] + E[‖X̂ − Ŷ ‖2] = E[‖X − X̂‖2] + E[‖Y − Ŷ ‖2] +W 22 (pX̂ , pŶ ). (56)
Let Z , X̂ . It can be verified that pX,Z,Y ∈ Mncr(pX , pY ) and max{I(X;Z), I(Y ;Z)} = max{I(X; X̂), I(Y ; X̂)} ≤ max{I(X; X̂), I(Y ; Ŷ )} ≤ R, which, together with (56), implies D (∞) ncr (pX , pY , R) ≤ D(∞)mse (pX , pY , R). This completes the proof of (54).
Dropping the term W 22 (pX̂ , pŶ ) in (50) yields
D(∞)ncr (pX , pY , R) ≥ D̃(∞)mse (pX , R) + D̃(∞)mse (pY , R),
where
D̃(∞)mse (pX , R) , inf pX̂|X E[‖X − X̂‖2]
s.t. E[X|X̂] = X̂, I(X; X̂) ≤ R.
and D̃mse(pY , R) is definely analogously. On the other hand, choosing pX̂|X = pX̂′|X and pŶ |Y = pŶ ′|Y in (50) gives
D(∞)ncr (pX , pY , R) ≤ D̃(∞)mse (pX , R) + D̃(∞)mse (pY , R) +W 22 (pX̂′ , pŶ ′),
where pX̂′|X and pŶ ′|Y are the minimizers that attain D̃ (∞) mse (pX , R) and D̃ (∞) mse (pY , R) respectively while pX̂′ and pŶ ′ are their induced marginal distributions. It is clear that pX̂′|X and pŶ ′|Y coincide with pX̂∗|X and pŶ ∗|Y respectively as the constraints E[X|X̂] = X̂ and E[Y |Ŷ ] = Ŷ are automatically satisfied by pX̂∗|X and pŶ ∗|Y . This proves (55). For the special case pX = pY , we have pX̂∗|X = pŶ ∗|Y and consequently the upper bound and the lower bound in (55) coincide.
Definition 5 (Asymptotic Optimal Transport with Entropy Bottleneck — with Common Randomness). The asymptotic optimal transport from pX to pY with entropy bottleneck R and common randomness is defined as
D(∞)cr (pX , pY , R) , inf n≥1 D(n)cr (pX , pY , R),
where
D(n)cr (pX , pY , R) , inf pU,Xn,Z,Y n∈Mcr(⊗ni=1pX ,⊗ni=1pY )
1
n
n∑
i=1
E[d(Xi, Yi)]
s.t. 1
n H(Z|U) ≤ R.
Remark: It is clear that D(1)cr (pX , pY , R) = Dcr(pX , pY , R). Moreover, one can readily show that {nD(n)cr (pX , pY , R)}∞n=1 is a subadditive sequence and consequently D (∞) cr (pX , pY , R) = limn→∞D (n) ncr(pX , pY , R).
Theorem 7. We have
D(∞)cr (pX , pY , R) = inf pX,Y ∈Γ(pX ,pY ) E[d(X,Y )]
s.t. I(X;Y ) ≤ R.
Proof. This result is known (see Theorem 7 in Saldi et al. (2015a)). It is possible to give a simpler proof of the achievability part by leveraging Theorem 3 and the strong data processing inequality Li & El Gamal (2018). The converse is based on standard information-theoretic arguments.

heading: A.8 GAUSSIAN CASE
text: Let X ∼ N (µX , σ2X) and Y ∼ N (µY , σ2Y ) be two Gaussian random variables, and let d(·, ·) be the squared distortion measure (i.e., d(x, y) = (x− y)2). Let D(G)min , (µX − µY )2 + (σX − σY )2 and D(G)max , (µX − µY )2 + σ2X + σ2Y . Note that D (G) min is the squared Wasserstein-2 distance between N (µX , σ2X) and N (µY , σY ), which is the minimum E[(X − Y )2] achievable by coupling X and Y . On the other hand, we have E[(X − Y )2] = D(G)max for X , Y independent. It is clear that D
(G) min and D (G) max are the infimum and supremum of D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R) (as well as
D (∞) cr (N (µX , σ2X),N (µY , σ2Y ), R)), respectively.
Theorem 8. Assume squared distortion measure. Under no common randomness, we have
D(∞)ncr (N (µX , σ2X),N (µY , σ2Y ), R) = D (G) min + 2σXσY 2 −2R, R ∈ [0,∞). (57)

heading: Moreover,
text: D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R) = D(∞)ncr (N (µX , σ2X),N (µY , σ2Y ), R), R ∈ [0,∞), (58) D(∞)ncr (N (µX , σ2X),N (µY , σ2Y ), R) = (σ2X + σ2Y )2−2R, R ∈ [0,∞). (59)

heading: With common randomness,
text: D(∞)cr (N (µX , σ2X),N (µY , σ2Y ), R) = D(G)max − 2σXσY √ 1− 2−2R, R ∈ [0,∞). (60)
Proof. Consider pX̂|X and pŶ |Y such that E[X|X̂], E[Y |Ŷ ], I(X; X̂) ≤ R, and I(Y ; Ŷ ) ≤ R. Denote the mean and the variance of X̂ by µX̂ and σ 2 X̂ , respectively. Similarly, denote the mean and the variance of Ŷ by µŶ and σ 2 Ŷ , respectively. Clearly, µX̂ = µX , µŶ = µY , σ 2 X̂
= σ2X − E[(X − X̂)2], and σ2
Ŷ = σ2Y − E[(Y − Ŷ )2]. Moreover,
W 22 (pX̂ , pŶ ) ≥W 2 2 (N (µX̂ , σ 2 X̂ ),N (µŶ , σ 2 Ŷ ))
= (µX̂ − µŶ ) 2 + (σX̂ − σŶ ) 2 = (µX − µY )2 + (σX̂ − σŶ ) 2.
So we have
E[(X − X̂)2] + E[‖Y − Ŷ ‖2] +W 22 (pX̂ , pŶ ) ≥ σ2X − σ2X̂ + σ 2 Y − σ2Ŷ + (µX − µY ) 2 + (σX̂ − σŶ ) 2
= D(G)max − 2σX̂σŶ . (61)
It can be verified that
R ≥ I(X; X̂)
= 1
2 log(2πeσ2X)− h(X|X̂)
≥ 1 2 log(2πeσ2X)− h(X − X̂)
≥ 1 2 log(2πeσ2X)− 1 2 log(2πeE[(X − X̂)2])
= 1
2 log σ2X σ2X − σ2X̂ ,
which implies
σX̂ ≤ σX √ 1− 2−2R. (62)
Similarly,
σŶ ≤ σY √ 1− 2−2R. (63)
Substituting (62) and (63) into (61) and invoking (54) in Theorem 6 shows
D(∞)ncr (N (µX , σ2X),N (µY , σ2Y ), R) ≥ D (G) min + 2σXσY 2 −2R.
To see that this lower bound is tight, we can let
X = X̂ +N, (64)
Y = Ŷ + N̂ , (65)
where X̂ ∼ N (µX , σ2X(1 − 2−2R)) is independent of N ∼ N (0, σ2X2−2R) while Ŷ ∼ N (µY , σ2Y (1− 2−2R)) is independent of N̂ ∼ N (0, σ2Y 2−2R). This completes the proof of (57).
To prove (58) and (59), it suffices to note the well-known fact that pX̂|X and pŶ |Y associated with (64) and (65) attain D(∞)mse (N (µX , σ2X), R) and D (∞) mse (N (µY , σ2Y ), R), respectively.
Now we proceed to prove (60). Consider pX,Y ∈ Γ(N (µX , σ2X),N (µY , σ2Y )) with I(X;Y ) ≤ R. Let ξ , E[(X − µX)(Y − µY )]. We have
E[(X − Y )2] = D(G)max − 2ξ. (66)
Moreover,
R ≥ I(X;Y )
= 1
2 log(2πeσ2X) +
1 2 log(2πeσ2Y )− h(X,Y )
≥ 1 2 log(2πeσ2X) + 1 2 log(2πeσ2Y )− 1 2 log((2πe)2(σ2Xσ 2 Y − ξ))
= 1
2 log
σ2Xσ 2 Y
σ2Xσ 2 Y − ξ2
,
which implies
ξ ≤ σXσY √ 1− 2−2R. (67)
Substituting (67) into (66) and invoking Theorem 7 shows
D(∞)cr (N (µX , σ2X),N (µY , σ2Y ), R) ≥ D(G)max − 2σXσY √ 1− 2−2R.
To see that this lower bound is tight, we can let X and Y be jointly Gaussian with ξ = σXσY √ 1− 2−2R. This completes the proof of Theorem 8. We acknowledge that the expression of D(∞)cr (N (µX , σ2X),N (µY , σ2Y ), R) was established in (Saldi et al., 2015b, Section IV-B) for the special case when the Gaussian distributions have zero mean. However, to the best of our understanding, they only provided an upper bound for the case of no common randomness .
In Figure 8, We plot D(∞)ncr (N (µX , σ2X),N (µY , σ2Y ), R), D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R), D(∞)ncr (N (µX , σ2X),N (µY , σ2Y ), R), and D (∞) cr (N (µX , σ2X),N (µY , σ2Y ), R) for two illustrative examples.
where D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R) and D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R) coincide with D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R); (b) µX = 0, σX = 1, µY = 1, σY = 2, where D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R) is tight but D (∞) ncr (N (µX , σ2X),N (µY , σ2Y ), R) is loose. Moreover, it can be seen from both examples that common randomness can indeed help improve the distortion-rate tradeoff.

heading: B EXPERIMENTAL RESULTS

heading: B.1 DATASET
text: Image super-resolution is conducted on MNIST (LeCun et al., 1998). For synthesizing low-resolution images, we perform bilinear downsampling on the original image from 28× 28 to 7× 7. The samples in Figure 5(b) show that the low resolution digits are blurry and some of them are hard to recognize. Image denoising is conducted on SVHN (Netzer et al., 2011). In our experiments, we synthesize the noisy image with additive Gaussian noise. The standard deviation is set to 20.

heading: B.2 UNIVERSAL QUANTIZATION
text: Let C be our codebook for quantization. Recall that the encoder uses a tanh activation so its output lies in (−1, 1)d. Given dimension d and L quantization levels per dimension as parameters, C will consist of L uniformly spaced intervals across all d dimensions. The upper bound of model rate is given by d log(L). With this codebook, universal quantization (Ziv, 1985; Gray & Stockham, 1993; Theis & Agustsson, 2021) is implemented as follows. We assume the sender and receiver have access to the same u ∼ U [−1/(L− 1),+1/(L− 1)]d. The sender computes
z = arg min c∈C
‖f(x) + u− c‖
and sends z to the receiver. The receiver decodes the image by passing z − u through the decoder. This is also known as a subtractive dither in literature (Gray & Stockham, 1993). For super-resolution and image denoising, the interval L is respectively fixed at 4 and 8.

heading: B.3 TRAINING DETAILS
text: To induce distributional shift, we use the Wasserstein GAN for our experiments. We alternate between training the encoder/decoder f, g, and the critic h. By Kantorovich-Rubinstein duality (Villani, 2009), the critic is used to approximate
W1(pY , pỸ ) = sup ‖∇h‖≤1
E[h(Y )]− E[h(Ỹ )], (68)
where Ỹ = g(Q(f(X)+U)−U) for U as in Appendix B.2. The Lipschitz constraint is implemented with a gradient penalty (Gulrajani et al., 2017) in practice.
Super-resolution. The training for end-to-end network lasts for 50 epochs. λ in (14) is fixed at 1e − 3 across all rates. The learning rate initialized to be 0.0001 and is decayed by a factor of 5 after 30 epochs. The Adam (Kingma & Ba, 2014) optimizer is used. Table 3 illustrates the detailed training setting. For the helper two-branch network at a specific rate constraint, we load the pre-trained encoder weight of the corresponding end-to-end network, as well as two randomly initialized decoders g1, g2. Note that only theese two decoders are trainable. During training, we use the Adam optimizer with the learning rate initialized at 0.0001. There are a total of 100 epochs until the convergence of the two decoders. The learning rate is decayed once at 50 epochs by a factor of 5. Detailed training settings are shown in Table 4.
Image Denoising. The experiments for image denoising share many settings with image superresolution. Tables 3 and 4 can be reused to reproduce the experiments on image denoising. Here, we list the difference between them. For denoising, the end-to-end model is trained for 100 epochs with λ fixed at 3e− 3 across all rates. The learning rate is decayed by a factor of 5 after 40 epochs. The two-branch model is trained for total 200 epochs and we decay the learning rate at 100 epochs by a factor of 5.

heading: B.4 DETAILED RESULTS IN FIGURE. 5
text: In Fig. 5(a)(c), we have provided a comparison between the case with or without common randomness in the form of a scatter chart. Here, we present detailed quantities of each point in Fig. 5(a)(c). Table 5 shows the number of each dot for super-resolution experiments, and Table 6 present the value of each dot for image denoising. From the two tables, we can further see the utility of common randomness quantitatively.

heading: B.5 COMPARISON WITH BASELINE
text: To illustrate the effectiveness of our system, we compare with a baseline method that separately deal with the tasks of image restoration and compression. For the restoration, we build an U-Net with skip connections and train it in the unsupervised manner by adopting the Eq. 14 as objective i.e.,
L1 = E[‖X − Ỹ ‖2] + λ1W1(pY , pỸ ). (69)
After the restoration network is trained to converge, we fix its weights and use it to produce restored images Ỹ given degraded one X . Afterwards, we adapt our end-to-end network as compression network by minimizing the following loss at different rates:
L1 = E[‖Ỹ − Y +‖2] + λW1(pY , pY +), (70)
where Y + is the outputs of compression network. Note that, to guarantee the distribution of reconstructed Y + is close to that of target images, we implement a penalty on the Wasserstein-1 distance in (69) and (70) where we experimentally selected λ1 = 0.05 and λ2 = 0.01. Once the compression network is converged, we report the final MSE distortion between Y + and X using E[‖X − Y +‖2].
The detailed results for entropy-constrained image super-resolution are shown in Table 7. It can easily check throughout the table that our end-to-end system outperforms the baseline by a large margin.

heading: B.6 COMPARISON WITH GROUND TRUTH
text: In order to illustrate the rate-distortion trade-offs, we report the MSE distortion that is measured between degraded input images and decoder outputs in Figure 5. Since the input and output distributions are different, we do not expect MSE→ 0 as the rate increases. The MSE distortion between degraded input and restored output is still able to reveal how much content information of the input is preserved in output (lower is better).
We now additionally show the MSE distortion between ground truth and decoder outputs in Tables 8 and 9. Concretely, we measure MSE distortion E[‖Y − Ỹ ‖2], where Y is ground truth and Ỹ is the network output. Note that for training, the ground truth is only used in an unsupervised fashion with unpaired noisy images, and here the ground truth-noisy image pairs are only used for test time evaluation. Note also that the MSE distortion is correspondingly lower if common randomness is adopted.

heading: B.6.1 BREAKDOWN OF THE TABLE 1
text: It is worth reminding that the each number in Table 1 is the total distortion 17. Here, we provide a breakdown of total distortion in each of the three term for joint training, i.e, E[‖X − Ỹ1‖2], E[‖Ỹ − Ỹ2‖2] and E[‖Ỹ1 − Ỹ2‖2].

heading: B.7 NETWORK ARCHITECTURE
text: Super-resolution. The detailed network structure for end-to-end model and two-branch model are respectively presented in Table 11 and Table 12. The last linear layer of the encoder controls the number of output symbols.
Denoising. The detailed network structure for end-to-end model and two-branch model are respectively presented in Table 13 and Table 14. The last linear layer of the encoder controls the number of output symbols.

Review summaries:
The paper explores the problem of learned compression scheme for the specific setup where the source and target distributions are not the same (such as in restoring a degraded image). The authors formulate the problem as an optimal transport problem with entropy constraints to control the compression rate. They further argue that the use of common randomness in the encoder and decoder improves the rate-distortion tradeoff and dcoument it on denoising and super-resolution experiments.

This paper addresses the problem of lossy compression when the source and target distributions differ. As example domains, the authors look at denoising (the distribution of noisy images and "clean" images are not the same) and super-resolution (again, the distribution of low-res and high-res images are different) both addressed as unsupervised learning problems, i.e. the noisy/clean and low/high-res training data are unpaired.  The problem is treated as optimal transport (to account for the domain shift) with an entropy bottleneck (to account for the rate constraint needed to achieve compression). The authors derive theoretical bounds for the achievable distortion in two scenarios (with and without a source of shared randomness between the sender and the receiver), and they show that a shared source of randomness strictly improves rate-distortion performance. The Wasserstein distance used in a Wasserstein GAN framework accounts for the distribution difference between the input and output domains.  

The paper focuses on a very particular kind of lossy compression, which they call "cross-domain lossy compression". It basically amounts to encode a degraded version of the signal at the encoder while being able to reconstruct some better version at the decoder, while maintaining interesting rate constraints. As such, this scenario puts together signal compression and denoising/super-resolution, so that I can definitely say it comes with interesting applications.  Technically, the authors show that the problem can be nicely formulated as a special kind of optimal transport under entropy constraints, which gives an interesting flavour to their contribution and much theoretical grounding for their proposed method.