# A Rate-Distortion Analysis for Composite Sources Under Subsource-Dependent
Fidelity Criteria

Jiakun Liu, H. Vincent Poor, Iickho Song, and Wenyi Zhang Jiakun Liu and Wenyi
Zhang are with the Department of Electronic Engineering and Information
Science, University of Science and Technology of China, Hefei 230027, China
(e-mail<EMAIL_ADDRESS>wenyizha@ustc.edu.cn).H. Vincent Poor is with
the Department of Electrical Engineering, Princeton University, Princeton, NJ
08544, USA (e-mail: poor@princeton.edu).Iickho Song is with the School of
Electrical Engineering, Korea Advanced Institute of Science and Technology,
291 Daehag Ro, Yuseong Gu, Daejeon 34141, Republic of Korea (e-mail:
i.song@ieee.org).

###### Abstract

A composite source, consisting of multiple subsources and a memoryless switch,
outputs one symbol at a time from the subsource selected by the switch. If
some data should be encoded more accurately than other data from an
information source, the composite source model is suitable because in this
model different distortion constraints can be put on the subsources. In this
context, we propose subsource-dependent fidelity criteria for composite
sources and use them to formulate a rate-distortion problem. We solve the
problem and obtain a single-letter expression for the rate-distortion
function. Further rate-distortion analysis characterizes the performance of
classify-then-compress (CTC) coding, which is frequently used in practice when
subsource-dependent fidelity criteria are considered. Our analysis shows that
CTC coding generally has performance loss relative to optimal coding, even if
the classification is perfect. We also identify the cause of the performance
loss, that is, class labels have to be reproduced in CTC coding. Last but not
least, we show that the performance loss is negligible for asymptotically
small distortion if CTC coding is appropriately designed and some mild
conditions are satisfied.

###### Index Terms:

Composite source, fidelity criterion, image processing, label-based code,
quantization, rate distortion theory, source coding, speech processing.

##  I Introduction

It is a common practice in rate-distortion (RD) theory [1, 2, 3, 4, 5] to
model an information source as a stochastic process
$\\{X_{i}\\}_{i=1}^{\infty}$. Each random variable $X_{i}$ is called a source
symbol or just a symbol. Symbols of many real-world sources can be naturally
divided into a few classes. For example, a pixel in a digital image may be in
the foreground or background [6], and a sample in a piece of speech signal may
belong to a voiced phoneme, an unvoiced phoneme, or a period of silence [7].
Symbols in different classes usually have different statistical
characteristics and are produced by different physical mechanisms. Thus, it is
not unreasonable to think of them as being produced by different subsources,
as done in the composite source model (see, for example, [3, Section 6.1]).
Besides the subsources, a composite source contains a conceptual switch, whose
position may vary with time. As shown in Figure 1, the source outputs a symbol
produced by Subsource $S$, which is selected by the switch. We refer to $S$ as
the state of the composite source. A composite source is modeled as a
stochastic process $\\{(S_{i},X_{i})\\}_{i=1}^{\infty}$ of state-symbol pairs,
where $\\{S_{i}\\}_{i=1}^{\infty}$ take values in a common finite set, say
$\\{1,2,\cdots,L\\}$.

Subsource 1Subsource 2$\vdots$Subsource $L$State
$S\in\\{1,2,\cdots,L\\}$Symbol $X$ producedby Subsource $S$ Figure 1: A
composite source with $L$ subsources.

In lossy compression of composite sources, we may wish to reproduce the
symbols from some subsources more accurately than the symbols from other
subsources. For example, an obscure foreground has a larger impact on the
quality of an image than an obscure background does. Thus, the distortion
constraint on the background can be loosened when we have to compress the
image into fewer bits. Similarly, a sample of an unvoiced phoneme is more
important than a sample of a silence period, and therefore the fidelity of the
former sample should be guaranteed first in low-rate coding of speech. This
idea applies to general information sources and has been implemented in some
source coding techniques such as JPEG, where pixels in regions of interest
(ROIs) are coded with higher quality [8].

In this paper, we propose a new type of fidelity criteria, called subsource-
dependent fidelity criteria, that impose different distortion constraints on
the subsources. We study an RD problem based on the criteria and obtain a
single-letter expression for the RD function. The classical fidelity criterion
can be viewed as a special case of the proposed criteria.

Subsource-dependent fidelity criteria reflect the need to treat subsources of
a composite source differently, and a technique widely adopted to fulfill the
need is classify-then-compress (CTC) coding, i.e. dividing the source symbols
into a few classes and then compressing the classes separately. See Section
I-A for examples. Here the idea behind CTC coding is that if most symbols in a
class are produced by the same subsource, then the class can be compressed
according to distortion constraints on the subsource. In this paper, we fix an
arbitrary classifier and design the coding of the individual classes for good
CTC coding performance. The optimal performance is characterized by another RD
function. Comparison of the RD functions provides interesting insights,
including:

  1. 1.

CTC coding in general has performance loss relative to RD-optimal coding, even
if the classification is perfect;

  2. 2.

The cause of the performance loss is that class labels have to be reproduced
in CTC coding, while separate compression of source symbols in different
classes in CTC coding does not cause performance loss; and

  3. 3.

The performance loss of CTC coding is negligible for asymptotically small
distortion if the coding is appropriately designed and some mild conditions
are satisfied.

A difficulty in the analysis of CTC coding is how to establish a mathematical
model for CTC coding, which we address by using variable-length codes. A key
tool in our proofs is a generalization of the conditional RD function [9, 10]
to subsource-dependent fidelity criteria, which may be of independent
interest.

This paper is organized as follows. In the remaining part of this section we
introduce related works and our notation. In Section II, we propose subsource-
dependent fidelity criteria and present other definitions that will be used in
the following sections. In Section III, we present our main results, including
coding theorems and analysis on CTC coding. Section IV outlines the proofs of
the coding theorems and Section V concludes the paper. Detailed proofs are
given in the appendices.

###  I-A Related Works

The first theoretical studies of the lossy compression problem were by Shannon
[1, 2]. Later many variants of the problem were considered. Many variants
involve some side information, which is usually a correlated source. For
example, if both the encoder and the decoder know the side information, the
problem becomes Gray’s conditional RD problem [9, 10]. If only the decoder
knows the side information, the problem becomes the one studied by Wyner and
Ziv in [11]. If the side information is chosen by some adversary, the problem
becomes Berger’s source coding game [3, Section 6.1.2] [12]. The side
information can also influence distortion measures [13, 14]. Another important
variant of the lossy compression problem is the indirect RD problem [3,
Section 3.5] [15, 16, 17], where the encoder observes noisy versions of source
symbols instead of source symbols themselves. In our work, the encoder and
decoder cannot observe states of composite sources directly, which affect how
distortion measures are applied to source symbols.

The composite source model was studied as early as in [3, Section 6.1], where
the state of a composite source could vary statistically or be controlled by
an adversary. For a composite source with a statistically varying state, both
the encoder and the decoder could have different knowledge of the switch
position, and this led to different RD functions. Each of the RD functions was
shown to equal the RD function of an appropriately chosen information source
without a state. If the state is controlled by an adversary, the problem is
modeled as the source coding game.

The composite source model turns out to be very versatile. Firstly,
information sources with uncertain statistical characteristics can be viewed
as mixtures of different sources, i.e. composite sources [3, Section 6.1.2]
[12, 18]. Secondly, some complex information sources can be decomposed into
simpler subsources and regarded as composite sources to facilitate analysis.
For example, some sources that are neither discrete nor continuous can be
decomposed into discrete and continuous components so that the behavior of
their RD functions at asymptotically small distortions can be characterized
[19, 20]. Sparse sources can be viewed as composite sources whose subsources
tend to output signals with different magnitudes [21]. A topic beyond our
scope here is that non-ergodic sources can be considered as mixtures of
ergodic ones [22].

The composite source model is also a good model for many real-world sources
such as speech, images, and videos [23, 7, 24, 25]. Two classes of composite
source models, i.e. hidden Markov and Gaussian mixture models [26], have been
widely adopted in the analysis and processing of real-world sources. In our
work, each composite source is assumed to have a finite number of subsources.
As pointed out in [3] and in [22], a generalized composite source can have
uncountably many subsources, and the state of such a source is a continuous
variable. Generative machine learning models with latent variables, such as
generative adversarial networks [27], variational autoencoders [28], and
diffusion models [29], can be viewed as generalized composite sources, with
latent variables viewed as source states.

Although RD problems on composite sources have been studied extensively,
existing RD analysis does not consider the need to treat subsources of a
composite source differently. Such consideration is important to lossy source
coding, and especially to lossy source coding in semantic communications [30].
In a series of recent works [31, 32, 33, 34, 35, 36, 37], inference is made on
hidden states of information sources, which are regarded as the meaning or
semantics of the sources. In our work, states can represent the importance of
the corresponding output data. By putting subsource-dependent fidelity
criteria on only the important data, we can provide another interpretation of
semantic communications.

CTC coding is widely adopted in situations where subsource-dependent fidelity
criteria are relevant. For speech signals, almost every successful coder uses
different modes for different parts of the signals [23, 25, 38]. For digital
images, the pixels in ROIs, such as the ROIs in JPEG, comprise a class encoded
with higher quality and the other pixels comprise a class encoded with lower
quality. In remote video analytics systems, relevant and irrelevant pixels
usually have to be compressed with different quality levels so that the video
transmission bandwidth can be reduced to an acceptable level (see, for
example, [39] and references therein). CTC coding is also adopted for other
purposes. For example, information sources can be modeled as composite sources
with Gaussian subsources. This model enables designs of robust CTC quantizers
with low computational complexity and variable rates [40, 41, 42]. In spite of
its wide applications, information-theoretical evaluation of CTC coding based
on subsource-dependent fidelity criteria is absent up to now.

###  I-B Notation

The set of real numbers is denoted by $\mathbb{R}$. For $a$,
$b\in\mathbb{R}\cup\\{-\infty,\infty\\}$, $(a:b]$ denotes the set of integers
$n$ satisfying $a<n\leq b$, and $(b]$ denotes a shorthand for $(0:b]$.
Similarly, $[a:b)$ denotes the set of integers $n$ satisfying $a\leq n<b$, and
$[b)$ denotes a shorthand for $[0:b)$. Thus, $[1:\infty)$ denotes the set of
positive integers, and $[\infty)$ denotes the set of non-negative integers.
The infimum of the empty set $\emptyset$ is considered as $\infty$.

For a set $J=\\{i_{1},i_{2},\cdots,i_{k}\\}$ of integers such that
$i_{1}<i_{2}<\cdots<i_{k}$, we let $x_{J}$ denote the sequence
$(x_{i_{1}},x_{i_{2}},\cdots,x_{i_{k}})$. Thus, $x_{(n]}$ is the sequence
$(x_{1},x_{2},\cdots,x_{n})$. This sequence is also written as
$\\{x_{i}\\}_{i=1}^{n}$ or as the boldface letter $\boldsymbol{x}$. The length
of a sequence $\boldsymbol{x}$ is denoted by $|\boldsymbol{x}|$. For two
sequences $\boldsymbol{x}$ and $\boldsymbol{y}$,
$\boldsymbol{x}\boldsymbol{y}$ denotes their concatenation. For any set $A$,
the class of all finite sequences composed of the elements of $A$, including
the empty sequence, is denoted by $A^{*}$.

We write $X\leftrightarrow Y\leftrightarrow Z$ if $X$, $Y$, and $Z$ are random
variables and form a Markov chain. All entropies and mutual information are in
units of bits.

##  II Definitions

###  II-A Subsource-Dependent Fidelity Criteria

Let $\mathcal{S}$, $\mathcal{X}$, and $\hat{\mathcal{X}}$ be sets, and
$\mathcal{S}$ be finite. Suppose random pairs $(S_{1},X_{1})$,
$(S_{2},X_{2})$, $\cdots$ are independent and identically distributed (i.i.d.)
and take values in $\mathcal{S}\times\mathcal{X}$. We refer to
$\\{(S_{i},X_{i})\\}_{i=1}^{\infty}$ as a memoryless composite source. For
$i\in[1:\infty)$, $X_{i}$ is an output symbol and is thought to be produced by
Subsource $S_{i}$. Let $\\{s_{i}\\}_{i=1}^{n}\in\mathcal{S}^{n}$ and
$\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$ be realizations of
$\\{S_{i}\\}_{i=1}^{n}$ and $\\{X_{i}\\}_{i=1}^{n}$, respectively. Suppose
$\\{x_{i}\\}_{i=1}^{n}$ is reproduced as
$\\{\hat{x}_{i}\\}_{i=1}^{n}\in\hat{\mathcal{X}}^{n}$.

A classical fidelity criterion requires

$\frac{1}{n}\sum_{i=1}^{n}d(x_{i},\hat{x}_{i})\leq\delta,$ (1)

where $\delta\in[0,\infty)$ and $d$ is a distortion measure on
$\mathcal{X}\times\hat{\mathcal{X}}$, i.e. a function from
$\mathcal{X}\times\hat{\mathcal{X}}$ to $[0,\infty)$. For $x\in\mathcal{X}$
and $\hat{x}\in\hat{\mathcal{X}}$, $d(x,\hat{x})$ is the distortion level of
$\hat{x}$ as a reproduction of $x$. The larger $d(x,\hat{x})$, the lower the
fidelity. Unlike (1), the subsource-dependent fidelity criterion involves the
state sequence $s_{(n]}$ and a subset $\mathcal{S}_{*}$ of $\mathcal{S}$, in
addition to $x_{(n]}$, $\hat{x}_{(n]}$, $d$, and $\delta$. We say $s_{(n]}$,
$x_{(n]}$, and $\hat{x}_{(n]}$ meet the fidelity criterion
$(d,\mathcal{S}_{*},\delta)$ if

$\sum_{i\in(n],s_{i}\in\mathcal{S}_{*}}(d(x_{i},\hat{x}_{i})-\delta)\leq 0.$
(2)

When the number $m=|\\{i\in(n]|s_{i}\in\mathcal{S}_{*}\\}|$ of terms
satisfying $s_{i}\in\mathcal{S}_{*}$ is non-zero, (2) can be written as

$\frac{1}{m}\sum_{i\in(n],s_{i}\in\mathcal{S}_{*}}d(x_{i},\hat{x}_{i})\leq\delta,$
(3)

implying that the average distortion of the symbols from the subsources in
$\mathcal{S}_{*}$ does not exceed $\delta$. If $\mathcal{S}_{*}=\mathcal{S}$,
the fidelity criterion $(d,\mathcal{S}_{*},\delta)$ is equivalent to the
classical fidelity criterion. If $\mathcal{S}_{*}\not=\mathcal{S}$, the
criterion $(d,\mathcal{S}_{*},\delta)$ measures fidelity of the symbols from
the subsources in $\mathcal{S}_{*}$.

We will consider a family
$\\{(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda))\\}_{\lambda\in\Lambda}$ of
fidelity criteria indexed by a finite set $\Lambda$, where for
$\lambda\in\Lambda$, $d_{\lambda}$ is a distortion measure on
$\mathcal{X}\times\hat{\mathcal{X}}$, $\mathcal{S}_{\lambda}$ is a subset of
$\mathcal{S}$, and $D(\lambda)\in[0,\infty)$ is a distortion level. For
example, we can let $\Lambda=\mathcal{S}$ and
$\mathcal{S}_{\lambda}=\\{\lambda\\}$ for $\lambda\in\Lambda$. Then the
fidelity criteria
$\\{(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda))\\}_{\lambda\in\Lambda}$
require that the average distortion of symbols from Subsource $s$ does not
exceed $D(s)$, for all $s\in\mathcal{S}$. We can define
$\\{\mathcal{S}_{\lambda}\\}_{\lambda\in\Lambda}$ in a more flexible fashion
to describe many other fidelity requirements.

###  II-B Variable-Length Codes and CTC Coding

The number of symbols in a class in CTC coding is usually random. Hence, we
use variable-length codes in our analysis of CTC coding. We also use variable-
length codes to describe other results for uniformity.

###### Definition 1

An $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code is a pair
$(f,\varphi)$ of functions $f:\mathcal{X}^{*}\to\\{0,1\\}^{*}$ and
$\varphi:\\{0,1\\}^{*}\to\hat{\mathcal{X}}^{*}$ satisfying
$|\varphi(f(\boldsymbol{x}))|=|\boldsymbol{x}|$ for all
$\boldsymbol{x}\in\mathcal{X}^{*}$.

###### Definition 2

An $(\mathcal{X},\mathcal{X})$-variable-length code is referred to as an
$\mathcal{X}$-lossless code if $\varphi(f(\boldsymbol{x}))=\boldsymbol{x}$ for
all $\boldsymbol{x}\in\mathcal{X}^{*}$.

In the $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f,\varphi)$,
$f$ describes how an encoder maps the sequence $\boldsymbol{x}$ of source
symbols to the bit string $f(\boldsymbol{x})$, and $\varphi$ describes how a
decoder maps the bit string $f(\boldsymbol{x})$ to the sequence
$\varphi(f(\boldsymbol{x}))$ of reproduced symbols. A key requirement is that
the reproduced sequence $\varphi(f(\boldsymbol{x}))$ has the same length as
the original sequence $\boldsymbol{x}$ of source symbols.

Classifier
$c$$\tilde{f}$$\tilde{\varphi}$Multiplexer$f_{1}$$\varphi_{1}$$f_{2}$$\varphi_{2}$$x_{(n]}$$u_{(n]}$$x_{J(1)}$$x_{J(2)}$$\tilde{\boldsymbol{b}}$$\boldsymbol{b}_{1}$$\boldsymbol{b}_{2}$$u_{(n]}$$\hat{x}_{J(1)}$$\hat{x}_{J(2)}$$\hat{x}_{(n]}$

Class labelSymbol in Class $1$Symbol in Class $2$Bits

Figure 2: An example of CTC coding.

CTC codes are variable-length codes that accomplish CTC coding. Before
defining CTC codes formally, let us consider an example of CTC coding. Let $L$
be a positive integer, $\mathcal{U}=(L]$, and $c:\mathcal{X}\to\mathcal{U}$ be
a classifier that assigns the label $c(x)$ to each $x\in\mathcal{X}$. Define
$u_{i}=c(x_{i})$ for $i\in(n]$ and $J(u)=\\{i\in(n]|u_{i}=u\\}$ for
$u\in\mathcal{U}$. An encoder encodes $u_{(n]}$ as a bit string
$\tilde{\boldsymbol{b}}=\tilde{f}(u_{(n]})$ using a $\mathcal{U}$-lossless
code $(\tilde{f},\tilde{\varphi})$. The encoder also encodes the sequence
$x_{J(u)}$ of the symbols in Class $u$ as a bit string
$\boldsymbol{b}_{u}=f_{u}(x_{J(u)})$ using an
$(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f_{u},\varphi_{u})$.
The encoder then outputs the concatenated bit string
$\tilde{\boldsymbol{b}}\boldsymbol{b}_{1}\boldsymbol{b}_{2}\cdots\boldsymbol{b}_{L}$.
A decoder recovers $\tilde{\boldsymbol{b}}$, $\boldsymbol{b}_{1}$,
$\boldsymbol{b}_{2}$, $\cdots$, $\boldsymbol{b}_{L}$ from the concatenated bit
string, reproduces $u_{(n]}$ as $\tilde{\varphi}(\tilde{\boldsymbol{b}})$, and
reproduces $x_{J(u)}$ as $\varphi_{u}(\boldsymbol{b}_{u})$ for all
$u\in\mathcal{U}$. Because $(\tilde{f},\tilde{\varphi})$ is lossless,
$\tilde{\varphi}(\tilde{\boldsymbol{b}})$ equals $u_{(n]}$. The decoder
replaces the $u$’s in $u_{(n]}$ with $\varphi_{u}(\boldsymbol{b}_{u})$ for all
$u\in\mathcal{U}$ to get $\\{\hat{x}_{i}\\}_{i=1}^{n}$ as the reproduced
$x_{(n]}$. The process for $L=2$ is shown in Figure 2. We can see
$\hat{x}_{J(u)}=\varphi_{u}(f_{u}(x_{J(u)}))$ for $u\in\mathcal{U}$.

$\tilde{\boldsymbol{b}}_{1}$$\boldsymbol{b}_{1}$$\tilde{\boldsymbol{b}}_{2}$$\boldsymbol{b}_{2}$$\tilde{\boldsymbol{b}}_{3}$$\boldsymbol{b}_{3}$
Figure 3: The transmitted bit string in another implementation of CTC coding
with $\mathcal{U}=(3]$.

CTC coding can be implemented in ways different from that shown in Figure 2.
For example, we can insert a bit string $\tilde{\boldsymbol{b}}_{u}$ before
$\boldsymbol{b}_{u}$ to indicate which symbols in $x_{(n]}$ are in Class $u$,
as shown in Figure 3. Then the bit string $\tilde{\boldsymbol{b}}$
representing labels can be omitted. It is not difficult to think of other
implementations of CTC coding. CTC coding has the following characteristics no
matter how it is implemented:

  1. 1.

The sequence $u_{(n]}$ of labels can be correctly recovered from the
transmitted bit string; and

  2. 2.

The classes are compressed separately, that is,
$\hat{x}_{J(u)}=\varphi_{u}(f_{u}(x_{J(u)}))$ for all $x_{(n]}$ and $u$.

We use these characteristics to define CTC codes. In general, the label set
$\mathcal{U}$ need not be $(L]$, and can be an arbitrary finite set.

###### Definition 3

An $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f,\varphi)$ is
referred to as an $(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC code if
there exist functions $\psi:\\{0,1\\}^{*}\to\mathcal{U}^{*}$ and
$g:\mathcal{X}^{*}\times\mathcal{U}\to\hat{\mathcal{X}}^{*}$ such that

  1. 1.

$\psi(f(x_{(n]}))=\\{c(x_{i})\\}_{i=1}^{n}$ for all $n\in[\infty)$ and
$\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$; and

  2. 2.

If $n\in[\infty)$ and
$\\{\hat{x}_{i}\\}_{i=1}^{n}=\varphi(f(\\{x_{i}\\}_{i=1}^{n}))$, then
$\hat{x}_{J(u)}=g(x_{J(u)},u)$ for all $u\in\mathcal{U}$, where
$J(u)=\\{i\in(n]|c(x_{i})=u\\}$.

For $u\in\mathcal{U}$, $g(\cdot,u)$ describes how the symbols in Class $u$ are
encoded and decoded, like $\varphi_{u}(f_{u}(\cdot))$ in Figure 2.

The CTC code illustrated in Figure 2 can be viewed as the combination of two
codes: One compresses the labels losslessly, and the other compresses the
source symbols based on their labels. We refer to the latter code as a label-
based code.

###### Definition 4

An $(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based code is a pair
$(f,\varphi)$ of functions
$f:\mathcal{X}^{*}\times\mathcal{U}^{*}\to\\{0,1\\}^{*}$ and
$\varphi:\\{0,1\\}^{*}\times\mathcal{U}^{*}\to\hat{\mathcal{X}}^{*}$
satisfying $|\varphi(f(\boldsymbol{x},\boldsymbol{u}),\boldsymbol{u})|=n$ for
all $n\in[\infty)$, $\boldsymbol{x}\in\mathcal{X}^{n}$, and
$\boldsymbol{u}\in\mathcal{U}^{n}$.

In Definition 4, we require the original sequence $\boldsymbol{x}$, the
reproduced sequence
$\varphi(f(\boldsymbol{x},\boldsymbol{u}),\boldsymbol{u})$, and the label
sequence $\boldsymbol{u}$ to have the same length, because every source symbol
has a label.

###  II-C RD Functions

Let $(S,X)$ be a random pair such that $(S,X)$, $(S_{1},X_{1})$,
$(S_{2},X_{2})$, $\cdots$ are identically distributed. Define
$\bar{\Lambda}=\\{\lambda\in\Lambda|\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]>0\\}$.
For an arbitrary family $\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of distortion
levels, let

$\displaystyle R^{*}(D)=\inf_{\hat{X}\in\Xi(D)}I(X;\hat{X}),$ (4)
$\displaystyle R^{\mathrm{C}}(D)=\inf_{\hat{X}\in\Xi(D)}I(X;\hat{X},c(X)),$
(5)

and

$R^{\mathrm{G}}(D)=\inf_{\hat{X}\in\Xi(D)}I(X;\hat{X}|c(X)),$ (6)

where $\Xi(D)$ is the set of random variables $\hat{X}$ satisfying
$S\leftrightarrow X\leftrightarrow\hat{X}$ and
$E[d_{\lambda}(X,\hat{X})|S\in\mathcal{S}_{\lambda}]\leq D(\lambda)$ for all
$\lambda\in\bar{\Lambda}$. Equation (4) defines the RD function $R^{*}$ of
$(S,X)$ for $\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$.
Equation (5) defines the RD function $R^{\mathrm{C}}$ of $(S,X)$ for
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ and
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC codes. Equation (6)
defines the RD function $R^{\mathrm{G}}$ of $(S,X)$ for
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ given $c(X)$.
In the next section, we will see that $R^{*}$, $R^{\mathrm{C}}$, and
$R^{\mathrm{G}}$ characterize the optimal performance of
$(\mathcal{X},\hat{\mathcal{X}})$-variable-length codes,
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC codes, and
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based codes, respectively.

##  III Main Results

###  III-A Coding Theorems

Fix $R\in[0,\infty)$ and a family $\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of
distortion levels. An $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code
is said to achieve $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ if

$\lim_{n\to\infty}\mathrm{Pr}[(S_{(n]},X_{(n]})\in F_{\epsilon}]=1$ (7)

for all $\epsilon\in(0,\infty)$, where $F_{\epsilon}$ is the set of
$(\boldsymbol{s},\boldsymbol{x})\in\mathcal{S}^{*}\times\mathcal{X}^{*}$ such
that $|f(\boldsymbol{x})|\leq|\boldsymbol{x}|R$ and such that
$\boldsymbol{s}$, $\boldsymbol{x}$, and $\varphi(f(\boldsymbol{x}))$ meet the
fidelity criterion $(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$
for all $\lambda\in\Lambda$. Define $U_{i}=c(X_{i})$ for $i\in[1:\infty)$. An
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based code is said to
achieve $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ given $c(X)$
if

$\lim_{n\to\infty}\mathrm{Pr}[(S_{(n]},X_{(n]},U_{(n]})\in G_{\epsilon}]=1$
(8)

for all $\epsilon\in(0,\infty)$, where $G_{\epsilon}$ is the set of
$(\boldsymbol{s},\boldsymbol{x},\boldsymbol{u})\in\mathcal{S}^{*}\times\mathcal{X}^{*}\times\mathcal{U}^{*}$
such that $|f(\boldsymbol{x},\boldsymbol{u})|\leq|\boldsymbol{x}|R$ and such
that $\boldsymbol{s}$, $\boldsymbol{x}$, and
$\varphi(f(\boldsymbol{x},\boldsymbol{u}),\boldsymbol{u})$ meet the fidelity
criterion $(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$ for all
$\lambda\in\Lambda$.

The following coding theorems are valid when $\mathcal{X}$ and
$\hat{\mathcal{X}}$ are finite. They may be generalized to abstract sources,
but with some additional technical conditions [3, 43].

###### Theorem 1

If $R>R^{*}(D)$, then there exists an
$(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f,\varphi)$ achieving
$(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$, and
satisfying

$\limsup_{n\to\infty}\frac{1}{n}\max_{\boldsymbol{x}\in\mathcal{X}^{n}}|f(\boldsymbol{x})|<R.$
(9)

Conversely, if an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code
$(f,\varphi)$ achieves $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$, then $R\geq
R^{*}(D)$.

###### Theorem 2

If $R>R^{\mathrm{C}}(D)$, then there exists an
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC code achieving111This
means that (7) holds for all $\epsilon\in(0,\infty)$, because any CTC code is
a variable-length code. $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$. Conversely,
if an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f,\varphi)$
achieves $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$, $\psi$ is a
function from $\\{0,1\\}^{*}$ to $\mathcal{U}^{*}$, and
$\psi(f(X_{(n]}))=U_{(n]}$ with probability one for all $n\in[\infty)$, then
$R\geq R^{\mathrm{C}}(D)$.

###### Theorem 3

If $R>R^{\mathrm{G}}(D)$, then there exist an
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based code $(f,\varphi)$
and a function $g:\mathcal{X}^{*}\times\mathcal{U}\to\hat{\mathcal{X}}^{*}$
such that

  1. 1.

$(f,\varphi)$ achieves $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ given $c(X)$;
and

  2. 2.

If $n\in[\infty)$ and

$\\{\hat{x}_{i}\\}_{i=1}^{n}=\varphi(f(\\{x_{i}\\}_{i=1}^{n},\\{u_{i}\\}_{i=1}^{n}),\\{u_{i}\\}_{i=1}^{n}),$
(10)

then $\hat{x}_{J(u)}=g(x_{J(u)},u)$ for all $u\in\mathcal{U}$, where
$J(u)=\\{i\in(n]|u_{i}=u\\}$.

Conversely, if there exists an
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based code $(f,\varphi)$
achieving $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ given $c(X)$,
then $R\geq R^{\mathrm{G}}(D)$.

The theorems say that $(\mathcal{X},\hat{\mathcal{X}})$-variable-length codes,
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC codes, and
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based codes need rates no
less than $R^{*}(D)$, $R^{\mathrm{C}}(D)$, and $R^{\mathrm{G}}(D)$,
respectively, for the fidelity criteria
$\\{(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda))\\}_{\lambda\in\Lambda}$.
The converse part of Theorem 2 does not need the condition that $(f,\varphi)$
is an $(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC code. It only needs
the condition that class labels $U_{(n]}$ can be correctly recovered from the
transmitted bit string $f(X_{(n]})$, i.e. the first characteristic of CTC
codes (see the paragraph preceding Definition 3). Hence, an
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC code cannot perform better
even if it is allowed to compress symbols in different classes jointly. In
other words, the performance loss of CTC coding relative to RD-optimal coding
is not due to separate compression of source symbols in different classes. The
performance loss is because class labels have to be reproduced in CTC coding.
The existence of the function $g$ in the direct part of Theorem 3 means that
$(f,\varphi)$ compresses symbols in different classes separately. Hence,
separate compression does not cause performance loss for label-based codes
either.

###  III-B Properties of RD Functions

For an arbitrary random variable $\hat{X}$, we have

$\displaystyle I(X;\hat{X}|c(X))+I(c(X);\hat{X})=I(X;\hat{X}),$ (11)
$\displaystyle I(X;\hat{X})+H(c(X)|\hat{X})=I(X;\hat{X},c(X)),$ (12)

and

$I(X;\hat{X}|c(X))+H(c(X))=I(X;\hat{X},c(X)),$ (13)

leading to the following corollary.

###### Corollary 1

For every family $\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of distortion levels,
$R^{\mathrm{G}}(D)\leq R^{*}(D)\leq
R^{\mathrm{C}}(D)=R^{\mathrm{G}}(D)+H(c(X))$.

The identity $R^{\mathrm{C}}(D)=R^{\mathrm{G}}(D)+H(c(X))$ has a
straightforward interpretation that CTC codes need to compress labels in
addition to source symbols.

###### Corollary 2

Define distortion measures $\\{\hat{d}_{\lambda}\\}_{\lambda\in\bar{\Lambda}}$
on $\mathcal{X}\times\hat{\mathcal{X}}$ by

$\hat{d}_{\lambda}(x,\hat{x})=\frac{\mathrm{Pr}[S\in\mathcal{S}_{\lambda}|X=x]}{\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]}d_{\lambda}(x,\hat{x}).$
(14)

Then for every $\\{D(\lambda)\\}_{\lambda\in\Lambda}$,

$R^{*}(D)=\inf_{\hat{X}\in\hat{\Xi}(D)}I(X;\hat{X}),$ (15)

where $\hat{\Xi}(D)$ is the set of random variables $\hat{X}$ satisfying
$E[\hat{d}_{\lambda}(X,\hat{X})]\leq D(\lambda)$ for all
$\lambda\in\bar{\Lambda}$.

We can prove Corollary 2 by noting that

$E[\hat{d}_{\lambda}(X,\hat{X})]=E[d_{\lambda}(X,\hat{X})|S\in\mathcal{S}_{\lambda}]$
(16)

for all $\lambda\in\bar{\Lambda}$ and random variables $\hat{X}$ satisfying
$S\leftrightarrow X\leftrightarrow\hat{X}$. Note that the right-hand side of
(15) is the classical RD function of $X$ for the distortion measures
$\\{\hat{d}_{\lambda}\\}_{\lambda\in\bar{\Lambda}}$. By the monotonicity and
convexity of the right-hand side of (15) with respect to
$\\{D(\lambda)\\}_{\lambda\in\Lambda}$, $R^{*}$ is non-increasing and convex.
If $\mathcal{X}$ and $\hat{\mathcal{X}}$ are finite, we can compute $R^{*}$
numerically using the Blahut-Arimoto algorithm [44, 45].

We can use the total expectation formula to prove the following corollary.

###### Corollary 3

Let $\Lambda=\mathcal{S}$, $d$ be a distortion measure on
$\mathcal{X}\times\hat{\mathcal{X}}$, and $R^{\mathrm{O}}$ be the classical RD
function of $X$ for $d$. Suppose $d_{\lambda}=d$ and
$\mathcal{S}_{\lambda}=\\{\lambda\\}$ for all $\lambda\in\Lambda$. Then for
every $\delta\in[0,\infty)$ we have

$R^{\mathrm{O}}(\delta)=\inf_{D\in A(\delta)}R^{*}(D),$ (17)

where $A(\delta)$ is the set of $\\{D(\lambda)\\}_{\lambda\in\Lambda}$
satisfying

$\sum_{s\in\mathcal{S}}\mathrm{Pr}[S=s]D(s)\leq\delta.$ (18)

Figure 4: The relation between $R^{\mathrm{O}}$ and $R^{*}$ in Example 1. Each
curve shows the relation between $D(0)$ and $R^{*}(D)$ under the constraint
$\mathrm{Pr}[S=0]D(0)+\mathrm{Pr}[S=1]D(1)=\delta$.

###### Example 1

Let $\mathcal{S}=\mathcal{X}=\hat{\mathcal{X}}=\Lambda=\\{0,1\\}$,

$\begin{bmatrix}\mathrm{Pr}[S=0,X=0]&\mathrm{Pr}[S=0,X=1]\\\
\mathrm{Pr}[S=1,X=0]&\mathrm{Pr}[S=1,X=1]\end{bmatrix}\\!=\\!\begin{bmatrix}0.1&0.4\\\
0.3&0.2\end{bmatrix}\\!,$ (19)

$\mathcal{S}_{0}=\\{0\\}$, $\mathcal{S}_{1}=\\{1\\}$, and $d_{0}=d_{1}=d$,
where $d$ is the Hamming distortion measure on
$\mathcal{X}\times\hat{\mathcal{X}}$ defined by

$d(x,\hat{x})=\begin{cases}0,&x=\hat{x},\\\ 1,&x\not=\hat{x}.\end{cases}$ (20)

Figure 4 shows the relation between $R^{\mathrm{O}}$ in Corollary 3 and
$R^{*}$. We can see

  1. 1.

Subject to

$\mathrm{Pr}[S=0]D(0)+\mathrm{Pr}[S=1]D(1)=0.25,$ (21)

$R^{*}(D)$ is minimized when $D(0)$ is approximately $0.2$;

  2. 2.

The minimum $R^{*}(D)$ subject to (21) equals $R^{\mathrm{O}}(0.25)$; and

  3. 3.

$R^{*}(D)>R^{\mathrm{O}}(0.25)$ when (21) and $D(0)=0.25$ hold, i.e. when
$D(0)=D(1)=0.25$.

Analogous facts can be seen for $\delta=0.1$ and for $\delta=0.4$. The second
observation confirms Corollary 3. The third observation is more interesting.
If $D(0)=D(1)=0.25$, then $R^{*}(D)$ is the minimum rate we need to ensure
that the distortion level of each subsource does not exceed $0.25$. We need
the rate $R^{\mathrm{O}}(0.25)$ to ensure that the average distortion of all
symbols output by the composite source does not exceed $0.25$. It is not
difficult to understand the fact $R^{*}(D)>R^{\mathrm{O}}(0.25)$: If the
distortion level of each subsource does not exceed $0.25$, then the average
distortion does not exceed $0.25$, but not vice versa. Hence, fidelity
criteria on individual subsources can be stricter than the classical fidelity
criteria that the average distortion of all symbols does not exceed a certain
distortion level.

###### Corollary 4

Let $\tilde{\Lambda}=\Lambda\cup\\{\tilde{\lambda}\\}$, where
$\tilde{\lambda}\not\in\Lambda$. Define distortion measures
$\\{\tilde{d}_{\lambda}\\}_{\lambda\in\tilde{\Lambda}}$ on
$\mathcal{X}\times(\hat{\mathcal{X}}\times\mathcal{U})$ by

$\tilde{d}_{\lambda}(x,(\hat{x},u))=\begin{cases}d_{\lambda}(x,\hat{x}),&\lambda\in\Lambda,\\\
0,&\lambda=\tilde{\lambda},c(x)=u,\\\
1,&\lambda=\tilde{\lambda},c(x)\not=u.\end{cases}$ (22)

Let $\tilde{\mathcal{S}}_{\tilde{\lambda}}=\mathcal{S}$ and
$\tilde{\mathcal{S}}_{\lambda}=\mathcal{S}_{\lambda}$ for all
$\lambda\in\Lambda$. Then for every $\\{D(\lambda)\\}_{\lambda\in\Lambda}$, we
have $R^{\mathrm{C}}(D)=\tilde{R}(\tilde{D})$, where $\tilde{R}$ is the RD
function of $(S,X)$ for
$\\{(\tilde{d}_{\lambda},\tilde{\mathcal{S}}_{\lambda})\\}_{\lambda\in\tilde{\Lambda}}$,
$\tilde{D}(\tilde{\lambda})=0$, and $\tilde{D}(\lambda)=D(\lambda)$ for all
$\lambda\in\Lambda$.

We can prove Corollary 4 by noting that

$E[\tilde{d}_{\tilde{\lambda}}(X,(\hat{X},U))|S\in\tilde{\mathcal{S}}_{\tilde{\lambda}}]\leq\tilde{D}(\tilde{\lambda})$
(23)

is equivalent to $\mathrm{Pr}[c(X)=U]=1$. By Corollaries 1, 2, and 4, $R^{*}$,
$R^{\mathrm{C}}$, and $R^{\mathrm{G}}$ have properties similar to those of
classical RD functions, as shown in the following corollary.

###### Corollary 5

The RD functions $R^{*}$, $R^{\mathrm{C}}$, and $R^{\mathrm{G}}$ are non-
increasing and convex.

The following theorem can be viewed as a generalization of a property of the
conditional RD function [9, 10].

###### Theorem 4

Define $\bar{\mathcal{U}}=\\{u\in\mathcal{U}|\mathrm{Pr}[c(X)=u]>0\\}$. For
$u\in\bar{\mathcal{U}}$, let $P_{u}$ be the conditional distribution of
$(S,X)$ given $c(X)=u$, and $R_{u}^{*}$ be the RD function defined in Section
II-C of a $P_{u}$-distributed random pair for
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$. Then for
every $\\{D(\lambda)\\}_{\lambda\in\Lambda}$,

$R^{\mathrm{G}}(D)=\inf_{\delta\in\Delta(D)}\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u]R_{u}^{*}(\delta(\cdot,u)),$
(24)

where $\Delta(D)$ is the set of functions
$\delta:\Lambda\times\mathcal{U}\to[0,\infty)$ satisfying

$\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[S\in\mathcal{S}_{\lambda},c(X)=u]\delta(\lambda,u)\leq\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]D(\lambda)$
(25)

for all $\lambda\in\Lambda$.

If $\mathcal{S}_{\lambda}=\mathcal{S}$ for all $\lambda\in\Lambda$, then
$R^{\mathrm{G}}$ is a conditional RD function and each $R_{u}^{*}$ in Theorem
4 is a classical RD function. Hence, (24) is a generalization of (2.2) in [10]
for subsource-dependent fidelity criteria. Theorem 4 also provides an approach
to numerical computation of $R^{\mathrm{G}}$, because we can compute
$R_{u}^{*}$ using the Blahut-Arimoto algorithm, as pointed out in the
discussions following Corollary 2.

###  III-C CTC Code Where Labels are Compressed by a Variable-Length Code

We have seen in Section II-B that CTC codes can have different
implementations. Our proofs outlined in Section IV-B of Theorems 2 and 3 show
that CTC codes implemented as in Figure 2 can have the performance
characterized by $R^{\mathrm{C}}$. The implementation shown in Figure 2, i.e.
the implementation where labels are compressed by a variable-length code, is
hence justified. Now we illustrate this by showing the relevant steps of the
proofs.

Define $\bar{\mathcal{U}}$ and $\\{P_{u}\\}_{u\in\bar{\mathcal{U}}}$ as in
Theorem 4. For $u\in\bar{\mathcal{U}}$, let an
$(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f_{u},\varphi_{u})$
achieves $(R_{u},\delta(\cdot,u))$ for a $P_{u}$-distributed random pair and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$. Here
$\delta(\cdot,u)$ denotes distortion levels
$\\{\delta(\lambda,u)\\}_{\lambda\in\Lambda}$. Then we can combine the codes
$\\{(f_{u},\varphi_{u})\\}_{u\in\bar{\mathcal{U}}}$ and a variable-length code
that losslessly compresses class labels in the way shown in Figure 2 to get an
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC code $(f,\varphi)$. By
Lemmas 2, 3, and 4 stated in Section IV-B, the rate of $(f,\varphi)$ is
approximately

$H(c(X))+\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u]R_{u},$ (26)

and for $\lambda\in\bar{\Lambda}$, the distortion level of $(f,\varphi)$
corresponding to $d_{\lambda}$ and $\mathcal{S}_{\lambda}$ is approximately

$\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u|S\in\mathcal{S}_{\lambda}]\delta(\lambda,u).$
(27)

For a family $\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of distortion levels, we
should choose such $\delta$ and $\\{R_{u}\\}_{u\in\bar{\mathcal{U}}}$ that the
approximate distortion level (27) does not exceed $D(\lambda)$ for any
$\lambda$ and that $R_{u}=R_{u}^{*}(\delta(\cdot,u))$ for all
$u\in\bar{\mathcal{U}}$. By $R^{\mathrm{C}}(D)=R^{\mathrm{G}}(D)+H(c(X))$ and
Theorem 4, the minimum rate (26) for $\delta$ so chosen is
$R^{\mathrm{C}}(D)$. Hence CTC codes where labels are compressed by a
variable-length code can have the performance characterized by
$R^{\mathrm{C}}$. The performance of other implementations of CTC codes is
left for future research.

###  III-D A Case with Perfect Classification

Figure 5: The RD function $R^{*}$ in Example 2. Figure 6: The gap
$R^{\mathrm{C}}-R^{*}$ in Example 2.

In this section, we study a case where the classification is perfect in that
$S\in\mathcal{S}_{\lambda}$ is equivalent to $c(X)=\lambda$ with probability
one for all $\lambda\in\Lambda$. Of course, this is possible only if all
$\lambda\in\Lambda$ satisfying $\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]>0$ are
chosen as labels. Insights into connections between CTC codes and general
variable-length codes will be gained in the following theorem and example.

###### Theorem 5

For $\lambda\in\bar{\Lambda}$, let $Q_{\lambda}$ be the distribution of $X$
given the condition $S\in\mathcal{S}_{\lambda}$ and $R^{(\lambda)}$ be the RD
function of a $Q_{\lambda}$-distributed random variable for $d_{\lambda}$. Fix
a family $\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of distortion levels. If
$S\in\mathcal{S}_{\lambda}$ is equivalent to $c(X)=\lambda$ with probability
one for all $\lambda\in\Lambda$, then

$R^{\mathrm{G}}(D)=\sum_{\lambda\in\bar{\Lambda}}\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]R^{(\lambda)}(D(\lambda)).$
(28)

If we have $|\bar{\Lambda}|=1$ in addition, then $R^{\mathrm{G}}(D)=R^{*}(D)$.

The meaning of (28) is as follows. For $\lambda\in\bar{\Lambda}$, the symbols
from the subsources in $\mathcal{S}_{\lambda}$ account for approximately
$\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]$ of all the source symbols, and
consequently we need a rate of
$\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]R^{(\lambda)}(D(\lambda))$ to describe
them.

###### Example 2

Let $\mathcal{S}=\mathcal{X}=\hat{\mathcal{X}}=\\{0,1,2,3\\}$, $S$ be
uniformly distributed over $\mathcal{S}$, $S=X$ with probability one,
$\Lambda=\mathcal{U}=\\{0,1\\}$, $\mathcal{S}_{0}=\\{0,1\\}$,
$\mathcal{S}_{1}=\\{2,3\\}$, $c(0)=c(1)=0$, $c(2)=c(3)=1$, and

$d_{0}(x,\hat{x})=d_{1}(x,\hat{x})=\begin{cases}0,&x=\hat{x},\\\
1,&x\not=\hat{x},\\\ \end{cases}$ (29)

for all $x\in\mathcal{X}$ and $\hat{x}\in\hat{\mathcal{X}}$. The RD function
$R^{*}$ and the gap $R^{\mathrm{C}}-R^{*}$ are shown in Figures 5 and 6,
respectively.

From (11), (12), and Example 2 we can see
$R^{\mathrm{G}}(D)<R^{*}(D)<R^{\mathrm{C}}(D)$ unless certain conditions are
satisfied. This is true even if the classification is perfect. The strict
inequality $R^{\mathrm{G}}(D)<R^{*}(D)$ can be understood by observing that
the encoder not only needs to describe source symbols in each class to the
decoder, but also needs to inform the decoder the labels of the symbols. On
the other hand, $R^{*}(D)<R^{\mathrm{C}}(D)=R^{\mathrm{G}}(D)+H(c(X))$ show
that compressing the labels using a lossless code with the rate $H(c(X))$ is
usually a suboptimal way to do this. In the extreme case of
$|\bar{\Lambda}|=1$, $R^{*}(D)$ even equals $R^{\mathrm{G}}(D)$. The
differences between the reproduced symbols from different classes may be
utilized to reduce the additional rate required by label compression. In
conclusion, CTC coding can be suboptimal even if the classification is
perfect.

###  III-E Comparison of RD Functions

In this section, we will show that the performance loss
$R^{\mathrm{C}}(D)-R^{*}(D)$ is small under mild conditions. Equation (12)
leads to the following corollary.

###### Corollary 6

Fix $\mu\in\Lambda$ and a family $\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of
distortion levels. Let $D(\mu)>0$. For $\delta\in[0,\infty)$ and
$\lambda\in\Lambda$, let

$D_{\delta}(\lambda)=\begin{cases}\delta,&\lambda=\mu,\\\
D(\lambda),&\lambda\not=\mu.\end{cases}$ (30)

If there exists a family $\\{\hat{X}_{\delta}\\}_{\delta\in(0,D(\mu))}$ of
random variables such that

  1. 1.

$\hat{X}_{\delta}\in\Xi(D_{\delta})$ for all $\delta\in(0,D(\mu))$; and

  2. 2.

$I(X;\hat{X}_{\delta})-R^{*}(D_{\delta})$ and $H(c(X)|\hat{X}_{\delta})$ tend
to 0 as $(0,D(\mu))\owns\delta\to 0$;

then $R^{\mathrm{C}}(D_{\delta})-R^{*}(D_{\delta})\to 0$ as
$(0,D(\mu))\owns\delta\to 0$.

As $\delta\to 0$, $D_{\delta}(\mu)$ tends to zero while the other distortion
levels in $\\{D_{\delta}(\lambda)\\}_{\lambda\in\Lambda}$ remain fixed. Hence
under the conditions in Corollary 6, the performance loss
$R^{\mathrm{C}}-R^{*}$ is negligible for asymptotically small distortion.

The cases where the conditions in Corollary 6 are satisfied are not rare. For
example, we can let $\mathcal{X}=\hat{\mathcal{X}}$ and let $d_{\mu}$ be a
distortion measure that characterizes the closeness or similarity between
source symbols and their reproductions, such as the Hamming distortion measure
or the squared-error distortion measure. For such a $d_{\mu}$ and some common
classifier $c$, a sufficiently small $d_{\mu}(x,\hat{x})$ means that $x$ and
$\hat{x}$ tend to have the same label. For $\delta\in(0,D(\mu))$, we let
$\hat{X}_{\delta}$ be a random variable in $\Xi(D_{\delta})$ satisfying
$I(X;\hat{X}_{\delta})<R^{*}(D_{\delta})+\delta$. Further assume that the
support set of $X$ equals the conditional support set of $X$ given
$S\in\mathcal{S}_{\mu}$. Then for sufficiently small $\delta$,
$E[d_{\mu}(X,\hat{X}_{\delta})]$ is small, and consequently
$c(X)=c(\hat{X}_{\delta})$ with a high probability. Hence for sufficiently
small $\delta$, $H(c(X)|\hat{X}_{\delta})$ is small, and by Corollary 6, we
can expect $R^{\mathrm{C}}(D_{\delta})-R^{*}(D_{\delta})$ to be small.

If $D(\lambda)$ is sufficiently large for all $\lambda\in\Lambda$, then
$R^{\mathrm{G}}(D)=R^{*}(D)=0$. Therefore, $R^{*}(D)$ can be close to
$R^{\mathrm{G}}(D)$ for $D$ having large values and can be close to
$R^{\mathrm{C}}(D)$ for $D$ having small values. Or equivalently, the
performance loss $R^{\mathrm{C}}(D)-R^{*}(D)$ of optimal CTC codes is close to
$0$ for $D$ having small values and is close to $H(c(X))$ for $D$ having large
values. This can be understood by observing that lossless compression of
labels needs a rate of $H(c(X))$, and that CTC codes need to compress the
labels losslessly even if $D(\lambda)$ is large. For $D$ having medium values,
we have $0<R^{\mathrm{C}}(D)-R^{*}(D)<H(c(X))$ by the continuity of $R^{*}$
and $R^{\mathrm{C}}$, which follows from Corollary 5. The performance loss
$R^{\mathrm{C}}(D)-R^{*}(D)$ is small if the number $|\mathcal{U}|$ of classes
is small.

###### Example 3

Let $S$ be uniformly distributed over $\mathcal{S}=\\{0,1\\}$,
$\mathcal{X}=\hat{\mathcal{X}}=\\{n/256+1/512|n\in[256)\\}$,
$\Lambda=\mathcal{U}=\\{0,1\\}$, $\mathcal{S}_{0}=\\{0\\}$,
$\mathcal{S}_{1}=\\{1\\}$, and
$d_{0}(x,\hat{x})=d_{1}(x,\hat{x})=(x-\hat{x})^{2}$ for all $x\in\mathcal{X}$
and $\hat{x}\in\hat{\mathcal{X}}$. Define an 8-bit quantizer
$Q:\mathbb{R}\to\mathcal{X}$ by

$Q(y)=\begin{cases}1/512,&y<1/256,\\\ \dfrac{\lfloor
256y\rfloor}{256}+\dfrac{1}{512},&\dfrac{1}{256}\leq y<\dfrac{255}{256},\\\
511/512,&255/256\leq y.\end{cases}$ (31)

Let a random variable $Y$ have the conditional distribution
$\mathcal{N}(0.3,0.04)$ given $S=0$, and have the conditional distribution
$\mathcal{N}(0.7,0.04)$ given $S=1$. Suppose $X=Q(Y)$ with probability one. A
reasonable classifier $c$ assigns label $0$ to every $x<1/2$, and assigns
label $1$ to every $x\geq 1/2$. The RD function $R^{*}$ is shown in Figure 7.
Figure 8 shows the gap between $R^{*}$ and $R^{\mathrm{C}}$. The performance
loss $R^{\mathrm{C}}(D)-R^{*}(D)$ is close to $1=H(c(X))$ when $D(0)$ and
$D(1)$ are sufficiently large and is close to 0 when $D(0)$ or $D(1)$ are
close to 0. This confirms Corollary 6 and the discussions following it.

Figure 7: The RD function $R^{*}$ in Example 3. Figure 8: The gap
$R^{\mathrm{C}}-R^{*}$ in Example 3.

##  IV Proof Sketches of Coding Theorems

###  IV-A Theorem 1

A key step in the proof is to define functions
$\\{d_{\lambda,\delta}\\}_{\lambda\in\Lambda,\delta\in\mathbb{R}}$ from
$\mathcal{X}\times\hat{\mathcal{X}}\times\mathcal{S}$ to $\mathbb{R}$ by

$d_{\lambda,\delta}(x,\hat{x},s)=\begin{cases}d_{\lambda}(x,\hat{x}),&s\in\mathcal{S}_{\lambda},\\\
\delta,&s\not\in\mathcal{S}_{\lambda}.\end{cases}$ (32)

For $\lambda\in\Lambda$ and $\delta\in[0,\infty)$, $d_{\lambda,\delta}$ can be
interpreted as a distortion measure on $\mathcal{X}\times\hat{\mathcal{X}}$
dependent on $s$. For $\lambda\in\Lambda$, $\delta\in[0,\infty)$,
$n\in[1:\infty)$, $\\{s_{i}\\}_{i=1}^{n}\in\mathcal{S}^{n}$,
$\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$, and
$\\{\hat{x}_{i}\\}_{i=1}^{n}\in\hat{\mathcal{X}}^{n}$, we can verify that

$\frac{1}{n}\sum_{i=1}^{n}d_{\lambda,\delta}(x_{i},\hat{x}_{i},s_{i})\leq\delta$
(33)

is a sufficient and necessary condition for $s_{(n]}$, $x_{(n]}$, and
$\hat{x}_{(n]}$ to meet the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},\delta)$. The inequality (33) means that
the average of all $d_{\lambda}(x_{i},\hat{x}_{i})$ satisfying
$s_{i}\in\mathcal{S}_{\lambda}$ does not exceed $\delta$, because
$d_{\lambda,\delta}(x_{i},\hat{x}_{i},s_{i})=\delta$ whenever
$s_{i}\not\in\mathcal{S}_{\lambda}$. Thus, the problem is reduced to an RD
problem where the distortion measures are influenced by some side information
unknown to both the encoder and the decoder [13, 14]. In spite of the
difference that the distortion measures depend on the distortion level
$\delta$, Theorem 1 can be proved using existing results [14] and the
following corollary of the definition of $\Xi(D)$.

###### Corollary 7

Define
$d_{\lambda,\delta}:\mathcal{X}\times\hat{\mathcal{X}}\times\mathcal{S}\to\mathbb{R}$
by (32) for $\lambda\in\Lambda$ and $\delta\in\mathbb{R}$. Let
$\\{D(\lambda)\\}_{\lambda\in\Lambda}$ be a family of distortion levels. Then
$\Xi(D)$ equals the set of random variables $\hat{X}$ satisfying
$S\leftrightarrow X\leftrightarrow\hat{X}$ and
$E[d_{\lambda,D(\lambda)}(X,\hat{X},S)]\leq D(\lambda)$ for all
$\lambda\in\Lambda$.

Since the existing results are on block codes, we still need to adapt them for
variable-length codes. From a sequence of block codes, a variable-length code
with almost the same rate can be constructed using the compound representation
of positive integers [46]. The compound representation of $j\in[1:\infty)$ is
the bit string $\gamma(j)$ obtained by

  1. 1.

Writing $j$ in the binary form $1b_{\lfloor\log_{2}(j)\rfloor-1}\cdots
b_{1}b_{0}$;

  2. 2.

Inserting a $1$ after $b_{0}$ and $0$’s after all the other bits in the binary
form; and

  3. 3.

Dropping the leading $1$ to get the bit string $\gamma(j)$.

For example, the binary form of 5 is 101, and so $\gamma(5)=00011$. It is
known [46] that

$|\gamma(j)|=1+2\lfloor\log_{2}(j)\rfloor\leq 1+2\log_{2}(j)$ (34)

for $j\in[1:\infty)$, and that $\gamma$ is prefix-free, that is, $\gamma(i)$
is not a prefix of $\gamma(j)$ for all $i$, $j\in[1:\infty)$ when $i\not=j$.
The following lemma shows properties of so constructed variable-length codes.

###### Lemma 1

For $n\in[1:\infty)$, let $M_{n}\in[1:\infty)$, $f_{n}$ be a function from
$\mathcal{X}^{n}$ to $(M_{n}]$, and $\varphi_{n}$ be a function from $(M_{n}]$
to $\hat{\mathcal{X}}^{n}$. If $R\in\mathbb{R}$ and $M_{n}\leq 2^{nR}$ for all
$n\in[1:\infty)$, then there exists an
$(\mathcal{X},\hat{\mathcal{X}})$-variable-length code $(f,\varphi)$
satisfying

$\limsup_{n\to\infty}\frac{1}{n}\max_{\boldsymbol{x}\in\mathcal{X}^{n}}|f(\boldsymbol{x})|\leq
R$ (35)

and
$\varphi(f(\boldsymbol{x}))=\varphi_{|\boldsymbol{x}|}(f_{|\boldsymbol{x}|}(\boldsymbol{x}))$
for all non-empty strings $\boldsymbol{x}\in\mathcal{X}^{*}$.

The complete proof of Theorem 1 is given in Appendix D.

###  IV-B Theorems 2 and 3

We prove the converse part of Theorem 2 using Theorem 1 and Corollary 4. By
assumption, the labels of the source symbols can be correctly recovered from
the transmitted bit string $f(X_{(n]})$ in the code $(f,\varphi)$. Hence we
can use $(f,\varphi)$ to construct an
$(\mathcal{X},\hat{\mathcal{X}}\times\mathcal{U})$-variable-length code
$(f,\tilde{\varphi})$ that achieves $(R,\tilde{D})$ for $(S,X)$ and
$\\{(\tilde{d}_{\lambda},\tilde{\mathcal{S}}_{\lambda})\\}_{\lambda\in\tilde{\Lambda}}$,
where $\tilde{D}$, $\tilde{d}_{\lambda}$, and $\tilde{\mathcal{S}}_{\lambda}$
are defined in Corollary 4. By Theorem 1 we have $R\geq\tilde{R}(\tilde{D})$,
i.e. $R\geq R^{\mathrm{C}}(D)$.

It is not difficult to prove the direct part of Theorem 3. We have shown in
Section IV-A how the subsource-dependent fidelity criteria can be converted to
fidelity criteria considered in [13] and [14]. The conversion can be used here
to reduce the problem to an RD problem with the side information expressed as
two random variables: $S$ unknown to both the encoder and the decoder, and
$c(X)$ known by both the encoder and the decoder. Then we can use existing
results [9, 14] to show that the lowest achievable rate is
$R^{\mathrm{G}}(D)$.

We will go into more detail about an alternative proof of the direct part of
Theorem 3 that also serves as a foundation of the analysis in Section III-C.
This proof explicitly constructs a variable-length code for each class
$u\in\mathcal{U}$ and then combines the variable-length codes to form the
desired label-based code. The proof uses the following lemmas.

###### Lemma 2

Let $n\in[1:\infty)$, $u\in\mathcal{U}$, $P_{u}$ be the conditional
distribution of $(S,X)$ given $c(X)=u$, and $J$ be the random set
$\\{i\in(n]|c(X_{i})=u\\}$. Define random pairs
$\\{(T_{i},Y_{i})\\}_{i=1}^{\infty}$ such that

  1. 1.

For every $i\in[1:\infty)$, $(T_{i},Y_{i})$ has the distribution $P_{u}$ and
is independent of $c(X_{i})$; and

  2. 2.

$\\{(T_{i},Y_{i},c(X_{i}))\\}_{i=1}^{\infty}$ is an i.i.d. process.

Then $(S_{J},X_{J})$ and $(T_{J},Y_{J})$ are identically distributed.

###### Lemma 3

Let $\\{Y_{i}\\}_{i=1}^{\infty}$ be a sequence of i.i.d. random variables
taking values in a set $\mathcal{Y}$. For $n\in[1:\infty)$, let $J(n)$ be a
random subset of a finite subset of $[1:\infty)$ and let $J(n)$ be independent
of $\\{Y_{i}\\}_{i=1}^{\infty}$. If $\lim_{n\to\infty}\mathrm{Pr}[|J(n)|>k]=1$
for all $k\in[1:\infty)$, $G\subseteq\mathcal{Y}^{*}$, and
$\lim_{k\to\infty}\mathrm{Pr}[Y_{(k]}\in G]=1$, then
$\lim_{n\to\infty}\mathrm{Pr}[Y_{J(n)}\in G]=1$.

###### Lemma 4

Let $d$ be a distortion measure on $\mathcal{X}\times\hat{\mathcal{X}}$,
$\mathcal{S}_{*}$ be a subset of $\mathcal{S}$, $\delta\in[0,\infty)$,
$\\{s_{i}\\}_{i=1}^{n}\in\mathcal{S}^{n}$,
$\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$,
$\\{\hat{x}_{i}\\}_{i=1}^{n}\in\hat{\mathcal{X}}^{n}$,
$J_{*}=\\{i\in(n]|s_{i}\in\mathcal{S}_{*}\\}$, and
$\\{J(u)\\}_{u\in\mathcal{U}}$ be a partition of $(n]$. If $s_{J(u)}$,
$x_{J(u)}$, and $\hat{x}_{J(u)}$ meet the fidelity criterion
$(d,\mathcal{S}_{*},\delta_{u})$ for all $u\in\mathcal{U}$, and
$\sum_{u\in\mathcal{U}}|J(u)\cap J_{*}|\delta_{u}\leq|J_{*}|\delta$, then
$s_{(n]}$, $x_{(n]}$, and $\hat{x}_{(n]}$ meet the fidelity criterion
$(d,\mathcal{S}_{*},\delta)$. If $s_{J(u)}$, $x_{J(u)}$, and $\hat{x}_{J(u)}$
do not meet the fidelity criterion $(d,\mathcal{S}_{*},\delta_{u})$ for any
$u\in\mathcal{U}$, and $\sum_{u\in\mathcal{U}}|J(u)\cap
J_{*}|\delta_{u}\geq|J_{*}|\delta$, then $s_{(n]}$, $x_{(n]}$, and
$\hat{x}_{(n]}$ do not meet the fidelity criterion
$(d,\mathcal{S}_{*},\delta)$.

We omit the proofs of the lemmas because they are straightforward. Lemma 2
characterizes the distributions of the symbols in the classes. Lemma 3 helps
us deal with the nuance that the number of the source symbols in a class is
random. We use Lemma 4 to calculate the distortion levels
$\\{D(\lambda)\\}_{\lambda\in\Lambda}$ of the constructed label-based code.
The direct part of Theorem 3 is proved by showing that the rate of the label-
based code is close to $R^{\mathrm{G}}(D)$.

Finally, the converse part of Theorem 3 follows from that of Theorem 2, and
the direct part of Theorem 2 follows from that of Theorem 3. The reason is
that we can get an $(\mathcal{X},\hat{\mathcal{X}},\mathcal{U},c)$-CTC code by
assembling the label-based code $(f,\varphi)$ in the direct part of Theorem 3
and a code that compresses class labels losslessly. Formally, we have the
following lemma.

###### Lemma 5

If $(f_{1},\varphi_{1})$ is an
$(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based code,
$R_{1}\in[0,\infty)$, and

$\lim_{n\to\infty}\mathrm{Pr}[|f_{1}(X_{(n]},U_{(n]})|\leq nR_{1}]=1,$ (36)

then there exist an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code
$(f_{2},\varphi_{2})$ and a function $\psi:\\{0,1\\}^{*}\to\mathcal{U}^{*}$
such that

  1. 1.

For every $R_{2}>R_{1}+H(c(X))$,

$\lim_{n\to\infty}\mathrm{Pr}[|f_{2}(X_{(n]})|\leq nR_{2}]=1;$ (37)

and

  2. 2.

If $n\in[\infty)$, $\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$, and
$u_{i}=c(x_{i})$ for all $i\in(n]$, then $\psi(f_{2}(x_{(n]}))=u_{(n]}$ and

$\varphi_{2}(f_{2}(x_{(n]}))=\varphi_{1}(f_{1}(x_{(n]},u_{(n]}),u_{(n]}).$
(38)

The complete proofs of Theorems 2 and 3 are given in Appendix E.

##  V Conclusion

In this paper, we have proposed subsource-dependent fidelity criteria for
composite sources and solved RD problems based on these criteria. The criteria
and hence the results in the paper are useful in situations where some data
from an information source should be encoded more accurately than other data
from the source. CTC coding is widely used in such situations. It is found in
this paper that CTC coding in general has performance loss relative to RD-
optimal coding, even if the classification is perfect. On the other hand, the
performance loss is small for appropriately designed CTC codes. How to design
practical CTC codes is left for future research.

##  Appendix A Proof of Theorem 4

We can verify the following lemmas about Markov chains, and will use them in
the proof.

###### Lemma 6

Suppose $V$, $Y$, and $Z$ are random variables, $B$ is a set, and
$\mathrm{Pr}[Y\in B]>0$. Let $(\tilde{V},\tilde{Y},\tilde{Z})\sim\tilde{P}$,
where $\tilde{P}$ is the conditional distribution of $(V,Y,Z)$ given $Y\in B$.
If $V\leftrightarrow Y\leftrightarrow Z$, then
$\tilde{V}\leftrightarrow\tilde{Y}\leftrightarrow\tilde{Z}$.

###### Lemma 7

Let $\mathcal{Q}$ be a finite set, and $V_{q}$, $Y_{q}$, and $Z_{q}$ be random
variables for every $q\in\mathcal{Q}$. Let a random variable $Q$ take values
in $\mathcal{Q}$ and be independent of
$\\{(V_{q},Y_{q},Z_{q})\\}_{q\in\mathcal{Q}}$. If the support sets of
$\\{Y_{q}\\}_{q\in\mathcal{Q}}$ are disjoint, and $V_{q}\leftrightarrow
Y_{q}\leftrightarrow Z_{q}$ for all $q\in\mathcal{Q}$, then
$V_{Q}\leftrightarrow Y_{Q}\leftrightarrow Z_{Q}$.

Define functions $\\{\chi_{\lambda}\\}_{\lambda\in\Lambda}$ from $\Lambda$ to
$\\{0,1\\}$ by

$\chi_{\lambda}(s)=\begin{cases}1,&s\in\mathcal{S}_{\lambda},\\\
0,&s\not\in\mathcal{S}_{\lambda}.\end{cases}$ (39)

Then $\Xi(D)$ defined in Section II-C equals the set of random variables
$\hat{X}$ satisfying $S\leftrightarrow X\leftrightarrow\hat{X}$ and

$E[\chi_{\lambda}(S)d_{\lambda}(X,\hat{X})]\leq\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]D(\lambda)$
(40)

for all $\lambda\in\Lambda$. To prove (24), we firstly prove that for every
$\hat{X}\in\Xi(D)$, $I(X;\hat{X}|c(X))$ is no less than the right-hand side of
(24). We then prove that

$R^{\mathrm{G}}(D)\leq\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u]R_{u}^{*}(\delta(\cdot,u))+\epsilon$
(41)

for all $\delta\in\Delta(D)$ and $\epsilon\in(0,\infty)$.

Let $\hat{X}\in\Xi(D)$. For $u\in\bar{\mathcal{U}}$, let $Q_{u}$ be the
conditional distribution of $(S,X,\hat{X})$ given $c(X)=u$, and define a
random tuple $(T_{u},Y_{u},\hat{Y}_{u})$ independent of $c(X)$ and having the
distribution $Q_{u}$. Then we have

$I(X;\hat{X}|c(X))=\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u]I(Y_{u};\hat{Y}_{u})$
(42)

and the total expectation formula

$\displaystyle E[\chi_{\lambda}(S)d_{\lambda}(X,\hat{X})]$
$\displaystyle=\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u]E[\chi_{\lambda}(T_{u})d_{\lambda}(Y_{u},\hat{Y}_{u})]$
(43)

for all $\lambda\in\Lambda$. For $u\in\bar{\mathcal{U}}$, we have
$T_{u}\leftrightarrow Y_{u}\leftrightarrow\hat{Y}_{u}$ by Lemma 6. There
exists a function $\delta:\Lambda\times\mathcal{U}\to[0,\infty)$ satisfying

$E[\chi_{\lambda}(T_{u})d_{\lambda}(Y_{u},\hat{Y}_{u})]=\mathrm{Pr}[T_{u}\in\mathcal{S}_{\lambda}]\delta(\lambda,u)$
(44)

for all $\lambda\in\Lambda$ and $u\in\bar{\mathcal{U}}$: Note that (44) holds
true even when $\mathrm{Pr}[T_{u}\in\mathcal{S}_{\lambda}]=0$, because the
left-hand side of (44) is zero in such a case. Hence

$I(Y_{u};\hat{Y}_{u})\geq R_{u}^{*}(\delta(\cdot,u))$ (45)

for all $u\in\bar{\mathcal{U}}$. We can see $\delta\in\Delta(D)$ from (40),
(43), and (44). By (42), (45), and $\delta\in\Delta(D)$, we conclude that
$I(X;\hat{X}|c(X))$ is no less than the right-hand side of (24).

Let $\delta\in\Delta(D)$ and $\epsilon\in(0,\infty)$. Since (41) is apparent
if $R_{u}^{*}(\delta(\cdot,u))=\infty$ for some $u\in\bar{\mathcal{U}}$, we
assume $R_{u}^{*}(\delta(\cdot,u))<\infty$ for all $u\in\bar{\mathcal{U}}$.
Define a random pair $(T_{u},Y_{u})\sim P_{u}$ for every
$u\in\bar{\mathcal{U}}$. There exist random variables
$\\{\hat{Y}_{u}\\}_{u\in\bar{\mathcal{U}}}$ satisfying $T_{u}\leftrightarrow
Y_{u}\leftrightarrow\hat{Y}_{u}$,

$E[\chi_{\lambda}(T_{u})d_{\lambda}(Y_{u},\hat{Y}_{u})]\leq\mathrm{Pr}[T_{u}\in\mathcal{S}_{\lambda}]\delta(\lambda,u),$
(46)

and

$I(Y_{u};\hat{Y}_{u})<R_{u}^{*}(\delta(\cdot,u))+\epsilon$ (47)

for all $\lambda\in\Lambda$ and $u\in\bar{\mathcal{U}}$. Further define a
random variable $U$ independent of
$\\{(T_{u},Y_{u},\hat{Y}_{u})\\}_{u\in\bar{\mathcal{U}}}$ and let $U$ and
$c(X)$ be identically distributed. It is not difficult to verify that
$(S,X,c(X))$ and $(T_{U},Y_{U},U)$ are identically distributed. Consequently,
we can define a random variable $\hat{X}$ such that $(S,X,c(X),\hat{X})$ and
$(T_{U},Y_{U},U,\hat{Y}_{U})$ are identically distributed. Then (42) still
holds, and (43) still holds for all $\lambda\in\Lambda$. For
$\lambda\in\Lambda$, (43), (46), and (25) imply (40). By Lemma 7 we have
$T_{U}\leftrightarrow Y_{U}\leftrightarrow\hat{Y}_{U}$, which implies
$S\leftrightarrow X\leftrightarrow\hat{X}$. Therefore,

$R^{\mathrm{G}}(D)\leq I(X;\hat{X}|c(X)).$ (48)

The inequality (41) follows from (42), (47), and (48).

##  Appendix B Proof of Theorem 5

We use Theorem 4 to prove (28). Define $\bar{\mathcal{U}}$,
$\\{P_{u}\\}_{u\in\bar{\mathcal{U}}}$,
$\\{R_{u}^{*}\\}_{u\in\bar{\mathcal{U}}}$, and $\Delta(D)$ as in Theorem 4. We
can see $\Delta(D)$ is the set of functions
$\delta:\Lambda\times\mathcal{U}\to[0,\infty)$ satisfying (25) for all
$\lambda\in\bar{\Lambda}$. We have
$\Lambda\cap\bar{\mathcal{U}}=\bar{\Lambda}$ because $c(X)=\lambda$ is
equivalent to $S\in\mathcal{S}_{\lambda}$ with probability one for all
$\lambda\in\Lambda$. For $\delta:\Lambda\times\mathcal{U}\to[0,\infty)$ and
$\lambda\in\bar{\Lambda}$, (25) is equivalent to $\delta(\lambda,\lambda)\leq
D(\lambda)$.

Fix $u\in\bar{\mathcal{U}}$ and $\tilde{D}:\Lambda\to[0,\infty)$. Define a
random pair $(T,Y)\sim P_{u}$ and a set
$\tilde{\Lambda}=\\{\lambda\in\Lambda|\mathrm{Pr}[T\in\mathcal{S}_{\lambda}]>0\\}$.
Then

$R_{u}^{*}(\tilde{D})=\inf_{\hat{Y}\in\tilde{\Xi}(\tilde{D})}I(Y;\hat{Y}),$
(49)

where $\tilde{\Xi}(\tilde{D})$ is the set of random variables $\hat{Y}$
satisfying $T\leftrightarrow Y\leftrightarrow\hat{Y}$ and
$E[d_{\lambda}(Y,\hat{Y})|T\in\mathcal{S}_{\lambda}]\leq\tilde{D}(\lambda)$
for all $\lambda\in\tilde{\Lambda}$. Also note

$\displaystyle\mathrm{Pr}[T\in\mathcal{S}_{\lambda}]$
$\displaystyle=\mathrm{Pr}[c(X)=\lambda|c(X)=u]$ (50)
$\displaystyle=\begin{cases}1,&\lambda=u,\\\ 0,&\lambda\not=u\end{cases}$ (51)

for $\lambda\in\Lambda$. If $u\in\bar{\Lambda}$, then $Y\sim Q_{u}$,
$\mathrm{Pr}[T\in\mathcal{S}_{u}]=1$, $\tilde{\Lambda}=\\{u\\}$, and
consequently $\tilde{\Xi}(\tilde{D})$ is the set of random variables $\hat{Y}$
satisfying $T\leftrightarrow Y\leftrightarrow\hat{Y}$ and
$E[d_{u}(Y,\hat{Y})]\leq\tilde{D}(u)$. If $u\not\in\bar{\Lambda}$, then
$u\not\in\Lambda$, $\tilde{\Lambda}=\emptyset$, and consequently
$\tilde{\Xi}(\tilde{D})$ is the set of random variables $\hat{Y}$ satisfying
$T\leftrightarrow Y\leftrightarrow\hat{Y}$. Hence
$R_{u}^{*}(\tilde{D})=R^{(u)}(\tilde{D}(u))$ if $u\in\bar{\Lambda}$, and
$R_{u}^{*}(\tilde{D})=0$ otherwise.

Therefore,

$R^{\mathrm{G}}(D)=\inf_{\delta\in\Delta(D)}\sum_{u\in\bar{\Lambda}}\mathrm{Pr}[c(X)=u]R^{(u)}(\delta(u,u)),$
(52)

and $\Delta(D)$ is the set of functions
$\delta:\Lambda\times\mathcal{U}\to[0,\infty)$ satisfying
$\delta(\lambda,\lambda)\leq D(\lambda)$ for all $\lambda\in\bar{\Lambda}$.
This proves (28).

Now suppose $\bar{\Lambda}$ has only one element $\lambda$. Fix
$\epsilon\in(0,\infty)$. Then there exists a random variable $\hat{X}$
satisfying $S\leftrightarrow X\leftrightarrow\hat{X}$,

$E[d_{\lambda}(X,\hat{X})|S\in\mathcal{S}_{\lambda}]\leq D(\lambda),$ (53)

and

$R^{\mathrm{G}}(D)+\epsilon>I(X;\hat{X}|c(X)).$ (54)

Let $\hat{P}$ be the conditional distribution of $\hat{X}$ given
$c(X)=\lambda$. Let a random variable $\hat{Y}$ have the distribution
$\hat{P}$ and be independent of $(S,X,\hat{X})$. Let a random variable $Z$
equals $\hat{X}$ when $c(X)=\lambda$, and equals $\hat{Y}$ when
$c(X)\not=\lambda$. We will show $Z\in\Xi(D)$, which implies an upper bound
for $R^{*}(D)$. Subtracting $I(S;X)$ from both sides of the data processing
inequality $I(S;X,\hat{X},\hat{Y})\geq I(S;X,Z)$, we get

$I(S;\hat{X}|X)+I(S;\hat{Y}|X,\hat{X})\geq I(S;Z|X).$ (55)

By the chain rule for mutual information,

$I(S,X,\hat{X};\hat{Y})=I(X,\hat{X};\hat{Y})+I(S;\hat{Y}|X,\hat{X}).$ (56)

By (55), (56), and the fact

$I(S;\hat{X}|X)=I(S,X,\hat{X};\hat{Y})=I(X,\hat{X};\hat{Y})=0,$ (57)

we have $S\leftrightarrow X\leftrightarrow Z$. Also note (53) and

$E[d_{\lambda}(X,Z)|S\in\mathcal{S}_{\lambda}]=E[d_{\lambda}(X,\hat{X})|S\in\mathcal{S}_{\lambda}].$
(58)

By definition, we have $Z\in\Xi(D)$, which implies

$R^{*}(D)\leq I(X;Z).$ (59)

The data processing inequality $I(X;\hat{X},\hat{Y},c(X))\geq I(X;Z,c(X))$,
the chain rule for mutual information, $I(X;\hat{Y})=0$, and
$I(X;\hat{X},c(X)|\hat{Y})=I(X;\hat{X},c(X))$ lead to

$I(X;\hat{X},c(X))\geq I(X;Z,c(X)).$ (60)

Subtracting $I(X;c(X))$ from (60), we get

$I(X;\hat{X}|c(X))\geq I(X;Z|c(X)).$ (61)

For $u\in\bar{\mathcal{U}}$, $Z$ has the conditional distribution $\hat{P}$
given $c(X)=u$, no matter $u=\lambda$ or not. Hence $c(X)$ and $Z$ are
independent. Since $I(c(X);Z)=0$, $I(c(X);Z|X)=0$, and
$I(X;Z|c(X))+I(c(X);Z)=I(X;Z)+I(c(X);Z|X)$, we have

$I(X;Z|c(X))=I(X;Z).$ (62)

The inequality (54), (59), (61), and (62) lead to
$R^{\mathrm{G}}(D)+\epsilon>R^{*}(D)$. Since $\epsilon$ can be an arbitrary
number in $(0,\infty)$, we have proved $R^{\mathrm{G}}(D)\geq R^{*}(D)$.

Therefore, $R^{\mathrm{G}}(D)=R^{*}(D)$ if $|\bar{\Lambda}|=1$.

##  Appendix C Proofs of Lemmas

###  C-A Lemma 1

For $n\in[1:\infty)$, since $M_{n}\leq 2^{\lceil nR\rceil}$, there exist
functions $\alpha_{n}:(M_{n}]\to\\{0,1\\}^{\lceil nR\rceil}$ and
$\beta_{n}:\\{0,1\\}^{\lceil nR\rceil}\to(M_{n}]$ satisfying
$\beta_{n}(\alpha_{n}(m))=m$ for all $m\in(M_{n}]$. Define
$f:\mathcal{X}^{*}\to\\{0,1\\}^{*}$ by

$f(\boldsymbol{x})=\begin{cases}\text{the empty
string},&|\boldsymbol{x}|=0,\\\
\gamma(|\boldsymbol{x}|)\alpha_{|\boldsymbol{x}|}(f_{|\boldsymbol{x}|}(\boldsymbol{x})),&|\boldsymbol{x}|>0,\end{cases}$
(63)

where $\gamma(|\boldsymbol{x}|)$ is the compound representation of
$|\boldsymbol{x}|$ (see Section IV-A). Since $\gamma$ is prefix-free, there
exists a function $\varphi:\\{0,1\\}^{*}\to\hat{\mathcal{X}}^{*}$ that maps
the empty string to the empty string and satisfies
$\varphi(\gamma(n)\boldsymbol{b})=\varphi_{n}(\beta_{n}(\boldsymbol{b}))$ for
all $n\in[1:\infty)$ and $\boldsymbol{b}\in\\{0,1\\}^{\lceil nR\rceil}$. We
can see
$\varphi(f(\boldsymbol{x}))=\varphi_{|\boldsymbol{x}|}(f_{|\boldsymbol{x}|}(\boldsymbol{x}))$
for all non-empty strings $\boldsymbol{x}\in\mathcal{X}^{*}$. Also note that
$\varphi(f(\text{the empty string}))$ is the empty string. Therefore,
$(f,\varphi)$ is an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code.
For $n\in[1:\infty)$ and $\boldsymbol{x}\in\mathcal{X}^{n}$, we have
$|\gamma(n)|\leq 1+2\log_{2}(n)$, $|\alpha_{n}(f_{n}(\boldsymbol{x}))|<nR+1$,
and consequently $|f(\boldsymbol{x})|<2+2\log_{2}(n)+nR$. This proves (35).

###  C-B Lemma 5

By basic information theory results, there exists a $\mathcal{U}$-lossless
code $(f_{\mathrm{L}},\varphi_{\mathrm{L}})$ such that

$\lim_{n\to\infty}\mathrm{Pr}[|f_{\mathrm{L}}(U_{(n]})|\leq
nR_{\mathrm{L}}]=1$ (64)

for all $R_{L}>H(c(X))$. For $n\in[\infty)$ and
$\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$, let

$f_{2}(x_{(n]})=\gamma(|f_{\mathrm{L}}(u_{(n]})|+1)f_{\mathrm{L}}(u_{(n]})f_{1}(x_{(n]},u_{(n]}),$
(65)

where $\gamma$ denotes the compound representation introduced in Section IV-A,
and $u_{i}=c(x_{i})$ for all $i\in(n]$. Define
$\varphi_{2}:\\{0,1\\}^{*}\to\hat{\mathcal{X}}^{*}$ and
$\psi:\\{0,1\\}^{*}\to\mathcal{U}^{*}$ such that

$\varphi_{2}(\gamma(l+1)b_{(m]})=\varphi_{1}(b_{(l:m]},\varphi_{\mathrm{L}}(b_{(l]}))$
(66)

and $\psi(\gamma(l+1)b_{(m]})=\varphi_{\mathrm{L}}(b_{(l]})$ hold for all
$l\in[\infty)$, $m\in[l:\infty)$, and $\\{b_{i}\\}_{i=1}^{m}\in\\{0,1\\}^{m}$.
This is possible because $\gamma$ is prefix-free. If $n\in[\infty)$,
$\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$, and $u_{i}=c(x_{i})$ for all
$i\in(n]$, then we can verify $\psi(f_{2}(x_{(n]}))=u_{(n]}$ and (38).

Fix $R_{2}>R_{1}+H(c(X))$. Then there exists a value $R_{\mathrm{L}}$
satisfying $R_{\mathrm{L}}>H(c(X))$ and $R_{1}+R_{\mathrm{L}}<R_{2}$. Equation
(37) follows from (34), (36), (64), (65), and $R_{1}+R_{\mathrm{L}}<R_{2}$.

##  Appendix D Proof of Theorem 1

###  D-A Direct Part

Let $R>R^{*}(D)$. Define functions
$\\{d_{\lambda,\delta}\\}_{\lambda\in\Lambda,\delta\in\mathbb{R}}$ by (32).

By Proposition 1 in [14] and Corollary 7, there exist sequences
$\\{M_{n}\\}_{n=1}^{\infty}$, $\\{f_{n}\\}_{n=1}^{\infty}$, and
$\\{\varphi_{n}\\}_{n=1}^{\infty}$ such that

  1. 1.

For every $n\in[1:\infty)$, $M_{n}\leq 2^{nR^{*}(D)}$ is a positive integer,
$f_{n}$ is a function from $\mathcal{X}^{n}$ to $(M_{n}]$, and $\varphi_{n}$
is a function from $(M_{n}]$ to $\hat{\mathcal{X}}^{n}$; and

  2. 2.

For every $\lambda\in\Lambda$ and $\epsilon\in(0,\infty)$, the probability
that

$\frac{1}{n}\sum_{i=1}^{n}d_{\lambda,D(\lambda)}(X_{i},\hat{X}_{n,i},S_{i})\leq
D(\lambda)+\epsilon$ (67)

tends to 1 as $n\to\infty$, where $\hat{X}_{n,i}$ is defined by
$\\{\hat{X}_{n,i}\\}_{i=1}^{n}=\varphi_{n}(f_{n}(X_{(n]}))$.

By Lemma 1, there exists an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length
code $(f,\varphi)$ satisfying (9) and
$\varphi(f(\boldsymbol{x}))=\varphi_{|\boldsymbol{x}|}(f_{|\boldsymbol{x}|}(\boldsymbol{x}))$
for all non-empty strings $\boldsymbol{x}\in\mathcal{X}^{*}$. Hence there
exists $n_{1}\in[1:\infty)$ such that $|f(\boldsymbol{x})|\leq nR$ for all
integers $n>n_{1}$ and $\boldsymbol{x}\in\mathcal{X}^{n}$. We then have

$\lim_{n\to\infty}\mathrm{Pr}[|f(X_{(n]})|\leq nR]=1.$ (68)

We now analyze the distortion of $(f,\varphi)$. Fix $\lambda\in\bar{\Lambda}$
and $\epsilon\in(0,\infty)$. Since $\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]>0$,
the probability that

$\frac{1}{n}\sum_{i=1}^{n}d_{\lambda,D(\lambda)}(X_{i},\hat{X}_{n,i},S_{i})\leq
D(\lambda)+\frac{\epsilon}{2}\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]$ (69)

tends to 1 as $n\to\infty$. Define a function
$\chi_{\lambda}:\mathcal{S}\to\\{0,1\\}$ by (39). Then

$\displaystyle d_{\lambda,D(\lambda)+\epsilon}(X_{i},\hat{X}_{n,i},S_{i})={}$
$\displaystyle d_{\lambda,D(\lambda)}(X_{i},\hat{X}_{n,i},S_{i})$
$\displaystyle+\epsilon-\epsilon\chi_{\lambda}(S_{i})$ (70)

with probability one for all integers $n$ and $i$ satisfying $0<i\leq n$. By
the law of large numbers, the probability that

$\frac{1}{n}\sum_{i=1}^{n}\chi_{\lambda}(S_{i})\geq\frac{1}{2}\mathrm{Pr}[S\in\mathcal{S}_{\lambda}]$
(71)

tends to 1 as $n\to\infty$. If (70) holds for all $i\in(n]$ with
$n\in[1:\infty)$, (69) holds, and (71) holds, then we have

$\frac{1}{n}\sum_{i=1}^{n}d_{\lambda,D(\lambda)+\epsilon}(X_{i},\hat{X}_{n,i},S_{i})\leq
D(\lambda)+\epsilon,$ (72)

which implies that $S_{(n]}$, $X_{(n]}$, and $\varphi(f(X_{(n]}))$ meet the
fidelity criterion $(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$.
Therefore, the probability with which $S_{(n]}$, $X_{(n]}$, and
$\varphi(f(X_{(n]}))$ meet the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$ tends to 1 as
$n\to\infty$.

For $\lambda\in\Lambda\setminus\bar{\Lambda}$, $\epsilon\in(0,\infty)$, and
$n\in[1:\infty)$, because $S_{i}\not\in\mathcal{S}_{\lambda}$ with probability
one for all $i\in(n]$, the probability with which $S_{(n]}$, $X_{(n]}$, and
$\varphi(f(X_{(n]}))$ meet the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$ is 1. In conclusion,
this probability tends to 1 as $n\to\infty$ for all $\lambda\in\Lambda$ and
$\epsilon\in(0,\infty)$. This fact and (68) lead to the conclusion that
$(f,\varphi)$ achieves $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$.

###  D-B Converse Part

Suppose an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code
$(f,\varphi)$ achieves $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$.

We firstly fix an arbitrary $n\in[1:\infty)$ and define a block code. Let
$M_{n}$ be the number of the bit strings in $f(\mathcal{X}^{n})$ whose length
does not exceed $nR$. There exists functions $f_{n}:\mathcal{X}^{n}\to(M_{n}]$
and $\varphi_{n}:(M_{n}]\to\hat{\mathcal{X}}^{n}$ such that for every
$\boldsymbol{x}\in\mathcal{X}^{n}$, if $|f(\boldsymbol{x})|\leq nR$, then
$\varphi_{n}(f_{n}(\boldsymbol{x}))=\varphi(f(\boldsymbol{x}))$. Since

$M_{n}\leq\sum_{l=0}^{\lfloor nR\rfloor}2^{l}=2^{\lfloor nR\rfloor+1}-1\leq
2^{nR+1},$ (73)

the rate $\log_{2}(M_{n})/n$ of the block code $(f_{n},\varphi_{n})$ does not
exceed $R+1/n$.

Now we analyze the distortion of the block codes. Fix $\lambda\in\Lambda$ and
$\epsilon\in(0,\infty)$. For $n\in[1:\infty)$, define the following sets:

  * •

$F_{n}$ — the set of
$(\boldsymbol{s},\boldsymbol{x})\in\mathcal{S}^{n}\times\mathcal{X}^{n}$ such
that $\boldsymbol{s}$, $\boldsymbol{x}$, and $\varphi(f(\boldsymbol{x}))$ meet
the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$; and

  * •

$G_{n}$ — the set of
$(\\{s_{i}\\}_{i=1}^{n},\\{x_{i}\\}_{i=1}^{n})\in\mathcal{S}^{n}\times\mathcal{X}^{n}$
such that $\\{\hat{x}_{i}\\}_{i=1}^{n}=\varphi_{n}(f_{n}(x_{(n]}))$ satisfies

$\frac{1}{n}\sum_{i=1}^{n}d_{\lambda,D(\lambda)}(x_{i},\hat{x}_{i},s_{i})\leq
D(\lambda)+\epsilon.$ (74)

For $n\in[1:\infty)$ and $(\\{s_{i}\\}_{i=1}^{n},\\{x_{i}\\}_{i=1}^{n})$, if
$(s_{(n]},x_{(n]})\in F_{n}$, $|f(x_{(n]})|\leq nR$, and
$\\{\hat{x}_{i}\\}_{i=1}^{n}=\varphi_{n}(f_{n}(x_{(n]}))$, then we have
$\\{\hat{x}_{i}\\}_{i=1}^{n}=\varphi(f(x_{(n]}))$,

$\frac{1}{n}\sum_{i=1}^{n}d_{\lambda,D(\lambda)+\epsilon}(x_{i},\hat{x}_{i},s_{i})\leq
D(\lambda)+\epsilon,$ (75)

and consequently $(s_{(n]},x_{(n]})\in G_{n}$ by the discussions in Section
IV-A and the fact that

$d_{\lambda,D(\lambda)}(x,\hat{x},s)\leq
d_{\lambda,D(\lambda)+\epsilon}(x,\hat{x},s)$ (76)

for all $x\in\mathcal{X}$, $\hat{x}\in\hat{\mathcal{X}}$, and
$s\in\mathcal{S}$. Hence for $n\in[1:\infty)$, we have $(S_{(n]},X_{(n]})\in
G_{n}$ whenever $(S_{(n]},X_{(n]})\in F_{n}$ and $|f(X_{(n]})|\leq nR$. Also
note that $\mathrm{Pr}[(S_{(n]},X_{(n]})\in F_{n}]$ and
$\mathrm{Pr}[|f(X_{(n]})|\leq nR]$ tend to 1 as $n\to\infty$. Therefore

$\lim_{n\to\infty}\mathrm{Pr}[(S_{(n]},X_{(n]})\in G_{n}]=1.$ (77)

The inequality $R\geq R^{*}(D)$ follows from Proposition 1 in [14] and
Corollary 7.

##  Appendix E Proof of Theorems 2 and 3

In Section IV-B we have seen that the converse part of Theorem 2 implies that
of Theorem 3. Also, the direct part of Theorem 3 implies that of Theorem 2.
Therefore, we only need to prove the converse part of Theorem 2 and the direct
part of Theorem 3.

###  E-A Converse Part of Theorem 2

Suppose an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length code
$(f,\varphi)$ achieves $(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$, $\psi$ is a
function from $\\{0,1\\}^{*}$ to $\mathcal{U}^{*}$, and
$\psi(f(X_{(n]}))=U_{(n]}$ with probability one for all $n\in[\infty)$.

Define $\tilde{\lambda}$, $\tilde{\Lambda}$,
$\\{\tilde{d}_{\lambda}\\}_{\lambda\in\tilde{\Lambda}}$,
$\\{\tilde{\mathcal{S}}_{\lambda}\\}_{\lambda\in\tilde{\Lambda}}$,
$\tilde{R}$, and $\tilde{D}$ as in Corollary 4. For
$\boldsymbol{b}\in\\{0,1\\}^{*}$, let
$\tilde{\varphi}(\boldsymbol{b})=\\{(\hat{x}_{i},\hat{u}_{i})\\}_{i=1}^{n}$,
where $\\{\hat{x}_{i}\\}_{i=1}^{n}=\varphi(\boldsymbol{b})$ and
$\\{\hat{u}_{i}\\}_{i=1}^{n}=\psi(\boldsymbol{b})$.

Fix $\epsilon\in(0,\infty)$. For $\lambda\in\Lambda$ and $n\in[\infty)$, let
$p_{\lambda,n}$ denote the probability with which $S_{(n]}$, $X_{(n]}$, and
$\varphi(f(X_{(n]}))$ meet the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$. For
$\lambda\in\tilde{\Lambda}$ and $n\in[\infty)$, let $\tilde{p}_{\lambda,n}$
denote the probability with which $S_{(n]}$, $X_{(n]}$, and
$\tilde{\varphi}(f(X_{(n]}))$ meet the fidelity criterion
$(\tilde{d}_{\lambda},\tilde{\mathcal{S}}_{\lambda},\tilde{D}(\lambda)+\epsilon)$.
Then for $\lambda\in\Lambda$, $\tilde{p}_{\lambda,n}=p_{\lambda,n}\to 1$ as
$n\to\infty$. For $n\in[\infty)$, because $\psi(f(X_{(n]}))=U_{(n]}$ with
probability one, $\tilde{p}_{\tilde{\lambda},n}=1$. In short,
$\tilde{p}_{\lambda,n}\to 1$ as $n\to\infty$ for all
$\lambda\in\tilde{\Lambda}$.

Also note that $\mathrm{Pr}[|f(X_{(n]})|\leq nR]\to 1$ as $n\to\infty$.
Therefore, the $(\mathcal{X},\hat{\mathcal{X}}\times\mathcal{U})$-variable-
length code $(f,\tilde{\varphi})$ achieves $(R,\tilde{D})$ for $(S,X)$ and
$\\{(\tilde{d}_{\lambda},\tilde{\mathcal{S}}_{\lambda})\\}_{\lambda\in\tilde{\Lambda}}$.
By the converse part of Theorem 1, we have $R\geq\tilde{R}(\tilde{D})$, i.e.
$R\geq R^{\mathrm{C}}(D)$.

###  E-B Direct Part of Theorem 3

Suppose $R>R^{\mathrm{G}}(D)$.

Define $\bar{\mathcal{U}}$, $\\{P_{u}\\}_{u\in\bar{\mathcal{U}}}$, and
$\\{R_{u}^{*}\\}_{u\in\bar{\mathcal{U}}}$ as in Theorem 4. By Theorem 4, there
exists a function $\delta:\Lambda\times\mathcal{U}\to[0,\infty)$ satisfying
$\sum_{u\in\bar{\mathcal{U}}}\mathrm{Pr}[c(X)=u]R_{u}^{*}(\delta(\cdot,u))<R$
and (25) for all $\lambda\in\Lambda$. Then there exist
$\\{q_{u}\\}_{u\in\mathcal{U}}$ and $\\{R_{u}\\}_{u\in\mathcal{U}}$ satisfying

$\sum_{u\in\bar{\mathcal{U}}}q_{u}R_{u}<R,$ (78)

$\mathrm{Pr}[c(X)=u]<q_{u}$, and $R_{u}^{*}(\delta(\cdot,u))<R_{u}$ for all
$u\in\bar{\mathcal{U}}$. For $u\in\bar{\mathcal{U}}$, by the direct part of
Theorem 1, there exists an $(\mathcal{X},\hat{\mathcal{X}})$-variable-length
code $(f_{u},\varphi_{u})$ achieving $(R_{u},\delta(\cdot,u))$ for a
$P_{u}$-distributed random pair (see Theorem 4) and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$. For
$u\in\mathcal{U}\setminus\bar{\mathcal{U}}$, define
$f_{u}:\mathcal{X}^{*}\to\\{0,1\\}^{*}$ by
$f_{u}(\boldsymbol{x})=\gamma(|\boldsymbol{x}|+1)$, and let
$\varphi_{u}:\\{0,1\\}^{*}\to\hat{\mathcal{X}}^{*}$ satisfy
$\varphi_{u}(\gamma(k+1))\in\hat{\mathcal{X}}^{k}$ for all $k\in[\infty)$,
where $\gamma$ is the compound representation introduced in Section IV-A. Then
$\\{(f_{u},\varphi_{u})\\}_{u\in\mathcal{U}}$ are
$(\mathcal{X},\hat{\mathcal{X}})$-variable-length codes. These variable-length
codes will be combined to form the desired label-based code. Let $\mu(i)$
denote the $i$-th element of the set $\mathcal{U}$: That is,
$\mathcal{U}=\\{\mu(1),\mu(2),\cdots,\mu(|\mathcal{U}|)\\}$. For
$n\in[\infty)$, $\\{x_{i}\\}_{i=1}^{n}\in\mathcal{X}^{n}$, and
$\\{u_{i}\\}_{i=1}^{n}\in\mathcal{U}^{n}$, let
$f(x_{(n]},u_{(n]})=\boldsymbol{b}_{\mu(1)}\boldsymbol{b}_{\mu(2)}\cdots\boldsymbol{b}_{\mu(|\mathcal{U}|)}$,
where $J(u)=\\{i\in(n]|u_{i}=u\\}$ and

$\boldsymbol{b}_{u}=\begin{cases}\gamma(|f_{u}(x_{J(u)})|+1)f_{u}(x_{J(u)}),&u\in\bar{\mathcal{U}},\\\
f_{u}(x_{J(u)}),&u\not\in\bar{\mathcal{U}}\end{cases}$ (79)

for all $u\in\mathcal{U}$. Since $\gamma$ is prefix-free, the bit strings
$\\{f_{u}(x_{J(u)})\\}_{u\in\mathcal{U}}$ can be recovered from
$f(x_{(n]},u_{(n]})$. Hence there exists a function
$\varphi:\\{0,1\\}^{*}\times\mathcal{U}^{*}\to\hat{\mathcal{X}}^{*}$ such that

  1. 1.

$(f,\varphi)$ is an $(\mathcal{X},\hat{\mathcal{X}},\mathcal{U})$-label-based
code; and

  2. 2.

If $n\in[\infty)$ and (10) hold, then
$\hat{x}_{J(u)}=\varphi_{u}(f_{u}(x_{J(u)}))$ for all $u\in\mathcal{U}$, where
$J(u)=\\{i\in(n]|u_{i}=u\\}$.

Define

$\\{\hat{X}_{i}^{(n)}\\}_{i=1}^{n}=\varphi(f(X_{(n]},U_{(n]}),U_{(n]})$ (80)

and $J(n,u)=\\{i\in(n]|U_{i}=u\\}$ for $n\in[1:\infty)$ and $u\in\mathcal{U}$.
Then

$\displaystyle|f(X_{(n]},U_{(n]})|=\sum_{u\in\mathcal{U}\setminus\bar{\mathcal{U}}}|\gamma(|J(n,u)|+1)|$
$\displaystyle+\sum_{u\in\bar{\mathcal{U}}}|\gamma(|f_{u}(X_{J(n,u)})|+1)|+\sum_{u\in\bar{\mathcal{U}}}|f_{u}(X_{J(n,u)})|$
(81)

with probability one for all $n\in[1:\infty)$, and

$\hat{X}_{J(n,u)}^{(n)}=\varphi_{u}(f_{u}(X_{J(n,u)}))$ (82)

with probability one for all $n\in[1:\infty)$ and $u\in\mathcal{U}$.

We now analyze the performance of $(f,\varphi)$. Fix $u\in\bar{\mathcal{U}}$
and $\epsilon\in(0,\infty)$. Define random pairs
$\\{(T_{i},Y_{i})\\}_{i=1}^{\infty}$ as in Lemma 2. Then

$\lim_{k\to\infty}\mathrm{Pr}[(T_{(k]},Y_{(k]})\in F_{u,\epsilon}]=1,$ (83)

where $F_{u,\epsilon}$ is the set of
$(\boldsymbol{s},\boldsymbol{x})\in\mathcal{S}^{*}\times\mathcal{X}^{*}$ such
that $|f_{u}(\boldsymbol{x})|\leq|\boldsymbol{x}|R_{u}$ and that
$\boldsymbol{s}$, $\boldsymbol{x}$, and $\varphi_{u}(f_{u}(\boldsymbol{x}))$
meet the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},\delta(\lambda,u)+\epsilon)$ for all
$\lambda\in\Lambda$. By Lemma 3 we have

$\lim_{n\to\infty}\mathrm{Pr}[(T_{J(n,u)},Y_{J(n,u)})\in F_{u,\epsilon}]=1.$
(84)

By Lemma 2, $(S_{J(n,u)},X_{J(n,u)})$ and $(T_{J(n,u)},Y_{J(n,u)})$ are
identically distributed for all $n\in[1:\infty)$. Hence

$\lim_{n\to\infty}\mathrm{Pr}[(S_{J(n,u)},X_{J(n,u)})\in F_{u,\epsilon}]=1.$
(85)

By the law of large numbers, the probability of $|J(n,u)|\leq nq_{u}$ also
tends to 1 as $n\to\infty$. Hence

$\lim_{n\to\infty}\mathrm{Pr}[|f_{u}(X_{J(n,u)})|\leq nq_{u}R_{u}]=1.$ (86)

Fix $\lambda\in\bar{\Lambda}$ and $\epsilon\in(0,\infty)$. Define
$J_{n}=\\{i\in(n]|S_{i}\in\mathcal{S}_{\lambda}\\}$ for $n\in[1:\infty)$. By
(25) and the law of large numbers, the probability that

$\sum_{u\in\mathcal{U}}|J(n,u)\cap
J_{n}|\left(\delta(\lambda,u)+\frac{\epsilon}{2}\right)\leq|J_{n}|(D(\lambda)+\epsilon)$
(87)

tends to 1 as $n\to\infty$. Also note that, for every $u\in\mathcal{U}$, the
probability with which $S_{J(n,u)}$, $X_{J(n,u)}$, and
$\varphi_{u}(f_{u}(X_{J(n,u)}))$ meet the fidelity criterion
$(d_{\lambda},\mathcal{S}_{\lambda},\delta(\lambda,u)+\epsilon/2)$ tends to 1
as $n\to\infty$. By (80), (82), and Lemma 4, the probability with which
$S_{(n]}$, $X_{(n]}$, and $\varphi(f(X_{(n]},U_{(n]}),U_{(n]})$ meet the
fidelity criterion $(d_{\lambda},\mathcal{S}_{\lambda},D(\lambda)+\epsilon)$
tends to 1 as $n\to\infty$.

Furthermore, $\lim_{n\to\infty}\mathrm{Pr}[|f(X_{(n]},U_{(n]})|\leq nR]=1$
follows from (34), (78), (81), and (86). Therefore, $(f,\varphi)$ achieves
$(R,D)$ for $(S,X)$ and
$\\{(d_{\lambda},\mathcal{S}_{\lambda})\\}_{\lambda\in\Lambda}$ given $c(X)$.

## References

  * [1] C. Shannon, “A mathematical theory of communication,” _Bell Syst. Tech. J._ , vol. 27, pp. 379–423 and 623–656, Jul. 1948.
  * [2] ——, “Coding theorems for a discrete source with a fidelity criterion,” _IRE Conv. Rec._ , 1959.
  * [3] T. Berger, _Rate Distortion Theory_. Englewood Cliffs, NJ, USA: Prentice-Hall, 1971.
  * [4] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. Hoboken, New Jersey: John Wiley & Sons, 2006\.
  * [5] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_ , 2nd ed. Cambridge University Press, 2011.
  * [6] R. Szeliski, _Computer Vision_. Springer, 2011.
  * [7] L. Rabiner and R. Schafer, “Introduction to digital speech processing,” _Found. Trends Signal Process._ , vol. 1, no. 1-2, pp. 1–194, Dec. 2007.
  * [8] C. Christopoulos, A. Skodras, and T. Ebrahimi, “The JPEG2000 still image coding system: An overview,” _IEEE Trans. Consum. Electron._ , vol. 46, no. 4, pp. 1103–1127, Nov. 2000.
  * [9] R. Gray, “Conditional rate-distortion theory,” Information System Laboratory, Stanford University, Stanford, California, Tech. Rep. 6502-2, Oct. 1972.
  * [10] ——, “A new class of lower bounds to information rates of stationary sources via conditional rate-distortion functions,” _IEEE Trans. Inf. Theory_ , vol. 19, no. 4, pp. 480–489, Jul. 1973.
  * [11] A. Wyner and J. Ziv, “The rate-distortion function for source coding with side information at the decoder,” _IEEE Trans. Inf. Theory_ , vol. 22, no. 1, pp. 1–10, Jan. 1976.
  * [12] T. Berger, “The source coding game,” _IEEE Trans. Inf. Theory_ , vol. 17, no. 1, pp. 71–76, Jan. 1971.
  * [13] T. Linder, R. Zamir, and K. Zeger, “On source coding with side-information-dependent distortion measures,” _IEEE Trans. Inf. Theory_ , vol. 46, no. 7, pp. 2697–2704, Nov. 2000.
  * [14] E. Martinian, G. Wornell, and R. Zamir, “Source coding with distortion side information,” _IEEE Trans. Inf. Theory_ , vol. 54, no. 10, pp. 4638–4665, Oct. 2008.
  * [15] R. Dobrushin and B. Tsybakov, “Information transmission with additional noise,” _IRE Trans. Inf. Theory_ , vol. 8, no. 5, pp. 293–304, Sep. 1962\.
  * [16] J. Wolf and J. Ziv, “Transmission of noisy information to a noisy receiver with minimum distortion,” _IEEE Trans. Inf. Theory_ , vol. 16, no. 4, pp. 406–411, Jul. 1970.
  * [17] H. Witsenhausen, “Indirect rate distortion problems,” _IEEE Trans. Inf. Theory_ , vol. 26, no. 5, pp. 518–521, Sep. 1980.
  * [18] R. Fontana, “Universal codes for a class of composite sources (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 26, no. 4, pp. 480–482, Jul. 1980.
  * [19] H. Rosenthal and J. Binia, “On the epsilon entropy of mixed random variables,” _IEEE Trans. Inf. Theory_ , vol. 34, no. 5, pp. 1110–1114, Sep. 1988.
  * [20] A. Gyorgy, T. Linder, and K. Zeger, “On the rate-distortion function of random vectors and stationary sources with mixed distributions,” _IEEE Trans. Inf. Theory_ , vol. 45, no. 6, pp. 2110–2115, Sep. 1999.
  * [21] C. Weidmann and M. Vetterli, “Rate distortion behavior of sparse sources,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 8, pp. 4969–4992, Aug. 2012.
  * [22] R. Gray and L. Davisson, “Source coding theorems without the ergodic assumption,” _IEEE Trans. Inf. Theory_ , vol. 20, no. 4, pp. 502–516, Jul. 1974.
  * [23] H. Kalveram and P. Meissner, “Itakura-Saito clustering and rate distortion functions for a composite source model of speech,” _Signal Processing_ , vol. 18, no. 2, pp. 195–216, Oct. 1989.
  * [24] J. Gibson and J. Hu, “Rate distortion bounds for voice and video,” _Found. Trends Commun. Inf. Theory_ , vol. 10, no. 4, pp. 379–514, Feb. 2014\.
  * [25] J. Gibson, “Rate distortion functions and rate distortion function lower bounds for real-world sources,” _Entropy_ , vol. 19, no. 11, pp. 1–22, Nov. 2017.
  * [26] L. Rabiner, “A tutorial on hidden Markov models and selected applications in speech recognition,” _Proc. IEEE_ , vol. 77, no. 2, pp. 257–286, Feb. 1989\.
  * [27] I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, “Generative adversarial nets,” in _Advances Neural Inf. Process. Syst._ , vol. 27, 2014, pp. 1–9.
  * [28] D. P. Kingma and M. Welling, “Auto-encoding variational Bayes,” in _Proc. Int. Conf. Learn. Representations_ , 2014, pp. 1–14.
  * [29] F.-A. Croitoru, V. Hondru, R. T. Ionescu, and M. Shah, “Diffusion models in vision: A survey,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 45, no. 9, pp. 10 850–10 869, Sep. 2023.
  * [30] D. Gündüz, Z. Qin, I. E. Aguerri, H. S. Dhillon, Z. Yang, A. Yener, K. K. Wong, and C.-B. Chae, “Beyond transmitting bits: Context, semantics, and task-oriented communications,” _IEEE J. Sel. Areas Commun._ , vol. 41, no. 1, pp. 5–41, Jan. 2023.
  * [31] A. Kipnis, S. Rini, and A. J. Goldsmith, “The rate-distortion risk in estimation from compressed data,” _IEEE Trans. Inf. Theory_ , vol. 67, no. 5, pp. 2910–2924, May 2021.
  * [32] J. Liu, W. Zhang, and H. V. Poor, “A rate-distortion framework for characterizing semantic information,” in _Proc. IEEE Int. Symp. Inf. Theory (ISIT)_ , 2021, pp. 2894–2899.
  * [33] J. Liu, S. Shao, W. Zhang, and H. V. Poor, “An indirect rate-distortion characterization for semantic sources: General model and the case of Gaussian observation,” _IEEE Trans. Commun._ , vol. 70, no. 9, pp. 5946–5959, Sep. 2022.
  * [34] T. Guo, Y. Wang, J. Han, H. Wu, B. Bai, and W. Han, “Semantic compression with side information: A rate-distortion perspective,” Aug. 2022. [Online]. Available: https://arxiv.org/abs/2208.06094
  * [35] Y. Wang, T. Guo, B. Bai, and W. Han, “The estimation-compression separation in semantic communication systems,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Nov. 2022, pp. 315–320.
  * [36] Y. Xiao, X. Zhang, Y. Li, G. Shi, and T. Başar, “Rate-distortion theory for strategic semantic communication,” in _Proc. IEEE Inf. Theory Workshop (ITW)_ , Nov. 2022, pp. 279–284.
  * [37] P. Stavrou and M. Kountouris, “The role of fidelity in goal-oriented semantic communication: A rate distortion approach,” _IEEE Trans. Commun._ , vol. 71, no. 7, pp. 3918–3931, Jul. 2023.
  * [38] A. Das, A. DeJaco, S. Manjunath, A. Ananthapadmanabhan, J. Huang, and E. Choy, “Multimode variable bit rate speech coding: an efficient paradigm for high-quality low-rate representation of speech signal,” in _Proc. IEEE Int. Conf. Acoust., Speech, and Signal Process. (ICASSP)_ , Mar. 1999, pp. 2307–2310.
  * [39] H. Wang, Q. Li, H. Sun, Z. Chen, Y. Hao, J. Peng, Z. Yuan, J. Fu, and Y. Jiang, “VaBUS: Edge-cloud real-time video analytics via background understanding and subtraction,” _IEEE J. Sel. Areas Commun._ , vol. 41, no. 1, pp. 90–106, Jan. 2023.
  * [40] R. Gray, “Gauss mixture vector quantization,” in _Proc. IEEE Int. Conf. Acoust., Speech and Signal Process. (ICASSP)_ , 2001, pp. 1769–1772.
  * [41] A. Subramaniam and B. Rao, “PDF optimized parametric vector quantization of speech line spectral frequencies,” _IEEE Trans. Speech Audio Process._ , vol. 11, no. 2, pp. 130–142, Mar. 2003.
  * [42] D. Zhao, J. Samuelsson, and M. Nilsson, “On entropy-constrained vector quantization using Gaussian mixture models,” _IEEE Trans. Commun._ , vol. 56, no. 12, pp. 2094–2104, Dec. 2008.
  * [43] R. Gray, _Entropy and Information Theory_ , 1st ed. New York: Springer-Verlag, 1990, corrected version of June 2023\. [Online]. Available: https://ee.stanford.edu/~gray/it.html
  * [44] S. Arimoto, “An algorithm for computing the capacity of arbitrary discrete memoryless channels,” _IEEE Trans. Inf. Theory_ , vol. 18, no. 1, pp. 14–20, Jan. 1972.
  * [45] R. Blahut, “Computation of channel capacity and rate-distortion functions,” _IEEE Trans. Inf. Theory_ , vol. 18, no. 4, pp. 460–473, Jul. 1972.
  * [46] P. Elias, “Universal codeword sets and representations of the integers,” _IEEE Trans. Inf. Theory_ , vol. 21, no. 2, pp. 194–203, Mar. 1975.