#  The Price of Distributed:
Rate Loss in the CEO Problem

Arda Atalik1, Alper Köse2 and Michael Gastpar3  1Department of Electrical and
Electronics Engineering, Bilkent University<EMAIL_ADDRESS>2Department of Electrical and Electronics Engineering, Bogazici University,
<EMAIL_ADDRESS>3School of Computer and Communication Sciences, EPFL,
<EMAIL_ADDRESS>
###### Abstract

In the distributed remote (CEO) source coding problem, many separate encoders
observe independently noisy copies of an underlying source. The rate loss is
the difference between the rate required in this distributed setting and the
rate that would be required in a setting where the encoders can fully
cooperate. In this sense, the rate loss characterizes the price of distributed
processing. We survey and extend the known results on the rate loss in various
settings, with a particular emphasis on the case where the noise in the
observations is Gaussian, but the underlying source is general.

###### Index Terms:

CEO problem, rate loss, remote source coding problem, Gaussian noise.

##  I Introduction and Motivation

The distributed remote (CEO) source coding problem has been presented in [1]
with the motivation to investigate the limits of a decentralized estimation
task and attracted researchers’ interest. In the CEO problem, the data
sequence, source, cannot be observed directly and the decoder only observes
the rate-limited noisy versions of the original sequence. The decoder produces
an approximation of the underlying source exploiting these observations. This
is illustrated in Figure 1.

In [1], Berger et al. investigate the asymptotic behavior of the minimal error
frequency as the number of agents and the total data rate of encoders go to
infinity where the source and observations are assumed to be discrete and
memoryless. The case, in which the source is assumed to be Gaussian
distributed and the observation noise is again Gaussian and the fidelity
criterion being mean-square error (MSE), is referred as the quadratic Gaussian
CEO problem and has been investigated in various works as [2, 3, 4, 5].

Eswaran and Gastpar consider the observation noise as additive Gaussian,
however they allow the underlying source to be any continuous distribution
with a constraint of having a finite differential entropy in [6]. Likewise, in
this paper, the source is allowed to be arbitrarily distributed ensuring that
it has a finite variance and differential entropy.

$X^{n}$$+$$W_{1}^{n}$$+$$W_{2}^{n}$$+$$W_{M}^{n}$$Y_{1}^{n}$enc
1$nR_{1}$$Y_{2}^{n}$enc 2$nR_{2}$$\vdots$$Y_{M}^{n}$enc
$M$$nR_{M}$dec${\hat{X}}^{n}$ Figure 1: The $M$-agent CEO problem. The rate
loss is the difference in compression rate required in the distributed setting
illustrated here versus the rate that would be required if all $M$ encoders
could cooperate fully. It characterizes the price of distributed processing.

###  I-A Contribution and Outline

In Section II, we revisit the well known rate loss for the special case where
the underlying source is Gaussian. We explicitly explore the limiting regimes.
The main contributions of the paper are in Section III:

  * •

In Section III-A, we compare two known lower bounds of the rate distortion
function in the remote source coding problem.

  * •

In Section III-B, we provide novel rate loss bounds for the $M-$agent AWGN CEO
problem and compare with the previous bounds analytically and numerically.

  * •

In Section III-C, we establish the asymptotic behavior of the rate loss
bounds. For example, we consider the case where the number of agents $M$
becomes large: In this regime, the rate loss typically scales linearly in the
number of agents $M.$ We also consider the case where the distortion tends to
the minimum possible distortion: In this regime, the rate loss typically
scales like $\log\frac{1}{\delta},$ where $\delta$ is the gap from the minimum
distortion.

  * •

In Section III-D, we present comparisons between the various bounds proposed
in this paper as well as bounds that appear in previous work. We also show a
number of numerical evaluations for concrete cases, such as when the
underlying source distribution is Uniform or Laplacian.

  * •

Section IV concludes the paper and presents some future directions.

###  I-B Notation

We use uppercase letters $X,\,Y$ to denote random variables, and lowercase
letters $x,\,y$ to denote their realizations. Given a square-integrable,
absolutely continuous random variable $X$ with density $p_{X}(x)$, its
variance $\mathsf{Var}\left(X\right)$ is denoted as $\sigma_{X}^{2}$, and its
differential entropy is

$h(X)=-\int p_{X}(x)\,\log p_{X}(x)\,dx.$ (1)

The entropy power of $X$ is $N(X)=\dfrac{e^{2h(X)}}{2\,\pi\,e}$, mutual
information is
$I(X;Y)=h(Y)-h(Y\operatorname*{|}X)=h(X)-h(X\operatorname*{|}Y)$ and its
Fisher information is $J(X)=\int p_{X}(x)\,\left(\frac{d}{dx}\,\log
p_{X}(x)\right)^{2}dx$, see [7, p.671]. Denote the conditional expectation of
$X$ given $Y$ as

$V=\mathsf{E}\left[X\operatorname*{|}Y\right]$ (2)

and its corresponding mean-square error as

$\mathsf{mmse}\left(X\operatorname*{|}Y\right)=\mathsf{E}\left[\mathsf{Var}\left(X\operatorname*{|}Y\right)\right]=\mathsf{E}\left[(X-V)^{2}\right].$
(3)

We denote the asymptotic equivalence of $f(x)$ and $g(x)$ around $x=x_{0}$ by
$f(x)\sim g(x)$. That is, $\lim_{x\rightarrow x_{0}}\frac{f(x)}{g(x)}=1$.

In this paper, our primary focus concerns the additive Gaussian noise model,

$Y=X+W,$ (4)

where $W$ is a zero-mean Gaussian random variable of variance
$\sigma_{W}^{2},$ independent of the signal $X,$ and where $X$ has an
arbitrary distribution. This is illustrated pictorially in Figure 2.

$X$$W\sim\mathcal{N}(0,\sigma_{W}^{2})$$Y=X+W$$+$ Figure 2: The additive
Gaussian noise observation model

###  I-C Differential Entropy of the Conditional Mean

The probability density function of the conditional mean is calculated
explicitly in [8], but in general, it may not be easy to calculate for
arbitrary input distributions. The following identity is useful as it omits
the calculation of the density of
$\mathsf{E}\left[X\operatorname*{|}Y\right]$. Our theorem is based on the
following lemma, which relates the differential entropy of the conditional
expectation to that of the output.

###### Theorem 1

. For the model given in Equation (4) with $\sigma_{W}^{2}>0,$ the
differential entropy of the conditional mean can be written as

$h(\mathsf{E}\left[X\operatorname*{|}Y\right])=h(Y)+\mathsf{E}\left[\log\left(\frac{1}{\sigma_{W}^{2}}\mathsf{Var}\left(X\operatorname*{|}Y\right)\right)\right].$
(5)

Furthermore, we have the following lower bound:

$h(\mathsf{E}\left[X\operatorname*{|}Y\right])+h(Y)\geq 2h(X).$ (6)

###### Proof.

This lemma follows by careful application of several known tools, including
Tweedie’s formula [9] and the Hatsell-Nolte identity [10]. A full proof is
provided in [11]. ∎

##  II Exact Rate Loss in the Gaussian Input $M-$Agent AWGN CEO Problem

The exact loss for the Gaussian input is well-known [3]. In this case, the
smallest attainable distortion (even with unlimited rates) is well known to be

$\displaystyle D_{\mathcal{N},0}$
$\displaystyle=\frac{\sigma_{X}^{2}\sigma_{W}^{2}}{M\,\sigma_{X}^{2}+\sigma_{W}^{2}}.$
(7)

The exact rate loss is given in the following proposition:

###### Proposition 2

. For the model given in (1), if the input is Gaussian with variance
$\sigma_{X}^{2}$, then the exact rate loss $L_{\mathcal{N}}(D)$ for
$D>D_{\mathcal{N},0}$ can be written as

$\displaystyle L_{\mathcal{N}}(D)$
$\displaystyle=\frac{M-1}{2}\log\left(\frac{D}{\frac{\sigma_{X}^{2}+\sigma_{W}^{2}/M}{\sigma_{X}^{2}}D-\frac{\sigma_{W}^{2}}{M}}\right)$
$\displaystyle=\frac{M-1}{2}\log\frac{1}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}$
(8)

From the expression, several important observations could be made on how the
rate loss scales.

###  II-A Fixed $D$, large $M$

As we expand (8) at $M=\infty$, we obtain

$L_{\mathcal{N}}(D)=L_{\mathcal{N}}^{\infty}(D)+L_{\mathcal{N}}^{\infty}(D)\,\left(L_{\mathcal{N}}^{\infty}(D)-1\right)\frac{1}{M}+O\left(\frac{1}{M^{2}}\right)$
(9)

where
$L_{\mathcal{N}}^{\infty}(D)=\frac{1}{2}\sigma_{W}^{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)$
is the rate loss as $M$ approaches infinity. Hence, for large $M$, the rate
loss is inversely proportional with $D$.

###  II-B $D=\beta\,M^{-\alpha}$ for $0<\alpha\leq 1$, large $M$

We assume $\beta$ is chosen such that $D>D_{\mathcal{N},0}$ (see Eqn. (7)). In
this case, the rate loss is asymptotically equivalent to $\gamma M^{\alpha}$.
That is,

$L_{\mathcal{N}}(D)\sim\gamma M^{\alpha}$ (10)

for large $M$ where

$\gamma=\begin{cases}\frac{\sigma_{W}^{2}}{2\beta}&\text{ if }0<\alpha<1\\\
\frac{1}{2}\log\left(\frac{\beta}{\beta-\sigma_{W}^{2}}\right)&\text{ if
}\alpha=1,\beta\neq\sigma_{W}^{2}\end{cases}.$ (11)

###  II-C Fixed $M$, $D=D_{\mathcal{N},0}+\delta$ for small $\delta$

As we expand (8) around the smallest possible distortion $D_{\mathcal{N},0}$
as given in Eqn. (7), i.e., $\delta=0^{+}$, we obtain

$L_{\mathcal{N}}(\delta)=\frac{1}{2}(M-1)\log\frac{1}{\delta}+\frac{1}{2}(M-1)\log\left(\frac{M\sigma_{W}^{2}\sigma_{X}^{4}}{\left(M\sigma_{x}^{2}+\sigma_{W}^{2}\right){}^{2}}\right)\\\
+\frac{\delta(M-1)\left(M\sigma_{X}^{2}+\sigma_{W}^{2}\right)}{2\sigma_{W}^{2}\sigma_{X}^{2}}+O\left(\delta^{2}\right)$
(12)

Hence, the rate loss scales with $\log\frac{1}{\delta}$. In the next section,
we analyze the same three cases and show that similar scaling behaviours are
observed when the input is non-Gaussian.

##  III Main Results

###  III-A Lower Bounds of the Rate Distortion Function in the Remote Source
Coding Problem

$X^{n}$$W^{n}\sim\mathcal{N}(0,\sigma_{W}^{2}\,I_{n})$$Y^{n}$ENC$+$$nR$DEC$\hat{X}^{n}$
Figure 3: The AWGN remote source coding problem.

An important application of Inequality (6) can be found in the remote source
coding problem. Specifically, consider the source coding problem illustrated
in Figure 3: An encoder observes the underlying source $X$ subject to additive
white Gaussian noise $W.$ The noisy observation is $Y$ and can be encoded
using $R$ bits per sample. The decoder produces a reconstruction $\hat{X}$ to
within the smallest possible mean-squared error. For a formal problem
statement, we refer to [6]. The smallest possible rate to attain a target
distortion $D$ is referred to as the remote rate-distortion function, denoted
as $R_{X}^{R}(D).$ For the case where the underlying source $X$, not
necessarily Gaussian, has finite differential entropy, [6] discusses two
different lower bounds for the remote rate-distortion function, namely

$\displaystyle R_{X}^{R}(D)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log^{+}\frac{N(V)}{D}$ (13)
$\displaystyle{}+\frac{1}{2}\log^{+}\frac{N(Y)}{N(Y)-\frac{N(X)}{D}N(W)}$

and

$\displaystyle R_{X}^{R}(D)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log^{+}\frac{N(X)}{D}$ (14)
$\displaystyle{}+\frac{1}{2}\log^{+}\frac{N(X)}{N(Y)-\frac{N(X)}{D}\sigma_{W}^{2}}$

where $D>\mathsf{E}\left[(X-V)^{2}\right]$ and $\log^{+}x=\max\\{0,\,\log
x\\}$. In [11], it is shown that (13) is a tighter bound than (14). Thus, in
the subsequent sections, we mainly use (13).

###  III-B Novel Rate-Loss Bounds for The CEO Problem

In this section, we apply Theorem 1 to the so-called CEO problem. In this
problem, a single underlying source $X$ is observed by $M$ encoders. Each
encoder receives a noisy version of the source $X,$ denoted as
$Y_{i}=X+W_{i},$ for $i=1,2,\ldots,M.$ In our consideration, the noises
$W_{i}$ are assumed to be zero-mean Gaussian, independent of each other, and
of variance $\sigma_{W}^{2}.$ Each encoder compresses its observation using
$R_{i}$ bits. All $M$ compressed representations are given to a single central
decoder whose goal is to produce a reconstruction of the underlying source $X$
to with mean-squared error $D.$ The smallest possible sum-rate required to
attain a distortion $D$ is denoted by $R_{X}^{\mathrm{CEO}}(D).$ We precisely
follow the exact problem statement and notation used in [6].

The rate loss in the CEO problem denotes the difference between
$R_{X}^{\mathrm{CEO}}(D)$ and the much smaller rate that would be required if
all encoders were to cooperate fully, i.e., the rate required by a single
encoder having access to all $M$ noisy source observations. Evidently, if the
encoders are allowed to cooperate fully, then the problem is exactly the
remote rate-distortion problem discussed in Section III-A above, but with
reduced variance $\sigma_{W}^{2}/M$. We denote the corresponding rate by
$R_{X}^{\mathrm{R}}(D),$ and the rate loss by

$L(D)\triangleq R_{X}^{\mathrm{CEO}}(D)-R_{X}^{\mathrm{R}}(D).$ (15)

In this section, we establish a novel bound on this rate loss.

To develop our results we will use the auxiliary notations

$\displaystyle Y(M)$ $\displaystyle=\frac{1}{M}\sum_{i=1}^{M}Y_{i}$ (16)

and $V(M)=\mathsf{E}\left[X\operatorname*{|}Y(M)\right].$

A lower bound for $L(D)$ is presented in [6]. For

$\displaystyle\sigma_{X}^{2}\dfrac{\nicefrac{{\sigma_{W}^{2}}}{{M}}}{\sigma_{X}^{2}+\nicefrac{{\sigma_{W}^{2}}}{{M}}}<D<N(X)\dfrac{\nicefrac{{\sigma_{W}^{2}}}{{M}}}{N(Y(M))-N(X)},$
(17)

the lower bound on the rate loss establishes that

$L(D)\geq\frac{M}{2}\log\left(\frac{1}{\frac{N(Y(M))}{N(X)}-\frac{\sigma_{W}^{2}}{M}\frac{1}{D}}\right)\\\
-\frac{1}{2}\log\left(\frac{\sigma_{X}^{2}}{N(X)}\,\frac{1}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}\right)$
(18)

For $M\uparrow\infty$ and under some regularity conditions further discussed
in 39, the bound becomes, for $0<D<\frac{1}{J(X)}$

$L(D)\geq\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-{J(X)}\right)-\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(X)}.$
(19)

The novel bound presented here is an upper bound on the rate loss, developed
in the following subsections.

####  III-B1 Cooperation Bound

The first ingredient of the novel upper bound on the rate loss is an improved
lower bound on $R_{X}^{\mathrm{R}}(D).$ To this end, we will utilize both
$N(V(M))$ and $\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)$, i.e., for
all $D>\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)$

$\displaystyle R_{X}^{\mathrm{R}}(D)$
$\displaystyle\geq\frac{1}{2}\log^{+}\frac{N(V(M))}{D-\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)}$
(20)

One can weaken (20) to omit the calculation of
$\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)$. In that case, one obtains
for all $D>N(X)\,\sigma_{W}^{2}/\left(M\,N(Y(M))\right)$,

$\displaystyle R_{X}^{\mathrm{R}}(D)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\log^{+}\frac{N(V(M))}{D}$ (22)
$\displaystyle{}+\frac{1}{2}\log^{+}\frac{M\,N\left(Y(M)\right)}{M\,N\left(Y(M)\right)-\frac{N(X)}{D}N(W)}$

where $Y(M)$ was defined in Equation (16), and
$V(M)=\mathsf{E}\left[X\operatorname*{|}Y(M)\right]$. As we have shown in
Section III-A, this bound is tighter than the other lower bound in [6] for any
finite111Observe that as $M\uparrow\infty$, the second term vanishes, and the
bound becomes $R_{X}^{\mathrm{R}}(D)\geq\frac{1}{2}\log^{+}\frac{N(X)}{D}$ as
expected. This is also true for the other lower bound. $M$.

####  III-B2 Novel Rate Loss Upper Bound

In order to upper bound the rate loss $L(D),$ we utilize the upper bound on
the CEO sum-rate distortion by Eswaran and Gastpar [6], which states that for
$D>D_{\mathcal{N},0}$,

$\displaystyle R_{X}^{\mathrm{CEO}}(D)$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log^{+}\frac{\sigma_{X}^{2}}{D}+\frac{M}{2}\log^{+}\frac{M\,\sigma_{X}^{2}}{M\sigma_{Y(M)}^{2}-\frac{\sigma_{X}^{2}}{D}\sigma_{W}^{2}}$
(23) $\displaystyle=$
$\displaystyle\frac{1}{2}\log^{+}\frac{\sigma_{X}^{2}}{D}+\frac{M}{2}\log^{+}\frac{1}{1+\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{\sigma_{X}^{2}}-\frac{1}{D}\right)}$
(24) $\displaystyle=$
$\displaystyle\begin{cases}\frac{1}{2}\log\frac{\sigma_{X}^{2}}{D}+\frac{M}{2}\log\frac{1}{1+\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{\sigma_{X}^{2}}-\frac{1}{D}\right)}&\small\text{if
}\scriptstyle{D<\sigma_{X}^{2}}\\\ 0&\small\text{otherwise}\end{cases}.$ (25)

One can use (20) to obtain a tight upper bound on the rate loss.

###### Theorem 3

. For
$D_{\mathcal{N},0}<D<\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)+N(V(M))$,
the rate loss is upper bounded as

$\displaystyle L(D)$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(V(M))}+\frac{M}{2}\log\frac{1}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}$
(26)
$\displaystyle{}-\frac{1}{2}\log\left(\frac{D}{D-\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)}\right)$
$\displaystyle=$
$\displaystyle{}\frac{M}{M-1}L_{\mathcal{N}}(D)+\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(V(M))}$
$\displaystyle{}-\frac{1}{2}\log\left(\frac{D}{D-\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)}\right)$

###### Proof.

Follows directly from subtracting (20) from (25). For the regions, observe
that
$\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)+N(V(M))\leq\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)+\sigma_{V(M)}^{2}=\sigma_{X}^{2}$
by law of total variance. ∎

###### Corollary 4

. As $M\uparrow\infty$, the upper bound on the loss becomes

$\displaystyle
L(D)\leq\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(X)}+\frac{1}{2}\sigma_{W}^{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)\text{
for }0<D<N(X)$ (27)

###### Remark 5

. Note that (26) is minimized for Gaussian inputs since both $N(V(M))$ and
$\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)$ is maximized in that case.
Furthermore, the theorem simplifies to

$\displaystyle L(D)$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log\left(1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)\right)$
(28)
$\displaystyle{}+\frac{M}{2}\log\frac{1}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}$
$\displaystyle=$
$\displaystyle\frac{M-1}{2}\log\frac{1}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}$
(29)

for any $D_{\mathcal{N},0}<D<\sigma_{X}^{2}$. Hence, the new upper bound is
tight for Gaussian inputs, irrespective of $M$.

###  III-C Asymptotic Analysis of the Bounds

In this subsection, we provide an analysis similar to Section II.

####  III-C1 Fixed $D$, large $M$

###### Theorem 6

. As the number of agents increases, (26) simplifies to the following.

$\displaystyle L(D)$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\sigma_{W}^{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)+\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(X)}+$
(30)
$\displaystyle{}\frac{\left(\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)\right)^{2}-\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-J(X)\right)}{M}+O\left(\frac{1}{M^{2}}\right)$
$\displaystyle=$ $\displaystyle
L_{\mathcal{N}}^{\infty}(D)+\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(X)}$
$\displaystyle{}+\frac{\left(L_{\mathcal{N}}^{\infty}(D)\right)^{2}-L_{\mathcal{N}}^{\infty}(D)+\frac{\sigma_{W}^{2}}{2}\left(J(X)-\frac{1}{\sigma_{X}^{2}}\right)}{M}$
$\displaystyle{}+O\left(\frac{1}{M^{2}}\right)$

and (18) simplifies to

$\displaystyle L(D)$ $\displaystyle\geq$
$\displaystyle\frac{1}{2}\sigma_{W}^{2}\left(\frac{1}{D}-J(X)\right)-\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(X)}+$
$\displaystyle\frac{\left(\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-J(X)\right)\right)^{2}-\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}{M}+O\left(\frac{1}{M^{2}}\right)$
$\displaystyle=$
$\displaystyle{}L_{\mathcal{N}}^{\infty}(D)-\frac{\sigma_{W}^{2}}{2}\left(J(X)-\frac{1}{\sigma_{X}^{2}}\right)-\frac{1}{2}\log\frac{\sigma_{X}^{2}}{N(X)}+$
$\displaystyle\frac{\left(\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-J(X)\right)\right)^{2}-\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}{M}+O\left(\frac{1}{M^{2}}\right)$

###### Proof.

Both inequalities follow from relaxing the bounds and expanding them at
$M=\infty$. By (6), $N(V(M))\geq\frac{N^{2}(X)}{N(Y(M))}$. We refer to Eqn. 16
in [6] for a lower bound on
$\mathsf{mmse}\left(X\operatorname*{|}Y(M)\right)$, Eqn. 98 for an upper bound
of $N(Y(M))$, and Appendix Acknowledgments for the simplification of the
bound. ∎

####  III-C2 $D=\beta\,M^{-\alpha}$ for $0<\alpha\leq 1$, large $M$

In this case, non-Gaussian inputs are not much different than Gaussian. That
is, the same asymptotic equivalence (10) is observed.

###### Theorem 7

. For arbitrary inputs with finite variance and entropy power, the rate loss
is asymptotically equivalent to $\gamma M^{\alpha}$, i.e.,

$L(D)\sim\gamma M^{\alpha}$ (32)

for large $M$ where

$\gamma=\begin{cases}\frac{\sigma_{W}^{2}}{2\beta}&\text{ if }0<\alpha<1,\\\
\frac{1}{2}\log\left(\frac{\beta}{\beta-\sigma_{W}^{2}}\right)&\text{ if
}\alpha=1,\beta\neq\sigma_{W}^{2}.\end{cases}$ (33)

###### Proof.

The dominating term on the right hand side of (18) is
$-\frac{M}{2}\log\left({\frac{N(Y(M))}{N(X)}-\frac{\sigma_{W}^{2}}{M}\frac{M^{\alpha}}{\beta}}\right)$.
By Eqn. 98 in [6], this can be further relaxed into
$\frac{M}{2}\log\left(1-\frac{\sigma_{W}^{2}}{\beta}M^{\alpha-1}+\sigma_{W}^{2}J(X)M^{-1}\right)$.
Similarly, the dominating term on the right hand side of (26) is
$\frac{M}{2}\log\left(1-\frac{\sigma_{W}^{2}}{\beta}M^{\alpha-1}+\frac{\sigma_{W}^{2}}{\sigma_{X}^{2}}M^{-1}\right)$.
Taking the limit as $M\uparrow\infty$ of both the upper and lower bounds
conclude the proof. ∎

####  III-C3 Fixed $M$, $D=D_{\mathcal{N},0}+\delta$ for small $\delta$

For this case, the upper bound for non-Gaussian inputs exhibits the same
behavior as Gaussian inputs.

###### Theorem 8

. For arbitrary inputs with finite variance and entropy power, as $D$ gets
closer to $D_{\mathcal{N},0}$ by $\delta$,

$\displaystyle L(D)\leq g(\delta)$ (34)

where $g(\delta)\sim\frac{M}{2}\log\frac{1}{\delta}$. That is,

$\lim_{\delta\downarrow
0}\frac{g(\delta)}{\frac{M}{2}\log{\frac{1}{\delta}}}=1$ (35)

###### Proof.

Follows immediately by (12) and (26) as the last two terms on (26) are $O(1)$.
∎

###  III-D Comparison and Numerical Results

We also note that the following upper bound on the rate loss $L(D)$ appears in
[12].

$\displaystyle L(D)$ $\displaystyle\leq$
$\displaystyle\frac{M-1}{2}\log\frac{1}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}$
(36) $\displaystyle{}+\frac{1}{2}\log\left(\scriptstyle
1+\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)\left(\frac{D+2\sqrt{D}\sigma_{W}+\frac{\sigma_{W}^{2}}{M}}{1-\frac{\sigma_{W}^{2}}{M}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)}\right)\right)$

and as $M\uparrow\infty$, we have

$L(D)\leq\frac{\sigma_{W}^{2}}{2}\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)\\\
+\frac{1}{2}\log\left(1+\left(\frac{1}{D}-\frac{1}{\sigma_{X}^{2}}\right)\left(D+2\sqrt{D\sigma_{W}^{2}}\right)\right).$
(37)

Comparing (26) and (36) for any input distributions is tedious. For Gaussian
inputs, it is easy to see that the new bound achieves the exact value while
(36) does not.

For comparing the two bounds in the large $M$ regime, we set
$\sigma_{X}^{2}=1,\sigma_{W}^{2}=1/\text{snr}$ and solve for $D$ such that
(37) is greater than (27), i.e., $D$ for which the new bound is strictly
better. These regions are in the form $D<D^{*}$, and we plot $D^{*}$ vs $N(X)$
in Fig. 4 for different snr values.

Figure 4: Comparison of the bounds (27) and (37): $D^{*}$ vs $N(X).$ The new
bound is valid for $0<D<N(X)$ and is better whenever $D<D^{*}.$ Note that
$D^{*}$ is calculated numerically.

For other distributions such as Laplace and Uniform, we present numerical
results in Fig. 5, and Fig. 6 for $M\uparrow\infty$, and in Fig. 7 for $M=10$.

Figure 5: Comparison of Upper Bounds for
$\sigma_{X}^{2}=\sigma_{W}^{2}=1,M\uparrow\infty$: Previous upper bound refers
to (37), new upper bound refers to (27), and exact rate loss for Gaussian
input refers to $L_{\mathcal{N}}^{\infty}(D)$ in (9). Calculations are done
analytically. Figure 6: Comparison of Bounds for
$\sigma_{X}^{2}=\sigma_{W}^{2}=1,M\uparrow\infty$: Previous upper bound refers
to (37), new upper bound refers to (27), exact rate loss for Gaussian input
refers to $L_{\mathcal{N}}^{\infty}(D)$ in (9), and lower bound refers to
(19). Calculations are done analytically. Figure 7: Comparison of Bounds for
$\sigma_{X}^{2}=\sigma_{W}^{2}=1$, $M=10$: Previous upper bound refers to
(36), new upper bound refers to (26), exact rate loss for Gaussian input
refers to (8), and lower bound refers to (18). Calculations are done
numerically.

###### Remark 9

: It is important to note that the Gaussian input maximizes the lower bound
(18), whereas it minimizes the upper bound (26). Hence, the bounds are tight
for the inputs that are close to the Gaussian distribution in terms of KL-
divergence.

##  IV Conclusion and Outlook

We studied the well known rate loss where the underlying source is arbitrary
but having a finite variance and differential entropy. We explicitly explored
three limiting regimes: the number of users gets larger for fixed $D$, the
number of users gets larger and $D$ is approaching zero with $1/D$ staying
sub-linear, and small $D$ for fixed number of users. Our results indicate that
the arbitrary input case is not so different from the Gaussian input analogue
which is due to [3]. An interesting continuation would be the study of the
worst-case rate loss and its tight bounds.

## Acknowledgments

The work in this manuscript was supported in part by the Swiss National
Science Foundation under Grant 200364.

###### Lemma 10

: Under regularity conditions,

$\displaystyle\kappa_{X}$ $\displaystyle\triangleq\lim_{s\rightarrow
0^{+}}\frac{d}{ds}N(X+\sqrt{s}G)$ (38) $\displaystyle=N(X)\,J(X).$ (39)

###### Proof.

We start by observing that we can express

$\displaystyle\kappa_{X}$ $\displaystyle=\lim_{s\rightarrow
0^{+}}\frac{d}{ds}N(X+\sqrt{s}G)$ (40) $\displaystyle=\lim_{s\rightarrow
0^{+}}2N(X+\sqrt{s}G)\,\frac{d}{ds}h(X+\sqrt{s}G)$ (41)
$\displaystyle=2N(X)\lim_{s\rightarrow 0^{+}}\frac{d}{ds}h(X+\sqrt{s}G)$ (42)
$\displaystyle=2N(X)\,\lim_{s\rightarrow 0^{+}}\frac{1}{2}\,J(X+\sqrt{s}G)$
(43) $\displaystyle=N(X)\,J(X),$ (44)

where we use de Bruijn’s Identity [7, p.672] in the last two lines. ∎

## References

  * [1] T. Berger, Z. Zhang, and H. Viswanathan, “The ceo problem [multiterminal source coding],” _IEEE Transactions on Information Theory_ , vol. 42, no. 3, pp. 887–902, 1996.
  * [2] H. Viswanathan and T. Berger, “The quadratic gaussian ceo problem,” _IEEE Transactions on Information Theory_ , vol. 43, no. 5, pp. 1549–1559, 1997.
  * [3] Y. Oohama, “The rate-distortion function for the quadratic gaussian ceo problem,” _IEEE Transactions on Information Theory_ , vol. 44, no. 3, pp. 1057–1070, 1998.
  * [4] V. Prabhakaran, D. Tse, and K. Ramachandran, “Rate region of the quadratic gaussian ceo problem,” in _International Symposium onInformation Theory, 2004. ISIT 2004. Proceedings._ IEEE, 2004, p. 119.
  * [5] S. Tavildar, P. Viswanath, and A. B. Wagner, “The gaussian many-help-one distributed source coding problem,” _IEEE Transactions on Information Theory_ , vol. 56, no. 1, pp. 564–581, 2009.
  * [6] K. Eswaran and M. Gastpar, “Remote source coding under gaussian noise: Dueling roles of power and entropy power,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 7, pp. 4486–4498, Jul. 2019.
  * [7] T. Cover and J. Thomas, _Elements of Information Theory_ , 2nd ed. John Wiley and Sons, 2006.
  * [8] A. Dytso, H. V. Poor, and S. Shamai, “A general derivative identity for the conditional mean estimator in gaussian noise and some applications,” in _Proc. IEEE Int. Symp. Inf. Theory_ , Los Angeles, CA, USA, Jun. 2020, pp. 1183–1188.
  * [9] H. Robbins, “An empirical Bayes approach to statistics,” in _Proc. Third Berkeley Symp. Math Statist. Probab._ , vol. 1, 1956, pp. 157–163.
  * [10] C. Hatsell and L. Nolte, “Some geometric properties of the likelihood ratio (corresp.),” _IEEE Trans. Inf. Theory_ , vol. 17, no. 5, pp. 616–618, 1971\.
  * [11] A. Atalik, A. Köse, and M. Gastpar, “Differential entropy of the conditional expectation under gaussian noise,” 2021, arxiv:2106.04677.
  * [12] P. L. Dragotti and M. Gastpar, _Distributed source coding: theory, algorithms and applications_. Academic Press, 2009.