# LOSSY COMPRESSION WITH DISTRIBUTION SHIFT AS ENTROPY CONSTRAINED OPTIMAL TRANSPORT

**Huan Liu[1][∗], George Zhang[2][∗], Jun Chen[1], Ashish Khisti[2]**

1McMaster University, 2University of Toronto
_{liuh127, chenjun}@mcmaster.ca_
gq.zhang@mail.utoronto.ca, akhisti@ece.utoronto.ca

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. 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 squaredEuclidean 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 suggesting consistency with our theoretical results.

1 INTRODUCTION

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

_∗Equal Contribution_


-----

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_ _X_
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_
_∼_ _Xˆ_
of interest. For example, if X denotes a noise-corrupted image   [] [] [] [] 

|X|Col2|
|---|---|

and Y denotes the associated clear reconstruction, then pY can be
selected to match the distribution of the original source. We willassume pX and pY are probability distributions over X _, Y ⊆_ R[n] _Yˆ_       

     

and require X and Y to be close with respect to some fidelity
metric, which will be measured using a non-negative cost function _Y_

|Y|Col2|Col3|Col4|
|---|---|---|---|

_dmeasure and assume that it satisfies(x, y) over X × Y. We will refer to d( dx, y(·,) = 0 ·) as the distortion if and only if_ Figure 1: Illustration of Theo_x = y. We further assume that X cannot be directly revealed to_ rem 1 (no common randomness).
the decoder, but instead must be transmitted over a bit interface Given source distribution pX, tarwith an average rate constraint. Such a scenario occurs naturally get reconstruction distribution pY
in many practical systems when the encoder and decoder are not and rate R, we can find quantizaco-located such as communication systems or storage systems. As tions _X[ˆ] of X and_ _Y[ˆ] of Y and_
one potential application, when aerial photographs are produced consider transport between them.
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.


-----

2.1 OPTIMAL TRANSPORT AND EXTENSIONS

**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 (1)
_pX,Y_ Γ(pX _,pY )_ [E][[][d][(][X, Y][ )]][,]
_∈_

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 = pX _pZ_ _X_ _pY_ _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][ )]] (2)

s.t. _H(Z) ≤_ _R,_

where H(·) denotes the Shannon entropy of a random variable.

We note that when the rate constraint R 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 R[1].

Of particular interest to us is the squared Euclidean distance d(X, Y ) = ||X − _Y ||[2]. As it turns out,_
when we specialize to this distance function we can without loss of optimality also impose a more
structured architecture for implementing the encoder and the decoder. Let W2[2][(][·][,][ ·][)][ be the squared]
quadratic Wasserstein distance, by using the squared loss in Definition 1.

**Theorem 1. Let**

_Dmse(pX_ _, pY, R) ≜_ _p ˆX_ _Xinf[,p][ ˆ]Y_ _Y_ E[∥X − _X[ˆ]_ _∥[2]] + E[∥Y −_ _Y[ˆ] ∥[2]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)]
_|_ _|_ (3)

_s.t._ E[X|X[ˆ] ] = X,[ˆ] E[Y |Y[ˆ] ] = Y,[ˆ] _H( X[ˆ]_ ) ≤ _R,_ _H( Y[ˆ] ) ≤_ _R,_

_and_
_Dmse(pX_ _, R) ≜_ inf E[ _X_ _X_ ]
_p ˆX_ _X_ _∥_ _−_ [ˆ] _∥[2]_
_|_ (4)

_s.t._ _H( X[ˆ]_ ) ≤ _R._

_Moreover, let_

_Dncr(pX_ _, pY, R) ≜_ _Dmse(pX_ _, R) + Dmse(pY, R) + W2[2][(][p][ ˆ]X_ _[∗]_ _[, p]Y[ ˆ]_ _[∗]_ [)][,] (5)

_Dncr(pX_ _, pY, R) ≜_ _Dmse(pX_ _, R) + Dmse(pY, R),_ (6)


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. We also note some differences
between this formulation and the distortion-rate function from information theory - here the target distribution
_pY is fixed, and we impose a constraint on entropy rather than mutual information to reflect that we perform_
compression on a per-sample basis (i.e. the one-shot scenario) rather than on asymptotically long blocks.


-----

_where p ˆX_ _[∗]_ _[and][ p][ ˆ]Y_ _[∗]_ _[are the marginal distributions induced by the minimizers][ p][ ˆ]X_ _[∗]|X_ _[and][ p][ ˆ]Y_ _[∗]|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 ._

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 p ˆX _X_ [to produce the compressed representation][ ˆ]X
_|_

from X. This is then passed through a “converter” p ˆY _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 symmetric[2] 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 p ˆY _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 R[n]) 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 p ˆY |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]] = W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][,] (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, W2[2][(][p][ ˆ]X _[, p]Y[ ˆ]_ [)][ 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.

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(·, ·).


-----

No common randomness With common randomness


_X_ _pZ|X_ _Z_ _pY |Z_ _Y_


|Col1|pZ|X|Col3|
|---|---|---|
||||

|Col1|pY |Z|Col3|
|---|---|---|
||||

|Col1|pZ|X,U|Col3|
|---|---|---|

|Col1|pY |Z,U|Col3|
|---|---|---|

|Col1|p Xˆ|X|Col3|
|---|---|---|
||||

|Col1|p Yˆ | Xˆ|Col3|
|---|---|---|
||||

|Col1|p Y | Yˆ|Col3|
|---|---|---|
||||

|Col1|pY |X,U|Col3|
|---|---|---|


_X,U_ _Z_ _pY |_

_U_


Figure 2: Architectures. Top left: Definition 2. Bottom left: Theorem 1. Top right: Definition 3.

_U_

Bottom right: Theorem 3. Entropy coding of intermediate representations Z, _X,[ˆ]_ _Y[ˆ] is not shown. For_
Theorem 3, the division between sender and receiver is across an encoder C = f (X, U ) and decoder
_Y = g(C, U_ ) performing entropy coding along pY |X,U .

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_
distributions pX, pY and satisfying pU,X,Z,Y = pU _pX_ _pZ_ _X,U_ _pY_ _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][ )]] (11)

s.t. _H(Z|U_ ) ≤ _R._

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 = pU_ _pX_ _pY_ _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][ )]] (12)

_s.t._ _H(Y |U_ ) ≤ _R._

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


-----

(a) (b) (c)

Figure 3: Binary case distortion-rate tradeoffs. (a) qX = qY = 0.3, where Dncr(B(qX ), B(qY ), R)
and Dncr( (qX ), (qY ), R) coincide with Dncr( (qX ), (qY ), R); (b) qX = 0.3, qY = 0.5, where
_B_ _B_ _B_ _B_
_Dncr(_ (qX ), (qY ), R) is tight but Dncr( (qX ), (qY ), R) is loose; (c) qX = 0.3, qY = 0.6, where
_B_ _B_ _B_ _B_
both bounds are loose. Moreover, it can be seen from all these examples that common randomness
can indeed help improve the distortion-rate tradeoff.

_Y given the source X 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 Y must be generated at the decoder.

2.2 NUMERICAL EXAMPLES

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(_ (qX ), (qY ), R) as well as Dncr( (qX ), (qY ), R) and Dncr( (qX ), (qY ), R) are pro_B_ _B_ _B_ _B_ _B_ _B_
vided 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. 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.

3 EXPERIMENTAL RESULTS

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

3.1 RATE-DISTORTION COMPARISON WITH COMMON RANDOMNESS

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


-----

|Col1|𝑓 𝑄 𝑔|
|---|---|


𝑢 𝑢

𝑓 𝑄 𝑔 𝑓 𝑄 𝑔"

𝑥 𝑥 𝑔#

ℎ

(a) (b)

Figure 4: Illustration of our experimental setup. (a) shows the end-to-end learning system with

common randomness, where the encoder and decoder have access to the same randomness u. (b)
presents the network setup for verifying the architecture principle given in Theorem 1.

problem of the form

min _X_ _g(Q(f_ (X, U ))) 2
_f,g,Q_ _∥_ _−_ _∥[2]_

(13)
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 p ˜Y [and][ p][Y][ 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_ ), (14)

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 ˜_ [)][,] (15)

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. p ˜Y

_[≈]_ _[p][Y][ 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, (14) becomes

_Y˜ = g(Q(f_ (X) + U1) _U2)_ (16)
_−_

Then we conduct training using the objective (15) 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.


-----

Low-Res

GT

Noisy

Clear


R = 4 R = 8 R = 12

R = 16 R = 20 R = 24

(b)

R = 6 R = 24 R = 42

R = 60 R = 78 R = 96

(d)


(a)

(c)


Figure 5: (a)(b) The experimental results of 4 times image super-resolution. (c)(d) The experimental
results of image denoising. The noise pattern is synthesized by additive Gaussian noise with standard
deviation set to 20. (a)(c) Rate-distortion trade-offs. Blue points are the MSE distortion loss for a
particular rate under the setting of using common randomness, while orange points illustrate the
same trade-off without using common randomness. For both tasks, at any rate, the performance of
using common randomness is better than the case without common randomness. (b)(d) Examples for
outputs from several models with different rates. As the rate increases, the outputs become clearer.

3.2 ARCHITECTURAL PRINCIPLE

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]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][,] (17)

where _X[ˆ] and_ _Y[ˆ] are some representations of X and Y under MSE distortion. The chosen rate-_
distortion 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 (17) 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)
| {z }


+ E[∥Y[˜] − _Y[˜]2∥[2]]_
(b)
| {z }


+ E[∥Y[˜]1 − _Y[˜]2∥[2]]_
(c)
| {z }


(18)


-----

Table 1: Results of architecture principle in Theorem 1. The end-to-end loss and decomposed loss
are very close for different rates.

|Col1|Super-resolution|Denoising|
|---|---|---|
|Rate|4 10 20 30|12 30 60 90|
|End-to-end Loss Decomposed Loss|0.0558 0.0435 0.0351 0.0308 0.0586 0.0453 0.0349 0.0309|0.0230 0.0175 0.0140 0.0123 0.0243 0.0192 0.0158 0.0139|



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 (18) (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
(18) 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.

Table 2: Comparison of separate vs. joint training for (18). See the above paragraph for explanation.

|Col1|Col2|Super-resolution|Col4|Col5|
|---|---|---|---|---|
|Rate|4|10|20|30|
|Method|Joint Separate|Joint Separate|Joint Separate|Joint Separate|
|E[∥X −Y˜ 1∥2] E[∥Y˜ −Y˜ 2∥2]|0.0355 0.0356 0.0227 0.0216|0.0223 0.0214 0.0222 0.0206|0.0136 0.0113 0.0191 0.0191|0.0092 0.0083 0.0172 0.0155|


|E[∥X −˜ Y1∥2] E[∥˜ Y −˜ Y2∥2]|0.0355 0.0356 0.0227 0.0216|0.0223 0.0214 0.0222 0.0206 Denoising|0.0136 0.0113 0.0191 0.0191|0.0092 0.0083 0.0172 0.0155|
|---|---|---|---|---|
|Rate|12|30|60|90|
|Method|Joint Separate|Joint Separate|Joint Separate|Joint Separate|
|E[∥X −Y˜ 1∥2] E[∥Y˜ −Y˜ 2∥2]|0.0191 0.0190 0.0050 0.0046|0.0146 0.0145 0.0044 0.0040|0.0117 0.0123 0.0038 0.0035|0.0104 0.0107 0.0032 0.0030|



4 RELATED WORKS

Sinkhorn distances (Cuturi, 2013) are a formulation of optimal transport with a penalty term corresponding to the mutual information between the source and target distributions. This has been
studied in information theory literature (e.g. (Bai et al., 2020; Wang et al., 2021a)). For source
coding in particular, Saldi et al. (2015a;b) consider common randomness with constrained output
distribution. Blau & Michaeli (2018) evaluated a number of deep image restoration techniques and
somewhat counter-intuitively demonstrated a tradeoff between optimizing for distortion and “perceptual quality”, i.e. realism. Wang et al. (2021b) model the shift in distribution due to degradation as an
optimal transport problem. However this work does not consider compression and their results are
qualitatively different from ours. Meanwhile, output-constrained lossy compression has also been
shown to improve perceptual quality (Tschannen et al., 2018), leading to the rate-distortion-perception
framework (Blau & Michaeli, 2019). An analysis of the one-shot distortion-rate function was studied
recently by (Elkayam & Feder, 2020). Our problem formulation is different as we assume the output
distribution is fixed.

5 CONCLUSION AND FUTURE WORK

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
tasks under distribution shift where our theory could be applicable.


-----

REFERENCES

Eirikur Agustsson, Fabian Mentzer, Michael Tschannen, Lukas Cavigelli, Radu Timofte, Luca
Benini, and Luc Van Gool. Soft-to-hard vector quantization for end-to-end learning compressible
representations. pp. 1142–1152, 2017.

Eirikur Agustsson, Michael Tschannen, Fabian Mentzer, Radu Timofte, and Luc Van Gool. Generative adversarial networks for extreme learned image compression. In Proceedings of the IEEE
_International Conference on Computer Vision, pp. 221–231, 2019._

Martin Arjovsky, Soumith Chintala, and Leon Bottou. Wasserstein generative adversarial networks.´
In International Conference on Machine Learning, pp. 214–223, 2017.

Yikun Bai, Xiugang Wu, and Ayfer Ozg[¨] ur. Information constrained optimal transport: From talagrand,¨
to marton, to cover. In 2020 IEEE International Symposium on Information Theory (ISIT), pp.
2210–2215. IEEE, 2020.

Yochai Blau and Tomer Michaeli. The perception-distortion tradeoff. In Proceedings of the IEEE
_Conference on Computer Vision and Pattern Recognition, pp. 6228–6237, 2018._

Yochai Blau and Tomer Michaeli. Rethinking lossy compression: The rate-distortion-perception
tradeoff. In International Conference on Machine Learning, pp. 675–685, 2019.

Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural
_information processing systems, 26:2292–2300, 2013._

Abbas El Gamal and Young-Han Kim. Network information theory. Cambridge university press,
2011.

Nir Elkayam and Meir Feder. One shot approach to lossy source coding under average distortion
constraints. In 2020 IEEE International Symposium on Information Theory (ISIT), pp. 2389–2393.
IEEE, 2020.

Robert M Gray and Thomas G Stockham. Dithered quantizers. IEEE Transactions on Information
_Theory, 39(3):805–812, 1993._

Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.
Improved training of wasserstein gans. In Advances in neural information processing systems, pp.
5767–5777, 2017.

Andras Gyorgy and Tamas Linder. Optimal entropy-constrained scalar quantization of a uniform´
source. IEEE Transactions on Information Theory, 46(7):2704–2711, 2000.

Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint
_arXiv:1412.6980, 2014._

Yann LeCun, Leon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to´
document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998.

Cheuk Ting Li and Abbas El Gamal. Strong functional representation lemma and applications to
coding theorems. IEEE Transactions on Information Theory, 64(11):6967–6978, 2018.

Ryutaroh Matsumoto. Introducing the perception-distortion tradeoff into the rate-distortion theory of
general information sources. IEICE Communications Express, 7(11):427–431, 2018.

Ryutaroh Matsumoto. Rate-distortion-perception tradeoff of variable-length source coding for general
information sources. IEICE Communications Express, 8(2):38–42, 2019.

Sachit Menon, Alexandru Damian, Shijia Hu, Nikhil Ravi, and Cynthia Rudin. Pulse: Self-supervised
photo upsampling via latent space exploration of generative models. In Proceedings of the ieee/cvf
_conference on computer vision and pattern recognition, pp. 2437–2445, 2020._

Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Conditional probability models for deep image compression. In Proceedings of the IEEE Conference on
_Computer Vision and Pattern Recognition, pp. 4394–4402, 2018._


-----

Fabian Mentzer, George D Toderici, Michael Tschannen, and Eirikur Agustsson. High-fidelity
generative image compression. In Advances in Neural Information Processing Systems, volume 33,
2020.

Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading
digits in natural images with unsupervised feature learning. 2011.

Xingang Pan, Xiaohang Zhan, Bo Dai, Dahua Lin, Chen Change Loy, and Ping Luo. Exploiting deep
generative prior for versatile image restoration and manipulation. IEEE Transactions on Pattern
_Analysis and Machine Intelligence, 2021._

Gabriel Peyre and Marco Cuturi. Computational optimal transport.´ _Foundations and Trends in_
_Machine Learning, 11(5-6), 2019._

Oren Rippel and Lubomir Bourdev. Real-time adaptive image compression. In International
_Conference on Machine Learning, pp. 2922–2930, 2017._

Naci Saldi, Tamas Linder, and Serdar Y´ uksel. Randomized quantization and source coding with¨
constrained output distribution. IEEE Transactions on Information Theory, 61(1):91–106, 2015a.

Naci Saldi, Tamas Linder, and Serdar Y´ uksel. Output constrained lossy source coding with limited¨
common randomness. IEEE Transactions on Information Theory, 61(9):4984–4998, 2015b.

Shibani Santurkar, David Budden, and Nir Shavit. Generative compression. In 2018 Picture Coding
_Symposium (PCS), pp. 258–262. IEEE, 2018._

Lucas Theis and Eirikur Agustsson. On the advantages of stochastic encoders. arXiv preprint
_arXiv:2102.09270, 2021._

Lucas Theis and Aaron B Wagner. A coding theorem for the rate-distortion-perception function.
_arXiv preprint arXiv:2104.13662, 2021._

Michael Tschannen, Eirikur Agustsson, and Mario Lucic. Deep generative models for distributionpreserving lossy compression. In Advances in Neural Information Processing Systems, pp. 5929–
5940, 2018.

C´edric Villani. Optimal transport: old and new, volume 338. Springer, 2009.

Shuchan Wang, Photios A Stavrou, and Mikael Skoglund. Generalized talagrand inequality for
sinkhorn distance using entropy power inequality. arXiv preprint arXiv:2109.08430, 2021a.

Wei Wang, Fei Wen, Zeyu Yan, Rendong Ying, and Peilin Liu. Optimal transport for unsupervised
restoration learning. arXiv preprint arXiv:2108.02574, 2021b.

Zeyu Yan, Fei Wen, Rendong Ying, Chao Ma, and Peilin Liu. On perceptual lossy compression: The
cost of perceptual reconstruction and an optimal training framework. In International Conference
_on Machine Learning, 2021._

George Zhang, Jingjing Qian, Jun Chen, and Ashish Khisti. Universal rate-distortion-perception
representations for lossy compression. arXiv preprint arXiv:2106.10311, 2021.

Kai Zhang, Wangmeng Zuo, Shuhang Gu, and Lei Zhang. Learning deep cnn denoiser prior for image
restoration. In Proceedings of the IEEE conference on computer vision and pattern recognition,
pp. 3929–3938, 2017.

Jacob Ziv. On universal quantization. IEEE Transactions on Information Theory, 31(3):344–347,
1985.


-----

A THEORETICAL RESULTS

A.1 DISTORTION-RATE VS RATE-DISTORTION FORMULATION

In addition to Definitions 2 and 3, we can equivalently define

_Rncr(pX_ _, pY, D) ≜_ inf
_pX,Z,Y ∈Mncr(pX_ _,pY )_ _[H][(][Z][)]_ (19)

s.t. E[d(X, Y )] ≤ _D,_


_Rcr(pX_ _, pY, D) ≜_ inf
_pU,X,Z,Y ∈Mcr(pX_ _,pY )_ _[H][(][Z][|][U]_ [)] (20)

s.t. E[d(X, Y )] ≤ _D._

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

A.2 PROOFS OF THEORETICAL RESULTS

_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_
_p ˆX|X_ [,][ p][ ˆ]Y |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_ [=][ p][X] _[p][ ˆ]X|X_ [,]

_pY,Y ˆ_ [=][ p][Y][ p][ ˆ]Y |Y [, and][ p][ ˆ]X,Y[ˆ] [satisfying][ E][[][∥]X[ˆ] − _Y[ˆ] ∥[2]] = W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][. 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]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][.] (21)


Lettogether with ( Z ≜ _X[ˆ]_ . It can be verified that21), implies Dncr(pX _, p pYX,Z,Y, R) ∈ ≤_ _DMmsencr((ppXX, p, pYY, R ) and). This completes the proof of ( H(Z) = H( X[ˆ]_ ) ≤ _R, which,7)._

Dropping the term W2[2][(][p][ ˆ]X _[, p]Y[ ˆ]_ [)][ in (][3][) yields]

_Dncr(pX_ _, pY, R) ≥_ _D[˜]_ mse(pX _, R) + D[˜]_ mse(pY, R),

where

_D˜_ mse(pX _, R) ≜_ inf E[ _X_ _X_ ]
_p ˆ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 p ˆX|X [=][ p][ ˆ]X _[′]|X_ [and][ p][ ˆ]Y |Y [=]
_p ˆY_ _[′]|Y_ [in (][3][) gives]

_Dncr(pX_ _, pY, R) ≤_ _D[˜]_ mse(pX _, R) + D[˜]_ mse(pY, R) + W2[2][(][p][ ˆ]X _[′]_ _[, p]Y[ ˆ]_ _[′]_ [)][,]

where p ˆX _[′]|X_ [and][ p][ ˆ]Y _[′]|Y_ [are the minimizers that attain][ ˜]Dmse(pX _, R) and_ _D[˜]_ mse(pY, R) respectively
while p ˆX _[′][ and][ p][ ˆ]Y_ _[′][ are their induced marginal distributions. It is clear that][ p][ ˆ]X_ _[′]|X_ [and][ p][ ˆ]Y _[′]|Y_ [coincide]


-----

with p ˆX _[∗]|X_ [and][ p][ ˆ]Y _[∗]|Y_ [respectively as the constraints][ E][[][X][|][ ˆ]X] = X[ˆ] and E[Y |Y[ˆ] ] = Y[ˆ] are automatically satisfied by p ˆX _[∗]|X_ [and][ p][ ˆ]Y _[∗]|Y_ [. This proves (][8][). For the special case][ p][X][ =][ p][Y][, we have]
_p ˆX_ _[∗]|X_ [=][ p][ ˆ]Y _[∗]|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 R[n] (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 R[n]. As such,
_Dmse(pX_ _, R) should be interpreted as the one-shot distortion-rate function with the reconstruction_
alphabet being R[n], 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 R[n]. This subtle issue, which is often overlooked in the literature, arises
when one deals with discrete X 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][ p]X,X[ˆ] [,][ p][ ˆ]X,Y[ˆ] [, and][ p]Y,Y[ˆ] [. We can construct a new joint]
distribution pX, ˆX _[′],Y[ˆ]_ _[′],Y_ [such that][ p]X,X[ˆ] _[′][ =][ p]X,X[ˆ]_ [,][ p][ ˆ]X _[′],Y[ˆ]_ _[′][ =][ p][ ˆ]X,Y[ˆ]_ [,][ p]Y,Y[ˆ] _[′][ =][ p]Y,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 p ˆX _[′′],Y[ˆ]_ _[′′][ with][ p][ ˆ]X_ _[′′][ =][ p][ ˆ]X_ [and]

_p ˆY_ _[′′][ =][ p][ ˆ]Y_ [such that][ E][[][∥]X[ˆ] _[′′]_ _−_ _Y[ˆ]_ _[′′]∥[2]] < E[∥X[ˆ] −_ _Y[ˆ] ∥[2]]. Leverage this p ˆX_ _[′′],Y[ˆ]_ _[′′][ to construct a new joint]_
distribution pX, ˆX _[′′],Y[ˆ]_ _[′′],Y_ [such that][ p]X,X[ˆ] _[′′][ =][ p]X,X[ˆ]_ [,][ p]Y,Y[ˆ] _[′′][ =][ p]Y,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 W2[2][(][p][ ˆ]X _[, p]Y[ ˆ]_ [)][.]

_Proof of Theorem 3. Choosing pU,X,Y from W2[2][(][p][X]_ _[, p][Y]_ [)][ 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 anyand V2, independent of (U, X, Z, Y (U, X, V ) with1 p)U,X,Z,Y, as well as determintic mappings ∈ _Mcr(pX_ _, pY ), there exist ϕ V11 and, independent of ϕ2 such that (U, X Z =),_
_ϕ2(U, X, V1) and Y = ϕ2(Z, V2). Let U_ _[′]_ ≜ (U, V1, V2). Clearly, pU ′,X,Y = pU ′ _pX_ _pY |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.

A.3 LINEAR PROGRAM FORMULATION FOR COMMON RANDOMNESS

In the finite alphabet case, we can formulate Theorem 3 as follows:


_pU_ (u)E[d(X, fu(X))]
_uX∈U_


_Dcr(pX_ _, pY, R) = min_
_pU_


s.t.


_pU_ (u)H(fu(X)) _R,_
_≤_
_uX∈U_

_pU_ (u)P(fu(X) = y) = pY (y), _y ∈Y,_
_uX∈U_


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

A.4 BINARY CASE

Letbetween Dmin[(][B][)] B[≜](q[|]X[q][X]) and[ −] _[q][Y] B[ |]([ and]qY )[ D], which is the minimummax[(][B][)]_ [≜] _[q]X_ [+] _[q]Y_ _[−]_ [2][q]X E[q]Y[d[. Note that]H (X, Y )][ D] achievable by couplingmin[(][B][)] [is the total variation distance] X and Y .
On the other hand, we have E[dH (X, Y )] = Dmax[(][B][)] [for][ X][,][ Y][ independent. It is clear that][ D]min[(][B][)] [and]
_Dmax[(][B][)]_ [are the infimum and supremum of][ D]ncr[(][B][(][q]X [)][,][ B][(][q]Y [)][, R][)][ (as well as][ D]cr[(][B][(][q]X [)][,][ B][(][q]Y [)][, R][)][),]
respectively.

**Theorem 4. Assume Hamming distortion measure. Under no common randomness, we have**


_−−_ [2(1]1−21H[−]q−Xb[−][q]H[X]q[1]Yb[−]([)(1]R[1]()[−]R[+][q])[Y][ q][ )][X]+ 2[ +][ q] −[Y][,]qX − _qY,_ _qqXX + + q qYY ≤ > 11,,_ (22)


_Dncr(B(qX_ ), B(qY ), R) =


_for R ∈_ [0, min{Hb(qX ), Hb(qY )}], and = Dmin[(][B][)] _[for][ R >][ min][{][H][b][(][q][X]_ [)][, H][b][(][q][Y][ )][}][. Moreover,]

_Dncr(B(qX_ ), B(qY ), R)

= −−− [2(1]1[(1]−[−]21H[−]q−[q]Xb[X][−][q]H[X]q[1][)]Yb[−][2]([)(1]R[+][1]()[q][−]RY[2]1[+][q])−[−][Y][ q][ )]H[(][q][X]b[Y][−]+ 2[ +][ −][1]([q]R[ q] −[X])[Y][+][,]q[H]Xb[−] −[1](Rq))Y[2], + Hb[−][1](R) − [2][q][Y](1[ (1]−[−]H[q]b[−][X][1][)]([H]Rb[−]))[1][2](R) _,_ _qqqXXX <, q, qYY ≤ ≥2[1]_ _[, q][Y]22[1][1][ >][,][,]_ [ 1]2 _[,]_

− _[q]X[2]_ [+(1][−][q][Y][ )]1[2]−[−]H[(][q]b[X][−][1][−]([q]R[Y])[ +][H]b[−][1](R))[2] + Hb[−][1](R) − [2][q][X](1[(1]−[−]H[q]b[−][Y][ )][1]([H]Rb[−]))[1][2](R) _,_ _qX >_ 2[1] _[, q][Y][ <][ 1]2_ _[,](23)_


-----

_for R ∈_ [0, min{Hb(qX ), Hb(qY )}], and


_−_ [(1][−][q]1[X]−[)]H[2][+(1]b[−][1](R[−])[q][Y][ )][2] + 2 − _qX −_ _qY,_ _qX_ _, qY ≤_ 2[1] _[,]_

_−_ 1−qXH[2] [+]b[−][1][q]Y([2]R) [+][ q][X][ +][ q][Y][,] _qX_ _, qY ≥_ 2[1] _[,]_

_−_ [(1]1[−]−[q]H[X]b[−][)][1][2]([+]R[q])Y[2] [+ 1][ −] _[q][X][ +][ q][Y][,]_ _qX <_ [1]2 _[, q][Y][ >][ 1]2_ _[,]_

_−_ _[q]X1[2]−[+(1]Hb[−][−][1][q]([Y]R[ )])[2]_ [+ 1 +][ q][X][ −] _[q][Y][,]_ _qX >_ [1]2 _[, q][Y][ <][ 1]2_ _[,]_


(24)


_Dncr(_ (qX ), (qY ), R) =
_B_ _B_


_for R_ [0, min _Hb(qX_ ), Hb(qY ) ]. Here, Hb[−][1](R) denotes the inverse of the binary entropy
_∈_ _{_ _}_
_function on [0, 1/2]. With common randomness,_

_Dcr(B(qX_ ), B(qY ), R) = − [2(1][ −]Hb[q]([X]qX[)][q])[X] _[R]_ + Dmax[(][B][)] (25)

_for R ∈_ [0, ρHb(qX )], and = Dmin[(][B][)] _[for][ R > ρH][b][(][q][X]_ [)][. Here,][ ρ][ ≜] [min][{][q][Y][ /q][X] _[,][ (1]_ _[−]_ _[q][Y][ )][/][(1]_ _[−]_ _[q][X]_ [)][}][.]

_Proof of (25). 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

_pU_ (u)H(fu(X)) = Hb(qX )(pU (1) + pU (2)),
_uX∈U_

_pU_ (u)E[dH (X, fu(X))] = pU (2) + qX _pU_ (3) + (1 − _qX_ )pU (4),
_uX∈U_

_pU_ (u)P(fu(X) = 1) = pU (1)qX + (1 − _qX_ )pU (2) + pU (4).
_uX∈U_

In light of Theorem 3,

_Rcr(_ (qX ), (qY ), D) = min
_B_ _B_ _pU_ (1), _,pU_ (4) _[H][b][(][q][X]_ [)(][p][U] [(1) +][ p][U] [(2))]

_···_

s.t. _pU_ (2) + qX _pU_ (3) + (1 _qX_ )pU (4) _D,_ (26)
_−_ _≤_
_qX_ _pU_ (1) + (1 − _qX_ )pU (2) + pU (4) = qY, (27)
_pU_ (1) + pU (2) + pU (3) + pU (4) = 1, (28)
_pU_ (1), pU (2), pU (3), pU (4) 0. (29)
_≥_


Note that

_pU_ (2) + qX _pU_ (3) + (1 _qX_ )pU (4)
_−_
= pU (2) + qX _pU_ (3) + (1 _qX_ )(1 _pU_ (1) _pU_ (2) _pU_ (3)) (30)
_−_ _−_ _−_ _−_
= (1 _qX_ )pU (1) + qX _pU_ (2) + (2qX 1)pU (3) + 1 _qX_ _,_ (31)
_−_ _−_ _−_ _−_

where (30) is due to (28). Moreover, it follows by (27) and (28) that

_pU_ (3) = −(1 − _qX_ )pU (1) − _qX_ _pU_ (2) + 1 − _qY ._ (32)

Substituting (32) into (31) and invoking the fact that pU (2) 0 gives
_≥_


_pU_ (2) + qX _pU_ (3) + (1 _qX_ )pU (4)
_−_

= 2(1 _qX_ )qX (pU (1) + pU (2)) + 4(1 _qX_ )qX _pU_ (2) + Dmax[(][B][)]
_−_ _−_ _−_
_≥−2(1 −_ _qX_ )qX (pU (1) + pU (2)) + Dmax[(][B][)] _[,]_

which, together with (26), implies


1

2(1 _qX_ )qX (Dmax[(][B][)] _[−]_ _[D][)][.]_
_−_


_pU_ (1) + pU (2)
_≥_


-----

As a consequence, we must have

_Hb(qX_ )
_Rcr(B(qX_ ), B(qY ), D) ≥ 2(1 _qX_ )qX (Dmax[(][B][)] _[−]_ _[D][)][.]_

_−_

One can readily verify that this lower bound is tight as it is attained by p[∗]U [with]


1
_p[∗]U_ [(1) =] 2(1 _qX_ )qX (Dmax[(][B][)] _[−]_ _[D][)][,]_

_−_

_p[∗]U_ [(2) = 0][,]


_p[∗]U_ [(3) =][ −] 2q[1]X (Dmax[(][B][)] _[−]_ _[D][) + 1][ −]_ _[q][Y]_ _[,]_


1
_p[∗]U_ [(4) =][ −] 2(1 − _qX_ ) [(][D]max[(][B][)] _[−]_ _[D][) +][ q][Y]_ _[,]_


which satisfies (26)–(29) for D ∈ [Dmin[(][B][)][, D]max[(][B][)] []][. The expression of][ D]cr[(][B][(][q]X [)][,][ B][(][q]Y [)][, R][)][ can be]
obtained by taking the inverse of Rcr(B(qX ), B(qY ), D).

_Proof of (22). 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 pX ˆXY 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) + ϵ. (33)

Without loss of generality, we assume _X[ˆ] and_ _Y[ˆ] take value from {xˆi}i[N]=1_ [and][ {]y[ˆ]i}i[N]=1[, respectively,]
and _Y[ˆ] = ψ( X[ˆ]_ ), where ψ is a bijection from {xˆi}i[N]=1 [to][ {]y[ˆ]i}i[N]=1 [with][ ˆ]yi = ψ(ˆxi), i = 1, · · ·, N . Let
_θi ≜_ _p ˆX_ [(ˆ]xi), or equivalently, θi ≜ _p ˆY_ [(ˆ]yi), i = 1, · · ·, N . Note that _X[ˆ] = E[X|X[ˆ]_ ] and _Y[ˆ] = E[Y |Y[ˆ] ]_
if and only ifNi=1 _[p][ ˆ]X_ [(ˆ]xi) ppXX| ˆX ˆX[(1][(1][|][|]x[ˆ]x[ˆ]ii) =) = ˆ qxXi and and pY |i ˆY=1[(1][p][|]y[ ˆ]Y[ˆ]i[(ˆ]) = ˆyi)pyYi for ˆY [(1] θ[|]yi[ˆ] >i) = 0, q iY = 1 can be written equivalently as, · · ·, N . So the constraints
PNi=1 _[θ][i]x[ˆ]i = qX and|_ _i=1_ _[θ][i]y[ˆ]i = qY[P] . Moreover, it is easy to verify that[N]_ _|_
P E[[P]∥X[N] − _X[ˆ]_ _∥[2]] + E[∥Y −_ _Y[ˆ] ∥[2]] + E[∥X[ˆ] −_ _Y[ˆ] ∥[2]]_


_θi(ˆxi_ _yˆi)[2]_
_i=1_ _−_

X


_θi(1 −_ _xˆi)ˆxi +_
_i=1_

X


_θi(1 −_ _yˆi)ˆyi +_
_i=1_

X


= _i=1_ _θi(ˆxi + ˆyi −_ 2ˆxiyˆi).

X

In light of Theorem 1 and (33), the following optimization problem (P) yields an upper bound on
_Dncr(pX_ _, pY, R) with a gap at most ϵ:_


_i=1_ _θi(ˆxi + ˆyi −_ 2ˆxiyˆi) (P)

X


min
(θi,xˆi,yˆi,)[N]i=1


_N_

_θi log [1]_ _R,_

_θi_ _≤_

_i=1_

X


s.t.


_θi = 1,_
_i=1_

X


_θixˆi = qX_ _,_
_i=1_

X


_θiyˆi = qY,_
_i=1_

X


_θi_ 0, _xˆi_ [0, 1], _yˆi_ [0, 1], _i = 1,_ _, N._
_≥_ _∈_ _∈_ _· · ·_

Given (θi, ˆyi)[N]i [, (P) degenerates to a linear programming problem with respect][ (ˆ]xi)[N]i=1 [over hyper-]
rectangle [0, 1][N] subject to the constraint _i=1_ _[θ][i]x[ˆ]i = qX_, for which the minimum is attained at

[P][N]


-----

a point on an edge of [0, 1][N] . Therefore, it suffices to consider (ˆxi)[N]i=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 ˆyi, 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]_

= −2ˆxyˆ − 2ˆx[′]yˆ[′] + 2ˆxyˆ[′] + 2ˆx[′]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 p ˆX_ [and][ p][ ˆ]Y [, 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

_p ˆX,Y[ˆ]_ [(ˆ]x, 1) = _[q][X]_

_x ˆ_ _[,]_

_p ˆX,Y[ˆ]_ [(0][,][ ˆ]y) = 1
_−_ _[q]x ˆ[X]_ _[,]_

_yˆ = 1_ _._
_−_ 1[1][ −] _[q]xˆ[Y]_

_−_ _[q][X]_


Clearly, H( X[ˆ] ) = H( Y[ˆ] ) = Hb( _[q]xˆ[X]_ [)][. Since][ ˆ]x ∈ (0, 1) and ˆy ∈ (0, 1), we must have

_qX <_ _[q]xˆ[X]_ _[< q][Y][, 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]]_

= _[q][X]_ _x(1_ _xˆ) +_ 1 _yˆ(1_ _yˆ) +_ _[q][X]_ _x)[2]_ + 1

_xˆ_ [ˆ] _−_ _−_ _[q]xˆ[X]_ _−_ _xˆ_ [(1][ −] [ˆ] _−_ _[q]xˆ[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 p ˆXY[ˆ] [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 ˆx1 = ˆy1 = 0, ˆx3 = ˆy3 = 1, ˆx2 = ˆx, and ˆy2 = ˆy.
The constraints _i=1_ _[θ][i][ = 1][,][ P]i[3]=1_ _[θ][i]x[ˆ]i = qX_, and _i=1_ _[θ][i]y[ˆ]i = qY imply_

[P][3] _θ1 = 1 −_ _qX −_ [P](1 −[3] _xˆ)θ,_

_θ3 = qX −_ _xθ,ˆ_

_yˆ =_ _[q][Y][ −]_ _[q][X]_ + ˆx.

_θ_

In this way, we get a simplified optimization problem (P’):

min _x(1_ _xˆ)θ + (1_ 2ˆx)(qY _qX_ ) (P’)
_θ,xˆ_ [2ˆ] _−_ _−_ _−_

1 1
s.t. (1 _qX_ (1 _xˆ)θ) log_ _xθ) log_
_−_ _−_ _−_ 1 _qX_ (1 _xˆ)θ_ [+][ θ][ log 1]θ [+ (][q][X][ −] [ˆ] _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”):

1 1
min _x)θ) log_ _xθ) log_ (P”)
_θ,xˆ_ [(1][ −] _[q][X][ −]_ [(1][ −] [ˆ] 1 _qX_ (1 _xˆ)θ_ [+][ θ][ log 1]θ [+ (][q][X][ −] [ˆ] _qX_ _xθˆ_

_−_ _−_ _−_ _−_

s.t. 2ˆx(1 _xˆ)θ + (1_ 2ˆx)(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, [q][Y][ −] _[q][X]_ _,_

1 _x ˆ_ _[, q][X][ −]xˆ_ _[q][Y]_

 _−_ 

_x)(qY_ _qX_ )

_θ ≜_ min 1, [1][ −] _[q][X]_ _−_ _._

1 _x ˆ_ _[, q]x ˆ[X]_ _[, D][ −]_ [(1]2ˆ[ −]x(1[2ˆ] _xˆ)_

 _−_ _−_ 

Without loss of generality, we assumeeasily verified. _qY ≥_ _qX and qX + qY ≤_ 1. The following statements can be

1. For ˆx [0, _[D]2(1[+][q][X]q[−]Y[q] )[Y]_ []][,]
_∈_ _−_


_θ =_ _[q][Y][ −]_ _[q][X]_

1 _x ˆ_ _[,]_
_−_

_θ = [1][ −]_ _[q][X]_

1 _x ˆ_ _[.]_
_−_

2. For ˆx ( _[D]2(1[+][q][X]q[−]Y[q] )[Y]_ _[,][ q][X]_ [+]2[q]q[Y]Y[ −][D] ],
_∈_ _−_

_θ =_ _[q][Y][ −]_ _[q][X]_

1 _x ˆ_ _[,]_
_−_

_x)(qY_ _qX_ )
_θ =_ _[D][ −]_ [(1][ −] [2ˆ] _−_

2ˆx(1 − _xˆ)_


3. For ˆx ∈ ( _[q][X]_ [+]2[q]q[Y]Y[ −][D] _,_ _[q]q[X]Y_ []][,]


_θ =_ _[q][Y][ −]_ _[q][X]_

1 _x ˆ_ _[,]_
_−_

_θ =_ _[q][X]_

_x ˆ_ _[.]_


-----

4. For ˆx > _[q]q[X]Y_ [,][ [][θ, θ][]][ is empty.]

Note that when ˆx ∈ [0, _[q]q[X]Y_ []][ and][ θ][ =][ θ][,]


1
_xˆ)θ) log_ _xθ) log_

1 _qX_ (1 _xˆ)θ_ [+][ θ][ log 1]θ [+ (][q][X][ −] [ˆ]
_−_ _−_ _−_

1 1

+ θ log [1] _xθ) log_
1 _qY_ _θ_ [+ (][q][X][ −] [ˆ] _qX_ _xθˆ_
_−_ _−_


(1 _qX_ (1 _xˆ)θ) log_
_−_ _−_ _−_


_qX_ _xθˆ_
_−_


= (1 − _qY ) log_

_≥_ _Hb(qY )_
= H(Y ).


So it suffices to consider the case ˆx ∈ [0, _[q]q[X]Y_ []][ and][ θ][ =][ θ][, for which (P”) is reduced to the following]

form:

min _x),_
_xˆ_ [0, _[qX]_
_∈_ _qY_ []][ η][(ˆ]


where

_η(ˆx) ≜_


++12ˆ1−x−[D][q]−q[X]xˆX[−]q[+(1]X[(1][log]+(12(1[−]2ˆ[−]x[2ˆ]2ˆ(1[2ˆ]x−1xx1)(−−2ˆxˆ−)xqq)qxˆxˆYYX))q − −Y[+] −qDX[ q]Dlog)1[X]log−log[−]xˆxq[ˆ]XD2ˆ[log]+(1x−−(12(1qqX1−2ˆX2ˆ−−x+(12ˆ−x(1xxxˆˆ)xˆ)(q)2ˆ−Y−[,]xqxˆY2ˆ) −xD)qq[,]YX −) _D_ _xxˆˆ ∈_ [0( _[D],2(1[+][D]2(1[q][+][X][q]q[−]−[X]Y[q] )q[−][Y]Y[q] )[,][Y][ q][]][X][,]_ [+]2[q]q[Y]Y[ −][D] ],

_xˆ−xˆqX_ log _−xˆ−xˆqX_ [+][ q]xˆ[X] [log] _qxˆX−[,]_ _−_ _xˆ ∈ ∈_ ( _[q][X]_ [+]2−[q]q[Y]Y[ −][D] _,_ _[q]q[X]Y_ []][.]


Note that η(ˆx) is a continuous function over [0, _[q]q[X]Y_ []][. Moreover,][ η][(ˆ]x) decreases monotonically from

_Hb(qX_ ) to Hb( 2 _DqXmax[(][B][)]q[−]Y[D]_ _D_ [)][ as][ ˆ]x varies from 0 to _[D]2(1[+][q][X]q[−]Y[q] )[Y]_ [. Since][ η][(ˆ]x) is a concave function of

_qxˆX_ [for][ ˆ]x ∈ [ _[q][X]_ [+]2−[q]q[Y]Y[ −]−[D] _,_ _[q]q −[X]Y_ []][, it follows that] _−_

2qX _qY_

min _η(ˆx) = min_ _η(_ _[q][X][ +][ q][Y][ −]_ _[D]_ ), η( _[q][X]_ ) = min _Hb(_
_xˆ∈[_ _[qX][ +]2qY[qY][ −][D]_ _,_ _[qX]qY_ []]  2qY _qY_   _qX + qY −_ _D_ [)][, H][b][(][q][Y][ )]


So we have


min _η(ˆx)_
_xˆ∈[0,_ _[D]2(1[+][qX]−qY[ −][qY] )_ []][∪][[][ qX][ +]2qY[qY][ −][D] _,_ _[qX]qY_ []]

_Dmax[(][B][)]_ 2qX _qY_

= min _Hb(_ _[−]_ _[D]_

( 2 _qX_ _qY_ _D_ [)][, H][b][(] _qX + qY_ _D_ [)][, H][b][(][q][Y][ )]

_−_ _−_ _−_ _−_

_Dmax[(][B][)]_ 2qX _qY_

= min _Hb(_ _[−]_ _[D]_

( 2 _qX_ _qY_ _D_ [)][, H][b][(] _qX + qY_ _D_ [)])

_−_ _−_ _−_ _−_

= min _η(_ _[D][ +][ q][X][ −]_ _[q][Y]_ ), η( _[q][X][ +][ q][Y][ −]_ _[D]_ )

2(1 _qY )_ 2qY

 _−_ 

_≥_ _xˆ∈[_ _[D]2(1[+][qX]−qY[ −]min[qY] )_ _[,][ qX][ +]2qY[qY][ −][D]_ ] _η(ˆx),_


(34)


where (34) is due to the fact that Hb(qY ) _Hb(qX_ ) _Hb(_ 2 _DqXmax[(][B][)]q[−]Y[D]_ _D_ [)][ (with the first inequality]
_≥_ _≥_ _−_ _−_ _−_

being a consequence of qX ≤ _qY and qX + qY ≤_ 1). So the problem boils down to solving

min _η(ˆx)._
_xˆ∈[_ _[D]2(1[+][qX]−qY[ −][qY] )_ _[,][ qX][ +]2qY[qY][ −][D]_ ]

It can be verified that the minimum is attained at ˆx = _[D]2(1[+][q][X]q[−]Y[q] )[Y]_ [. This completes the proof of (][22][).]

_−_
A graphical illustration of the entropy-constrained optimal transport plan for the binary case can be
found in Figure 6.


-----

_Proof of (23). Note that_

_Dmse(_ (qX ), R) = [1]
_B_ 2 _[D][ncr][(][B][(][q][X]_ [)][,][ B][(][q][X] [)][, R][)]


= −− 11−−[(1]HH[−]qbb[−][−][q]X[2][X][1][1](([)]RR[2] )) [+ 1][+][ q][X][ −][,] _[q][X]_ _[,]_ _qqXX > ≤_ 22[1][1] _[,][,]_ _R ∈_ [0, Hb(qX )],

_Dmse(_ (qY ), R) = [1]
_B_ 2 _[D][ncr][(][B][(][q][Y][ )][,][ B][(][q][Y][ )][, R][)]_


= −− 11−−(1HH−qbb[−][−]qY[2]Y[1][1] )((RR[2] )) [+ 1][+][ q][Y][ −][,] _[q][Y][,]_ _qqYY > ≤_ 22[1][1] _[,][,]_ _R ∈_ [0, Hb(qY )].

Moreover, we have



_p ˆX_ _[∗]_ [(][ q]1[X]−[−]H[H]b[−]b[−][1][1]((RR)) [) = 1][ −] _[H]b[−][1](R),_ _R_ [0, Hb(qX )], qX
(p ˆX _[∗]_ [(1) =][ H]b[−][1](R), _∈_ _≤_ [1]2 _[,]_


_p ˆX_ _[∗]_ [(0) =][ H]b[−][1](R),
(p ˆX _[∗]_ [(] 1−Hqb[−]X[1](R) [) = 1][ −] _[H]b[−][1](R),_ _R ∈_ [0, Hb(qX )], qX ≥ [1]2 _[,]_

_p ˆY_ _[∗]_ [(][ q]1[Y]−[ −]H[H]b[−]b[−][1][1]((RR)) [) = 1][ −] _[H]b[−][1](R),_ _R_ [0, Hb(qY )], qY
(p ˆY _[∗]_ [(1) =][ H]b[−][1](R), _∈_ _≤_ 2[1] _[,]_

_p ˆY_ _[∗]_ [(0) =]q[ H]Y _b[−][1](R),_ _R_ [0, Hb(qY )], qY
(p ˆY _[∗]_ [(] 1−Hb[−][1](R) [) = 1][ −] _[H]b[−][1](R),_ _∈_ _≥_ 2[1] _[.]_

So
_W2[2][(][p][ ˆ]X_ _[∗]_ _[, p]Y[ ˆ]_ _[∗]_ [)]

1(−qXH−b[−]q[1]Y( )R[2]) _[,]_ _qX_ _, qY ≤_ 2[1] [or][ q][X] _[, q][Y][ ≥]_ 2[1] _[,]_

=  ((qqYX −−11qq−−XYHH ++bb[−][−]HH[1][1]bb[−][−]((RR[1][1](())RR))))[2][2] ++ H Hbb[−][−][1][1]((RR)) − − [2][2][q][q][Y][X](1(1[ (1][(1]−−[−][−]HH[q][q]bb[−][−][X][Y][ )][1][1][)](([H][H]RRbb[−][−]))))[1][1][2][2]((RR)) _,,_ _qqXX < >_ [1]2[1]2 _[, q][, q][Y][Y][ >][ <][ 1][ 1]22_ _[,][.]_

Based on the above expressions, one can easily verify ( 23) and (24). In particular, it is worth noting
that when qX _, qY ≤_ 2[1] [or][ q][X] _[, q][Y][ ≥]_ 2[1] [,]

_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(_ (qX ), R) ≜ min
_B_ _qY_ [0,1] _[D][cr][(][B][(][q][X]_ [)][,][ B][(][q][Y][ )][, R][)]
_∈_


_qX_ 1 _Hb(RqX_ ) _,_ _R_ [0, Hb(qX )], qX 2 _[,]_

= _−_ _∈_ _≤_ [1]

(1  _qX_ ) 1 _Hb(RqX_ ) _,_ _R_ [0, Hb(qX )], qX > 2[1] _[,]_
 _−_ _−_ _∈_

 

_Dncr(B(qX_ ), R) ≜ qYmin[0,1] _[D][ncr][(][B][(][q][X]_ [)][,][ B][(][q][Y][ )][, R][)]
_∈_

_qX_ _Hb−1(R),_ _R_ [0, Hb(qX )], qX 2 _[,]_
= _−_ _∈_ _≤_ [1]

1 _qX_ _Hb[−][1](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 (qX ) with and
_B_
without common randomness. In general, Dncr( (qX ), R) is different from Dmse( (qX ), R) (the
_B_ _B_
former is strictly above the latter). The reason is as follows: even though the output distribution
constraint is removed in the definition of Dncr( (qX ), R), the output alphabet remains to be 0, 1 ;
_B_ _{_ _}_
in contrast, for Dmse(B(qX ), R), the output alphabet is relaxed to R.


-----

A.5 AUXILIARY RESULTS

**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][ p][X][ and][ p][Y][ 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 finite-_
support 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_ ] + E[ _Y_ _Y_ ] + E[ _X_ _Y_ ] _Dncr(pX_ _, pY, R) +_ _[ϵ]_ (35)
_∥_ _−_ [ˆ] _∥[2]_ _∥_ _−_ [ˆ] ∥ _∥_ [ˆ] − [ˆ] ∥[2] _≤_ 2 _[.]_

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}i[N]=1[−][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}i[N]=1[−][1][}][E][[][∥][X][ −] _X[ˆ]_ _[′]∥[2]_ + ∥X[ˆ] _[′]_ _−_ _Y[ˆ] ∥[2]|X[ˆ] ∈{xˆi}i[N]=1[−][1][]]_

+ P{X[ˆ] ∈{xˆi}i[∞]=N _[}][E][[][∥][X][ −]_ _X[ˆ]_ _[′]∥[2]_ + ∥X[ˆ] _[′]_ _−_ _Y[ˆ] ∥[2]|X[ˆ] ∈{xˆi}i[∞]=N_ []]

= P{X[ˆ] ∈{xˆi}i[N]=1[−][1][}][E][[][∥][X][ −] _X[ˆ]_ _∥[2]_ + ∥X[ˆ] − _Y[ˆ] ∥[2]|X[ˆ] ∈{xˆi}i[N]=1[−][1][]]_

+ P{X[ˆ] ∈{xˆi}i[∞]=N _[}][E][[][∥][X][ −]_ _X[ˆ]_ _[′]∥[2]_ + ∥X[ˆ] _[′]_ _−_ _Y[ˆ] ∥[2]|X[ˆ] ∈{xˆi}i[∞]=N_ []]

_≤_ P{X[ˆ] ∈{xˆi}i[N]=1[−][1][}][E][[][∥][X][ −] _X[ˆ]_ _∥[2]_ + ∥X[ˆ] − _Y[ˆ] ∥[2]|X[ˆ] ∈{xˆi}i[N]=1[−][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}i[N]=1[−][1][}][E][[][∥][X][ −] _X[ˆ]_ _∥[2]_ + ∥X[ˆ] − _Y[ˆ] ∥[2]|X[ˆ] ∈{xˆi}i[N]=1[−][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_ ] + E[ _X_ _Y_ ] + _[ϵ]_ (36)
_≤_ _∥_ _−_ [ˆ] _∥[2]_ _∥_ [ˆ] − [ˆ] ∥[2] 2 _[.]_

Now define a new joint distribution pX, ˆX _[′′],Y[ˆ]_ _[′′],Y_ [such that][ p]X,X[ˆ] _[′′][ =][ p]X,X[ˆ]_ _[′][,][ p][ ˆ]X_ _[′′],Y[ˆ]_ _[′′][ =][ p][ ˆ]X_ _[′],Y[ˆ]_ [,]

_pY,Y ˆ_ _[′′][ =][ p]Y,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_ ] + E[ _Y_ _Y_ ] + E[ _X_ _Y_ ] + _[ϵ]_ (37)
_≤_ _∥_ _−_ [ˆ] _∥[2]_ _∥_ _−_ [ˆ] ∥ _∥_ [ˆ] − [ˆ] ∥[2] 2

_≤_ _Dncr(pX_ _, pY, R) + ϵ,_ (38)

where (37) and (38) are due to (35) and (36), 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_


-----

Figure 6: Illustration of the entropy-constrained optimal transport plan for the binary case (assuming

_b_ (R) _b_ (R)
_qX + qY ≤_ 1), where p ˆX [(ˆ]x) = p ˆY [(ˆ]y) = 1 − _Hb[−][1](R) with ˆx =_ _[q]1[X]−[−]H[H]b[−][−][1][1](R)_ [and][ ˆ]y = _[q]1[Y]−[ −]H[H]b[−][−][1][1](R)_ [.]

It is interesting to note that the quantizer p ˆX _X_ [does not depend on][ p][Y][ while the dequantizer][ p]Y _Y[ˆ]_
_|_ _|_
does not depend on pX . So they are decoupled in a certain sense. Moreover, p ˆX _X_ [and][ p]Y _Y[ˆ]_ [coincide]
_|_ _|_
respectively with optimal quantizer p ˆX _[∗]|X_ [and dequantizer][ p]Y |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][ p]X,X[ˆ] _[′][ =][ p]X,X[ˆ]_ [,][ p][ ˆ]X _[′],Y[ˆ]_ _[′][ =]_

_p ˆX,Y[˜]_ [,][ p]Y,Y[ˆ] _[′][ =][ p]Y,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.

A.6 UNIFORM DISTRIBUTION

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) = _a[1]_ _[,][ 0][ ≤]_ _[x][ ≤]_ _[a][ and][ p][Y][ (][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:


0xa,[,] _x0 ≤ ≤_ _x0 ≤,_ _a,_ _CY (y) =_
1, _x ≥_ _a,_


0yb,[,] 0y ≤ ≤ _y0 ≤,_ _b,_
1, _y ≥_ _b._


_CX_ (x) =


Following Peyre & Cuturi´ (2019, Remark 2.30) we have that the optimal transport (without rate
constraint) is given by:

1
_W2[2][(][p][X]_ _[, p][Y]_ [) =] (CX[−][1][(][r][)][ −] _[C]Y[−][1][(][r][))][2][dr][ = (][b][ −]_ _[a][)][2]_ _,_ (39)

0 3

Z

where CX[−][1][(][·][)][ and][ C]Y[−][1][(][·][)][ are the pseudo-inverse of the CDF functions for][ X][ and][ Y][ as defined in]

Peyr´e & 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[ˆ] :_
_∈{_ _}_


_a_
_Xˆ_ =
_∈_ _X[ˆ]_ 2N [,][ 3]2N [a] _[,][ 5]2N [a]_ _[, . . .,][ (2][N]2[ −]N_ [1)][a]


_b_
_Yˆ_ =
_∈_ _Y[ˆ]_ 2N [,][ 3]2N [b] _[,][ 5]2N [b]_ _[, . . .,][ (2][N]2[ −]N_ [1)][b]



(40)

(41)


To compute the upper bound we select p ˆX _X_ [to correspond to scalar quantization of][ X][ i.e., given][ X]
_|_

we select _X[ˆ] as a point in_ [ˆ] closest to X. The distribution p ˆY _Y_ [is defined in an analogous manner][3][ .]
_X_ _|_
Our upper bound can be computed as:

_Dncr[+]_ [(][p][X] _[, p][Y]_ _[, R][) =][ E][[(][X][ −]_ _X[ˆ]_ )[2]] + E[(Y − _Y[ˆ] )[2]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][.] (42)


Note that with ∆= _N[1]_ [we have that][ E][[(][X][ −] _X[ˆ]_ )[2]] = _[a][2]12[∆][2]_ and E[(Y − _Y[ˆ] )[2]] =_ _[b][2]12[∆][2]_ [. Thus we only]

need to compute the third term. Following Peyr´e & Cuturi (2019, Remark 2.28) we have that:


_W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [) = (][b][ −] _[a][)][2][∆][2]_

4N


_N_

(2i 1)[2] = [(][b][ −] _[a][)][2]_
_−_ 3
_i=1_

X


1
_−_ [∆]4[2]


(43)


Thus using ∆[2] = 2[−][2][R], we have that

_Dncr[+]_ [(][p][X] _[, p][Y]_ _[, R][) = (][b][ −]_ _[a][)][2]_


_Dncr[+]_ [(][p][X] _[, p][Y]_ _[, R][) = (][b][ −]_ _[a][)][2]_ + _[a][ ·][ b]_ (44)

3 6 [2][−][2][R][.]

Note that the upper bound approaches the lower bound in (39) as R →∞, with exponential rate of
convergence.

For the case of general R, we let N = ⌈2[R]⌉ and following Gyorgy & Linder (2000, Theorem 1), we
select

_ac_

_Xˆ_ =  _, a_ _c +_ _[c][′]_ _, a_ _c + 3_ _[c][′]_ _, . . ., a_ _c + (2N_ 3) _[c][′]_  _,_
_∈_ _X[ˆ]_  2  2   2   _−_ 2 

_xˆ1_ _xˆ2_ _xˆ3_ _xˆN_ (45)

|{z} | {z } | {z } | {z }

_bc_

_Yˆ_ =  _, b_ _c +_ _[c][′]_ _, b_ _c + 3_ _[c][′]_ _, . . ., b_ _c + (2N_ 3) _[c][′]_  _,_
_∈_ _Y[ˆ]_  2  2   2   _−_ 2 

_yˆ1_ _yˆ2_ _yˆ3_ _yˆN_

3Please note that we do not claim that the proposed choice is optimal with respect to|{z} | {z } | {z } | {z _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.


_ac_

_, a_ _c +_ _[c][′]_

2 2



_xˆ1_ _xˆ2_
|{z} | {z

_bc_

_, b_ _c +_ _[c][′]_



_, a_ _c + 3_ _[c][′]_



-----

4.25

W2[2][(][p][X][,][ p][Y][)] E(X X)[2]

1.4

4.00 W2[2][(][p][X][,][ p][Y][)] E(Y Y)[2]

Dncr[+] [(][p][X][,][ p][Y][,][ R][)] 1.2

3.75

1.0

3.50

0.8

3.25

0.6

3.00

0.4

2.75

0.2

2.50 0.0

1 2 3 4 5 1 2 3 4 5

Rate Rate


Figure 7: Example of Uniform sources with a = 2 and b = 5. The left plot shows the lower bound
_W2[2][(][p][X]_ _[, p][Y]_ [)][ in][ (][39][)][ and the upper bound][ D]ncr[+] [(][p][X] _[, p][Y]_ _[, R][)][ which is the sum of of the right hand]_
side in (46), (47) and (50). For comparison we also show the value of W2[2][(][p][ ˆ]X _[, p]Y[ ˆ]_ [)][. The right plot]
shows the distortions associated with the quantization and dequantization steps.

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]N[−][c]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 = log2 N we will have that c = c[′] = _N[1]_ [and our construction for]

_Xˆ and_ _Y[ˆ] is consistent with the previous case._

As before we use p ˆX _X_ [and][ p][ ˆ]Y _Y_ [to be the distributions associated with scalar quantization. Thus we]
_|_ _|_
have that:


E[(X − _X[ˆ]_ )[2]] = c _[a]12 [2][c][2]_ [+ (1][ −] _[c][)]_ _[a][2]12[c][′][2]_ _[,]_ (46)


E[(Y − _Y[ˆ] )[2]] = c_ _[b]12 [2][c][2]_ [+ (1][ −] _[c][)]_ _[b][2]12[c][′][2]_ _[.]_ (47)

Furthermore using the result stated in Peyr´e & Cuturi (2019, Remark 2.30) we have that


_W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [) =][ c][(ˆ]x1 − _yˆ1)[2]_ + c[′]


(ˆxj _yˆj)[2]_ (48)
_j=2_ _−_

X


_N_ _−1_ 2

= (b − _a)[2][ c]4 [3]_ [+ (][b][ −] _[a][)][2][c][′]_ _c + [2][j][ −]2_ [1] _c[′]_ (49)

_j=1_  

X

_c3_
= (b − _a)[2]_ 4 [+][ c][2][c][′][(][N][ −] [1) +][ cc][′][2][(][N][ −] [1)][2][ + 1]12 _[c][′][3][(2][N][ −]_ [1)(2][N][ −] [3)(][N][ −] [1)]


(50)

Finally, the upper bound Dncr[+] [(][p][X] _[, p][Y]_ _[, R][)][ can be obtained by summing the right hand side]_
of (46), (47) and (50). We provide a numerical evaluation of this upper bound in Fig. 7.

A.7 ASYMPTOTIC OPTIMAL TRANSPORT

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

_Dncr[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≜]_ [inf] ncr[(][p][X] _[, p][Y]_ _[, R][)][,]_
_n_ 1 _[D][(][n][)]_
_≥_

where


_Dncr[(][n][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≜]_ inf
_pXn,Z,Y n_ _∈Mncr(⊗i[n]=1[p][X]_ _[,][⊗][n]i=1[p][Y][ )]_

1
s.t.
_n_ _[H][(][Z][)][ ≤]_ _[R.]_


E[d(Xi, Yi)]
_i=1_

X


Remark: It is clear that Dncr[(1)] [(][p]X _[, p]Y_ _[, R][) =][ D]ncr[(][p]X_ _[, p]Y_ _[, R][)][. Moreover, one can readily show]_
that {nDncr[(][n][)][(][p]X _[, p]Y_ _[, R][)][}][∞]n=1_ [is a subadditive sequence and consequently][ D]ncr[(][∞][)][(][p]X _[, p]Y_ _[, R][) =]_
limn _Dncr[(][n][)][(][p]X_ _[, p]Y_ _[, R][)][.]_
_→∞_

**Theorem 5. We have**

_Dncr[(][∞][)][(][p][X]_ _[, p][Y]_ _[, 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**


_Dmse[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≜]_ _p ˆX_ _Xinf[,p][ ˆ]Y_ _Y_ E[∥X − _X[ˆ]_ _∥[2]] + E[∥Y −_ _Y[ˆ] ∥[2]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)]
_|_ _|_ (51)

_s.t._ E[X|X[ˆ] ] = X,[ˆ] E[Y |Y[ˆ] ] = Y,[ˆ] _I(X; X[ˆ]_ ) ≤ _R,_ _I(Y ; Y[ˆ] ) ≤_ _R,_

_and_
_Dmse(pX_ _, R) ≜_ inf E[ _X_ _X_ ]
_p ˆX_ _X_ _∥_ _−_ [ˆ] _∥[2]_
_|_ (52)

_s.t._ _I(X; X[ˆ]_ ) ≤ _R._

_Moreover, let_

_D(ncr∞)[(][p][X]_ _[, p][Y]_ _[, R][)][ ≜]_ _[D]mse[(][∞][)][(][p][X]_ _[, R][) +][ D]mse[(][∞][)][(][p][Y]_ _[, R][) +][ W][ 2]2_ [(][p][ ˆ]X _[∗]_ _[, p]Y[ ˆ]_ _[∗]_ [)][,] (53)

_D[(]ncr[∞][)][(][p][X]_ _[, p][Y][, R][)][ ≜]_ _[D]mse[(][∞][)][(][p][X]_ _[, R][) +][ D]mse[(][∞][)][(][p][Y]_ _[, R][)][,]_ (54)


_where p ˆX_ _[∗]_ _[and][ p][ ˆ]Y_ _[∗]_ _[are the marginal distributions induced by the minimizers][ p][ ˆ]X_ _[∗]|X_ _[and][ p][ ˆ]Y_ _[∗]|Y_ _[that]_

_attain Dmse[(][∞][)][(][p]X_ _[, R][)][ and][ D]mse[(][∞][)][(][p]Y_ _[, R][)][, respectively (assuming the existence and uniqueness of such]_
_minimizers). Then under the squared Eucledian distortion measure,_

_Dncr[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][) =][ D]mse[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][.]_ (55)


_In addition, we have_

_D(ncr∞)[(][p][X]_ _[, p][Y]_ _[, R][)][ ≥]_ _[D]ncr[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≥]_ _[D][(]ncr[∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][,]_ (56)

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


-----

_Dmse[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][,]_
_≥_

where the last inequality follows from the definition of Dmse[(][∞][)][(][p]X _[, p]Y_ _[, 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 Dncr[(][∞][)][(][p]X _[, p]Y_ _[, R][)][ ≥]_ _[D]mse[(][∞][)][(][p]X_ _[, p]Y_ _[, R][)][. On the other hand,]_
for any p ˆX|X [,][ p][ ˆ]Y |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_ [=][ p][X] _[p][ ˆ]X|X_ [,][ p]Y,Y[ˆ] [=][ p][Y][ p][ ˆ]Y |Y [, and][ p][ ˆ]X,Y[ˆ] [satisfying][ E][[][∥]X[ˆ] − _Y[ˆ] ∥[2]] = W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][. 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]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][.] (57)

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 (57), implies_
_Dncr[(][∞][)][(][p]X_ _[, p]Y_ _[, R][)][ ≤]_ _[D]mse[(][∞][)][(][p]X_ _[, p]Y_ _[, R][)][. This completes the proof of (][55][).]_

Dropping the term W2[2][(][p][ ˆ]X _[, p]Y[ ˆ]_ [)][ in (][51][) yields]


_Dncr[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≥]_ _D[˜]_ mse[(][∞][)][(][p][X] _[, R][) + ˜]Dmse[(][∞][)][(][p][Y]_ _[, R][)][,]_

_D˜_ mse[(][∞][)][(][p][X] _[, R][)][ ≜]_ _p[inf] ˆX_ _X_ E[∥X − _X[ˆ]_ _∥[2]]_
_|_

s.t. E[X|X[ˆ] ] = X,[ˆ] _I(X; X[ˆ]_ ) ≤ _R._


where


and _D[˜]_ mse(pY, R) is definely analogously. On the other hand, choosing p ˆX|X [=][ p][ ˆ]X _[′]|X_ [and][ p][ ˆ]Y |Y [=]
_p ˆY_ _[′]|Y_ [in (][51][) gives]

_Dncr[(][∞][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≤]_ _D[˜]_ mse[(][∞][)][(][p][X] _[, R][) + ˜]Dmse[(][∞][)][(][p][Y]_ _[, R][) +][ W][ 2]2_ [(][p][ ˆ]X _[′]_ _[, p]Y[ ˆ]_ _[′]_ [)][,]

where p ˆX _[′]|X_ [and][ p][ ˆ]Y _[′]|Y_ [are the minimizers that attain][ ˜]Dmse[(][∞][)][(][p]X _[, R][)][ and][ ˜]Dmse[(][∞][)][(][p]Y_ _[, R][)][ respectively]_
while p ˆX _[′][ and][ p][ ˆ]Y_ _[′][ are their induced marginal distributions. It is clear that][ p][ ˆ]X_ _[′]|X_ [and][ p][ ˆ]Y _[′]|Y_ [coincide]

with p ˆX _[∗]|X_ [and][ p][ ˆ]Y _[∗]|Y_ [respectively as the constraints][ E][[][X][|][ ˆ]X] = X[ˆ] and E[Y |Y[ˆ] ] = Y[ˆ] are automatically satisfied by p ˆX _[∗]|X_ [and][ p][ ˆ]Y _[∗]|Y_ [. This proves (][56][). For the special case][ p][X][ =][ p][Y][, we have]
_p ˆX_ _[∗]|X_ [=][ p][ ˆ]Y _[∗]|Y_ [and consequently the upper bound and the lower bound in (][56][) 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

_Dcr[(][∞][)](pX_ _, pY, R) ≜_ inf cr [(][p][X] _[, p][Y]_ _[, R][)][,]_
_n_ 1 _[D][(][n][)]_
_≥_

where


_Dcr[(][n][)][(][p][X]_ _[, p][Y]_ _[, R][)][ ≜]_ inf
_pU,Xn,Z,Y n_ _∈Mcr(⊗i[n]=1[p][X]_ _[,][⊗][n]i=1[p][Y][ )]_

1
s.t.
_n_ _[H][(][Z][|][U]_ [)][ ≤] _[R.]_


E[d(Xi, Yi)]
_i=1_

X


Remark: It is clear that Dcr[(1)][(][p]X _[, p]Y_ _[, R][) =][ D]cr[(][p]X_ _[, p]Y_ _[, R][)][. Moreover, one can readily show]_
that {nDcr[(][n][)][(][p]X _[, p]Y_ _[, R][)][}][∞]n=1_ [is a subadditive sequence and consequently][ D]cr[(][∞][)](pX _, pY, R) =_
limn _Dncr[(][n][)][(][p]X_ _[, p]Y_ _[, R][)][.]_
_→∞_


-----

**Theorem 7. We have**


_Dcr[(][∞][)](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.

A.8 GAUSSIAN CASE

Let X ∼N (µX _, σX[2]_ [)][ and][ Y][ ∼N] [(][µ][Y][, σ]Y[2] [)][ be two Gaussian random variables, and let][ d][(][·][,][ ·][)][ be]
the squared distortion measure (i.e., d(x, y) = (x − _y)[2]). Let Dmin[(][G][)]_ [≜] [(][µ][X][ −] _[µ][Y][ )][2][ + (][σ][X][ −]_ _[σ][Y][ )][2]_

and Dmax[(][G][)] [≜] [(][µ]X _[−]_ _[µ]Y_ [)][2][ +][ σ]X[2] [+][ σ]Y[2] [. Note that][ D]min[(][G][)] [is the squared Wasserstein-2 distance]
between N (µX _, σX[2]_ [)][ 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]] = Dmax[(][G][)]_ [for][ X][,][ Y][ independent. It is clear that]
_Dmin[(][G][)]_ [and][ D]max[(][G][)] [are the infimum and supremum of][ D]ncr[(][∞][)][(][N] [(][µ]X _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][ (as well as]
_Dcr[(][∞][)](N_ (µX _, σX[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][), respectively.]

**Theorem 8. Assume squared distortion measure. Under no common randomness, we have**


_Dncr[(][∞][)][(][N]_ [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][) =][ D]min[(][G][)] [+ 2][σ][X] _[σ][Y][ 2][−][2][R][,]_ _R ∈_ [0, ∞). (58)


_Moreover,_


_D(ncr∞)[(][N]_ [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][) =][ D]ncr[(][∞][)][(][N] [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][)][,] _R ∈_ [0, ∞), (59)

_D[(]ncr[∞][)][(][N]_ [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][) = (][σ]X[2] [+][ σ]Y[2] [)2][−][2][R][,] _R ∈_ [0, ∞). (60)

_With common randomness,_


_Dcr[(][∞][)](N_ (µX _, σX[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][) =][ D]max[(][G][)] _[−]_ [2][σ][X] _[σ][Y]_


1 − 2[−][2][R], _R ∈_ [0, ∞). (61)


_Proof. Consider p ˆX|X_ [and][ p][ ˆ]Y |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][ σ]X[2]ˆ [, respectively. Similarly, denote the mean and]
_Xthe variance ofˆ_ )[2]], and σY[2]ˆ [=]Y[ˆ][ σ] byY[2] _µ[−] ˆY[E][[(][and][Y][ −][ σ]Y[2]ˆY[ˆ][, respectively. Clearly,] )[2]]. Moreover,_ _[ µ][ ˆ]X_ [=][ µ][X] [,][ µ][ ˆ]Y [=][ µ][Y][,][ σ]X[2]ˆ [=][ σ]X[2] _[−]_ [E][[(][X][ −]

_W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)][ ≥] _[W][ 2]2_ [(][N] [(][µ][ ˆ]X _[, σ]X[2]ˆ_ [)][,][ N] [(][µ][ ˆ]Y _[, σ]Y[2]ˆ_ [))]

= (µ ˆX _[−]_ _[µ][ ˆ]Y_ [)][2][ + (][σ][ ˆ]X _[−]_ _[σ][ ˆ]Y_ [)][2]

= (µX − _µY )[2]_ + (σ ˆX _[−]_ _[σ][ ˆ]Y_ [)][2][.]

So we have

E[(X − _X[ˆ]_ )[2]] + E[∥Y − _Y[ˆ] ∥[2]] + W2[2][(][p][ ˆ]X_ _[, p]Y[ ˆ]_ [)]

_≥_ _σX[2]_ _[−]_ _[σ]X[2]ˆ_ [+][ σ]Y[2] _[−]_ _[σ]Y[2]ˆ_ [+ (][µ][X][ −] _[µ][Y][ )][2][ + (][σ][ ˆ]X_ _[−]_ _[σ][ ˆ]Y_ [)][2]

= Dmax[(][G][)] _[−]_ [2][σ][ ˆ]X _[σ][ ˆ]Y_ _[.]_ (62)

It can be verified that

_R ≥_ _I(X; X[ˆ]_ )

= [1]2 [log(2][πeσ]X[2] [)][ −] _[h][(][X][|][ ˆ]X)_

_≥_ 2 [1] [log(2][πeσ]X[2] [)][ −] _[h][(][X][ −]_ _X[ˆ]_ )


-----

_X_ [)][ −] [1] _X)[2]])_

_≥_ 2 [1] [log(2][πeσ][2] 2 [log(2][πe][E][[(][X][ −] [ˆ]

= [1] _σX[2]_ _,_

2 [log] _σX[2]_ _Xˆ_

_[−]_ _[σ][2]_


which implies

Similarly,


1 − 2[−][2][R]. (63)


_σ ˆX_

_[≤]_ _[σ][X]_


_σ ˆY_ 1 2[−][2][R]. (64)

_[≤]_ _[σ][Y]_ _−_

Substituting (63) and (64) into (62) and invoking (p55) in Theorem 6 shows

_Dncr[(][∞][)][(][N]_ [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][)][ ≥] _[D]min[(][G][)]_ [+ 2][σ][X] _[σ][Y][ 2][−][2][R][.]_

To see that this lower bound is tight, we can let


_X = X[ˆ] + N,_ (65)

_Y = Y[ˆ] + N,[ˆ]_ (66)

where _X[ˆ]_ _∼N_ (µX _, σX[2]_ [(1][ −] [2][−][2][R][))][ is independent of][ N] _∼N_ (0, σX[2] [2][−][2][R][)][ while][ ˆ]Y _∼_
_N_ (µY, σY[2] [(1][ −] [2][−][2][R][))][ is independent of][ ˆ]N ∼N (0, σY[2] [2][−][2][R][)][. This completes the proof of (][58][).]

To prove (59) and (60), it suffices to note the well-known fact that p ˆX _X_ [and][ p][ ˆ]Y _Y_ [associated with]
_|_ _|_

(65) and (66) attain Dmse[(][∞][)][(][N] [(][µ]X _[, σ]X[2]_ [)][, R][)][ and][ D]mse[(][∞][)][(][N] [(][µ]Y _[, σ]Y[2]_ [)][, R][)][, respectively.]

Now we proceed to prove (61). Consider pX,Y ∈ Γ(N (µX _, σX[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [))][ with][ I][(][X][;][ Y][ )][ ≤] _[R][.]_
Let ξ ≜ E[(X − _µX_ )(Y − _µY )]. We have_

E[(X _Y )[2]] = Dmax[(][G][)]_ (67)
_−_ _[−]_ [2][ξ.]

Moreover,

_R ≥_ _I(X; Y )_

= [1]2 [log(2][πeσ]X[2] [) + 1]2 [log(2][πeσ]Y[2] [)][ −] _[h][(][X, Y][ )]_

_X_ [) + 1] _Y_ [)][ −] [1] _X_ _[σ]Y[2]_

_≥_ 2 [1] [log(2][πeσ][2] 2 [log(2][πeσ][2] 2 [log((2][πe][)][2][(][σ][2] _[−]_ _[ξ][))]_

_σX[2]_ _[σ]Y[2]_

= [1]

2 [log] _σX[2]_ _[σ]Y[2]_

_[−]_ _[ξ][2][,]_

which implies

_ξ_ _σX_ _σY_ 1 2[−][2][R]. (68)
_≤_ _−_

Substituting (68) into (67) and invoking Theoremp 7 shows

_Dcr[(][∞][)](N_ (µX _, σX[2]_ [)][,][ N] [(][µ][Y] _[, σ]Y[2]_ [)][, R][)][ ≥] _[D]max[(][G][)]_ _[−]_ [2][σ][X] _[σ][Y]_ 1 − 2[−][2][R].

To see that this lower bound is tight, we can let X and Y be jointly Gaussian withp _ξ =_
_σX_ _σY_ _√1_ 2[−][2][R]. This completes the proof of Theorem 8. We acknowledge that the expres
_−_
sion of Dcr[(][∞][)](N (µX _, σX[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, 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 Dncr[(][∞][)][(][N] [(][µ]X _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][,][ D](ncr∞)[(][N] [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][,]
_D[(]ncr[∞][)][(][N]_ [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][, and][ D]cr[(][∞][)](N (µX _, σX[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][ for two illustrative ex-]
amples.


-----

(a) (b)

Figure 8: Gaussian case distortion-rate tradeoffs. (a) µX = µY = 0, σX = σY = 1,
where D(ncr∞)[(][N] [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][ and][ D]ncr[(][∞][)][(][N] [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][ coincide with]
_Dncr[(][∞][)][(][N]_ [(][µ]X _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][;][ (b)][ µ][X] = 0, σX = 1, µY = 1, σY = 2, where

_D(ncr∞)[(][N]_ [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][ is tight but][ D]ncr[(][∞][)][(][N] [(][µ][X] _[, σ]X[2]_ [)][,][ N] [(][µ][Y][, σ]Y[2] [)][, R][)][ is loose. More-]
over, it can be seen from both examples that common randomness can indeed help improve the
distortion-rate tradeoff.

B EXPERIMENTAL RESULTS

B.1 DATASET

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.

B.2 UNIVERSAL QUANTIZATION

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 minc∈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.

B.3 TRAINING DETAILS

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 ˜_ [) =] _∥∇suph∥≤1_ E[h(Y )] − E[h( Y[˜] )], (69)


-----

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 (15) 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 super-**
resolution. 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.

Table 3: Hyperparameters used for training end-to-end model in Fig. 4(a). α is the learning rate,
(β1, β2) are the parameters for Adam, and λGP is the gradient penalty coefficient.

_α_ _β1_ _β2_ _λGP_

Encoder 10[−][4] 0.5 0.999 - 
Decoder 10[−][4] 0.5 0.999 - 
Critic 10[−][4] 0.5 0.999 10

Table 4: Hyperparameters used for training two-branch model in Fig. 4(b). α is the learning rate,
(β1, β2) are the parameters for Adam, and λGP is the gradient penalty coefficient.

_α_ _β1_ _β2_ _λGP_

Encoder 0 -  -  - 
Decoder-1 10[−][4] 0.5 0.999 - 
Decoder-2 10[−][4] 0.5 0.999 - 
Critic 10[−][4] 0.5 0.999 10

B.4 DETAILED RESULTS IN FIGURE. 5

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.

B.5 COMPARISON WITH BASELINE

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 (image super-resolution and
denoising), we respectively build two U-Nets with skip connections and train them in the unsupervised
manner by adopting the Eq. 15 as objective i.e.,

_L1 = E[∥X −_ _Y[˜] ∥[2]] + λ1W1(pY, pY ˜_ [)][.] (70)

After the restoration networks are trained to converge, we fix their weights and use them to produce restored images _Y[˜] given degraded one X. Afterwards, we adopt our end-to-end network as_
compression network by minimizing the following loss at different rates:


-----

Table 5: The detailed number of MSE distortion loss in Fig. 5(a).

Super-resolution with Common Randomness

Rate 4 6 8 10 12 14 16 18

MSE 0.0515 0.0457 0.0420 0.0394 0.0372 0.0353 0.0339 0.0324

Rate 20 22 24 26 28 30 32 - 

MSE 0.0313 0.0300 0.0297 0.0285 0.0280 0.0277 0.0269 - 

Super-resolution without Common Randomness

Rate 4 6 8 10 12 14 16 18

MSE 0.0558 0.0506 0.0463 0.0435 0.0415 0.0396 0.0383 0.0367

Rate 20 22 24 26 28 30 32 - 

MSE 0.0351 0.0337 0.0331 0.0328 0.0315 0.0308 0.0300 - 

Table 6: The detailed number of MSE distortion loss in Fig. 5(c).

Image Denoising with Common Randomness


Rate 12 18 24 30 36 42 48 54 60

MSE 0.0219 0.0195 0.0175 0.01634 0.0154 0.0147 0.0138 0.0135 0.0129

Rate 66 72 78 84 90 96 102 108 114

MSE 0.0126 0.0123 0.0118 0.0117 0.0115 0.0112 0.0109 0.0107 0.0106

Image Denoising without Common Randomness

Rate 12 18 24 30 36 42 48 54 60

MSE 0.0230 0.0208 0.0189 0.0175 0.0165 0.0157 0.0151 0.0145 0.014

Rate 66 72 78 84 90 96 102 108 114

MSE 0.0137 0.0133 0.0130 0.0127 0.0123 0.0120 0.0118 0.0116 0.0114

_L1 = E[∥Y[˜] −_ _Y_ [+]∥[2]] + λW1(pY, pY + ), (71)

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 (70) and (71). For the image super-resolution, we experimentally selected λ1 = 0.05 and
_λ2 = 0.01. For the image denoising, we experimentally selected λ1 = 0.03 and λ2 = 0.005. 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 and denoising are respectively
shown in Table 7 and Table 8. It can easily check throughout the tables that our end-to-end systems
outperform the baselines.

B.6 COMPARISON WITH GROUND TRUTH

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 9
and 10. 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


-----

Table 7: Comparison between our end-to-end system with the baseline method for image superresolution. Numbers are the MSE distortion loss for a particular rate. Best results are in bold.

Super-resolution with Common Randomness

Rate 4 6 8 10 12 14 16 18

Baseline 0.0603 0.0568 0.0544 0.0530 0.0523 0.0511 0.0503 0.0498

Ours **0.0515** **0.0457** **0.0420** **0.0394** **0.0372** **0.0353** **0.0339** **0.0342**

Rate 20 22 24 26 28 30 32 - 

Baseline 0.0489 0.0485 0.0484 0.0482 0.0478 0.0476 0.0471 - 

Ours **0.0313** **0.0300** **0.0297** **0.0285** **0.0280** **0.0277** **0.0269** - 


Super-resolution without Common Randomness

Rate 4 6 8 10 12 14 16 18

Baseline 0.0620 0.0585 0.0573 0.0555 0.0543 0.0535 0.0532 0.0520

Ours **0.0558** **0.0506** **0.0463** **0.0435** **0.0415** **0.0396** **0.0383** **0.0367**

Rate 20 22 24 26 28 30 32 - 

Baseline 0.0517 0.0512 0.0506 0.0505 0.0497 0.0495 0.0490 - 

Ours **0.0351** **0.0337** **0.0331** **0.0328** **0.0315** **0.0308** **0.0300** - 

Table 8: Comparison between our end-to-end system with the baseline method for image denoising.
Numbers are the MSE distortion loss for a particular rate. Best results are in bold.

Image Denoising with Common Randomness

Rate 12 18 24 30 36 42 48 54 60

Baseline 0.0242 0.0213 0.0189 0.0173 0.0162 0.0154 0.0148 0.0142 0.0136

Ours 0.0219 0.0195 0.0175 0.0163 0.0154 0.0147 0.0138 0.0135 0.0129

Rate 66 72 78 84 90 96 102 108 114

Baseline 0.0134 0.0130 0.0127 0.0124 0.0120 0.0118 0.0116 0.0111 0.0110

Ours 0.0126 0.0123 0.0118 0.0117 0.0115 0.0112 0.0109 0.0107 0.0106


Image Denoising without Common Randomness

Rate 12 18 24 30 36 42 48 54 60

Baseline 0.0252 0.0216 0.0202 0.0185 0.0178 0.0164 0.0158 0.0154 0.0149

Ours 0.0230 0.0208 0.0189 0.0175 0.0165 0.0157 0.0151 0.0145 0.014

Rate 66 72 78 84 90 96 102 108 114

Baseline 0.0147 0.0144 0.0140 0.0135 0.0133 0.0129 0.0126 0.0120 0.0117

Ours 0.0137 0.0133 0.0130 0.0127 0.0123 0.0120 0.0118 0.0116 0.0114


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

Table 9: Illustration of MSE distortion between network outputs and ground truth for super-resolution.

Super-resolution with Common Randomness

Rate 4 8 12 16 20 24 28 32

MSE 0.0582 0.0464 0.0408 0.0380 0.0360 0.0353 0.0348 0.0343

Super-resolution without Common Randomness

Rate 4 8 12 16 20 24 28 32

MSE 0.0646 0.0492 0.0426 0.0390 0.0375 0.0362 0.0353 0.0345


-----

Table 10: Illustration of MSE distortion between network outputs and ground truth for image
denoising.

Image Denoising with Common Randomness

Rate 12 24 36 48 60 72 84 96 108

MSE 0.0157 0.0114 0.0092 0.0077 0.0069 0.0062 0.0056 0.0052 0.0047

Image Denoising without Common Randomness

Rate 12 24 36 48 60 72 84 96 108

MSE 0.0169 0.0128 0.0104 0.0090 0.0080 0.0072 0.0066 0.0060 0.0057

B.7 BREAKDOWN OF THE TABLE 1

It is worth reminding that the each number in Table 1 is the total distortion 18. 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]]._

B.8 NETWORK ARCHITECTURE

**Super-resolution. The detailed network structure for end-to-end model and two-branch model are**
respectively presented in Table 12 and Table 13. 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 respec-**
tively presented in Table 14 and Table 15. The last linear layer of the encoder controls the number of
output symbols.

Table 11: Breakdown of the Table 1. At any rate, it can be observed that the total losses of our
approximation system (L2) are very close to that of end-to-end learning system under the setting
without common randomness (E[∥X − _Y[˜] ∥[2]])._

Image Super-resolution Using Joint Training

Rate E[∥X − _Y[˜]1∥[2]]_ E[∥Y[˜] − _Y[˜]2∥[2]]_ E[∥Y[˜]1 − _Y[˜]2∥[2]]_ _L2_ E[∥X − _Y[˜] ∥[2]]_

4 0.0355 0.0227 0.0004 **0.0586** **0.0558**
10 0.0223 0.0222 0.0008 **0.0453** **0.0435**
20 0.0136 0.0191 0.00013 **0.0349** **0.0351**
30 0.00122 0.0172 0.0015 **0.0309** **0.0308**

Image Denoising Using Joint Training

Rate E[∥X − _Y[˜]1∥[2]]_ E[∥Y[˜] − _Y[˜]2∥[2]]_ E[∥Y[˜]1 − _Y[˜]2∥[2]]_ _L2_ E[∥X − _Y[˜] ∥[2]]_

12 0.01911 0.00497 0.00020 **0.02428** **0.02302**
30 0.01458 0.00435 0.00026 **0.01919** **0.01746**
60 0.01168 0.00378 0.00032 **0.01578** **0.01401**
90 0.01035 0.00323 0.00028 **0.01386** **0.01229**


-----

Table 12: Model architectures of end-to-end network used in super-resolution.


Encoder


Decoder


Critic


Input

Conv2D, l-ReLU
Conv2D, l-ReLU
Conv2D, l-ReLU

Linear


Input

Linear, BatchNorm1D, l-ReLU
Linear, BatchNorm1D, l-ReLU

Unflatten

ConvT2D, BatchNorm2D, l-ReLU
ConvT2D, BatchNorm2D, l-ReLU

ConvT2D, BatchNorm2D, Sigmoid


Input

Conv2D, l-ReLU
Conv2D, l-ReLU

Flatten

Linear, l-ReLU
Linear, l-ReLU

Linear, Tanh

Quantizer


Table 13: Model architectures of two-branch network used in super-resolution.


Encoder


Decoder1 and 2


Input

Linear, BatchNorm1D, l-ReLU
Linear, BatchNorm1D, l-ReLU

Unflatten

ConvT2D, BatchNorm2D, l-ReLU
ConvT2D, BatchNorm2D, l-ReLU

ConvT2D, Sigmoid


Input

Conv2D, l-ReLU
Conv2D, l-ReLU

Flatten

Linear, l-ReLU
Linear, l-ReLU

Linear, Tanh

Quantizer


Table 14: Model architectures of end-to-end network used in image denoising.


Encoder


Decoder


Critic


Input

Conv2D, l-ReLU
Conv2D, l-ReLU
Conv2D, l-ReLU

Linear


Input

Conv2D, l-ReLU
Conv2D, l-ReLU
Conv2D, l-ReLU

Flatten

Linear, Tanh

Quantizer


Input

Linear, BatchNorm1D, l-ReLU
Linear, BatchNorm1D, l-ReLU

Unflatten

ConvT2D, BatchNorm2D, l-ReLU
ConvT2D, BatchNorm2D, l-ReLU
ConvT2D, BatchNorm2D, l-ReLU

ConvT2D, BatchNorm2D, Sigmoid


Table 15: Model architectures of two-branch network used in image denoising. ResBlock is formed
using two Conv2D and skip connection.


Encoder


Decoder1 and 2


Input

Conv2D, l-ReLU
Conv2D, l-ReLU
Conv2D, l-ReLU

Flatten

Linear, Tanh

Quantizer


Input

Linear, BatchNorm1D, l-ReLU
Linear, BatchNorm1D, l-ReLU

Unflatten

ConvT2D, l-ReLU

ResBlock, ConvT2D, l-ReLU
ResBlock, ConvT2D, l-ReLU

ResBlock, ConvT2D, Sigmoid


-----

