# The finite-dimensional Witsenhausen counterexample

Pulkit Grover, Se Yong Park and Anant Sahai
Department of EECS, University of California at Berkeley, CA-94720, USA
{pulkit, sahai<EMAIL_ADDRESS>
###### Abstract

Recently, a vector version of Witsenhausen’s counterexample was considered and
it was shown that in that limit of infinite vector length, certain
quantization-based control strategies are provably within a constant factor of
the optimal cost for all possible problem parameters. In this paper, finite
vector lengths are considered with the dimension being viewed as an additional
problem parameter. By applying a large-deviation “sphere-packing” philosophy,
a lower bound to the optimal cost for the finite dimensional case is derived
that uses appropriate shadows of the infinite-length bound. Using the new
lower bound, we show that good lattice-based control strategies achieve within
a constant factor of the optimal cost uniformly over all possible problem
parameters, including the vector length. For Witsenhausen’s original problem —
the scalar case — the gap between regular lattice-based strategies and the
lower bound is numerically never more than a factor of $8$.

##  I Introduction

Distributed control problems have long proved challenging for control
engineers. In 1968, Witsenhausen [1] gave a counterexample showing that even a
seemingly simple distributed control problem can be hard to solve. For the
counterexample, Witsenhausen chose a two-stage distributed LQG system and
provided a nonlinear control strategy that outperforms all linear laws. It is
now clear that the non-classical information pattern of Witsenhausen’s problem
makes it quite challenging111In words of Yu-Chi Ho [2], “the simplest problem
becomes the hardest problem.”; the optimal strategy and the optimal costs for
the problem are still unknown — non-convexity makes the search for an optimal
strategy hard [3, 4, 5]. Discrete approximations of the problem [6] are even
NP-complete222More precisely, results in [7] imply that the discrete
counterparts to the Witsenhausen counterexample are NP-complete if the
assumption of Gaussianity of the primitive random variables is relaxed.
Further, it is also shown in [7] that with this relaxation, a polynomial time
solution to the original continuous problem would imply $P=NP$, and thus
conceptually the relaxed continuous problem is also hard. [7].

In the absence of a solution, research on the counterexample has bifurcated
into two different directions. Since there is no known systematic approach to
obtain provably optimal solutions, a body of literature (e.g. [4] [5] [8] and
the references therein) applies search heuristics to explore the space of
possible control actions and obtain intuition into the structure of good
strategies. Work in this direction has also yielded considerable insight into
addressing non-convex problems in general.

In the other direction the emphasis is on understanding the role of implicit
communication in the counterexample. In distributed control, control actions
not only attempt to reduce the immediate control costs, they can also
communicate relevant information to other controllers to help them reduce
costs. Witsenhausen [1, Section 6] and Mitter and Sahai [9] aim at developing
systematic constructions based on implicit communication. Witsenhausen’s two-
point quantization strategy is motivated from the optimal strategy for two-
point symmetric distributions of the initial state [1, Section 5] and it
outperforms linear strategies for certain parameter choices. Mitter and Sahai
[9] propose multipoint-quantization strategies that, depending on the problem
parameters, can outperform linear strategies by an arbitrarily-large factor.

Various modifications to the counterexample investigate if misalignment of
these two goals of control and implicit communication makes the problems hard
[3, 10, 11, 12, 13, 14] (see [15] for a survey of other such modifications).
Of particular interest are two works, those of Rotkowitz and Lall [12], and
Rotkowitz [14]. The first work [12] shows that with extremely fast, infinite-
capacity, and perfectly reliable external channels, the optimal controllers
are linear not just for the Witsenhausen’s counterexample (which is a simple
observation), but for more general problems as well. This suggests that
allowing for an external channel between the two controllers in Witsenhausen’s
counterexample might simplify the problem. However, when the channel is not
perfect, Martins [16] shows that finding optimal solutions can be
hard333Martins shows that nonlinear strategies that do not even use the
external channel can outperform linear ones that do use the channel where the
external channel SNR is high. As is suggested by what David Tse calls the
“deterministic perspective” (along the lines of [17, 18, 19]), linear
strategies do not make good use of the external channel because they only
communicate the “most significant bits” — which can anyway be estimated
reliably at the second controller. So if the uncertainty in the initial state
is large, the external channel is only of limited help and there may be
substantial advantage in having the controllers talk through the plant. A
similar problem is considered by Shoarinejad et al in [20], where noisy side
information of the source is available at the receiver. Since this formulation
is even more constrained than that in [16], it is clear that nonlinear
strategies outperform linear for this problem as well.. A closer inspection of
the problem in [16] reveals that nonlinear strategies can outperform linear
ones by an arbitrarily large factor for any fixed SNR on the external channel.
Even to make good use of the external channel resource, one needs nonlinear
strategies.

The second work [14] shows that if one considers the induced norm instead of
the original expected quadratic cost, linear control laws are optimal and easy
to find. The induced norm formulation is therefore easy to solve, and at the
same time, it makes no assumptions on the state and the noise distributions.
This led Doyle to ask if Witsenhausen’s counterexample (with expected
quadratic cost) is at all relevant [21] — after all, not only is the LQG
formulation more constrained, it is also harder to solve. The question thus
becomes what norm is more appropriate, and the answer must come from what is
relevant in practical situations. In practice, one usually knows the “typical”
amplitude of the noise and the initial state, or at least rough bounds them.
The induced-norm formulation may therefore be quite conservative: since no
assumptions are made on the state and the noise, it requires budgeting for
completely arbitrary behavior of state and noise — they can even collude to
raise the costs for the chosen strategy. To see how conservative the induced-
norm formulation can be, notice the following: even allowing for colluding
state and noise, mere knowledge of a bound on the noise amplitude suffices to
have quantization-based nonlinear strategies outperform linear strategies by
an arbitrarily large factor (with the expected cost replaced by a hard-budget.
The proof is simpler than that in [9], and is left as an exercise to the
interested reader for reasons of limited space). Conceptually, the LQG
formulation is only abstracting some knowledge of noise and initial state
behavior. In practical situations where such knowledge exists, designs based
on an induced norm formulation (and linear strategies) may be needlessly
expensive because they budget for impossible events.

The fact that nonlinear strategies can be arbitrarily better brings us to a
question that has received little attention in the literature — how far are
the proposed nonlinear strategies from the optimal? It is believed that the
strategies of Lee, Lau and Ho [5] are close to optimal. In Section VI, we will
see that these strategies can be viewed as an instance of the “dirty-paper
coding” strategy in information theory, and quantify their advantage over pure
quantization based strategies. Despite their improved performance, there was
no guarantee that these strategies are indeed close to optimal444The search in
[5] is not exhaustive. The authors first find a good quantization-based
solution. Inspired by piecewise linear strategies (from the neural networks
based search of Baglietto et al [4]), each quantization step is broken into
several small sub-steps to approximate a piecewise linear curve. .
Witsenhausen [1, Section 7] derived a lower bound on the costs that is loose
in the interesting regimes of small $k$ and large $\sigma_{0}^{2}$ [15, 22],
and hence is insufficient to obtain any guarantee on the gap from optimality.

Towards obtaining such a guarantee, a strategic simplification of the problem
was introduced in [23, 15] where we consider an asymptotically-long vector
version of the problem. This problem is related to a toy communication problem
that we call “Assisted Interference Suppression” (AIS) which is an extension
of the dirty-paper coding (DPC) [24] model in information theory. There has
been a burst of interest in extensions to DPC in information theory mainly
along two lines of work — multi-antenna Gaussian channels, and the “cognitive-
radio channel.” For multi-antenna Gaussian channels, a problem of much
theoretical and practical interest, DPC turns out to be the optimal strategy
(see [25] and the references therein). The “cognitive radio channel” problem
was formulated by Devroye et al [26]. This inspired much work in asymmetric
cooperation between nodes [27, 28, 29, 30, 31]. In our work [15, 23], we
developed a new lower bound to the optimal performance of the vector
Witsenhausen problem. Using this bound, we show that vector-quantization based
strategies attain within a factor of $4.45$ of the optimal cost for all
problem parameters in the limit of infinite vector length. Further,
combinations of linear and DPC-based strategies attain within a factor $2$ of
the optimal cost. This factor was later improved to $1.3$ in [32] by improving
the lower bound. While a constant-factor result does not establish true
optimality, such results are often helpful in the face of intractable problems
like those that are otherwise NP-hard [33]. This constant-factor spirit has
also been useful in understanding other stochastic control problems [34, 35]
and in the asymptotic analysis of problems in multiuser wireless communication
[36, 17].

While the lower bound in [15] holds for all vector lengths, and hence for the
scalar counterexample as well, the ratio of the costs attained by the
strategies of [9] and the lower bound diverges in the limit $k\rightarrow 0$
and $\sigma_{0}\rightarrow\infty$. This suggests that there is a significant
finite-dimensional aspect of the problem that is being lost in the infinite-
dimensional limit: either quantization-based strategies are bad, or the lower
bound of [15] is very loose. This effect is elucidated in [22] by deriving a
different lower bound showing that quantization-based strategies indeed attain
within a constant555The constant is large in [22], but as this paper shows,
this is an artifact of the proof rather than reality. factor of the optimal
cost for Witsenhausen’s original problem. The bound in [22] is in the spirit
of Witsenhausen’s original lower bound, but is more intricate. It captures the
idea that observation noise can force a second-stage cost to be incurred
unless the first stage cost is large.

In this paper, we revert to the line of attack initiated by the vector
simplification of [15]. In Section II, we formally state the vector version of
the counterexample. For obtaining good control strategies, we observe that the
action of the first controller in the quantization-based strategy of [9] can
be thought of as forcing the state to a point on a one-dimensional lattice.
Extending this idea, in Section III, we provide lattice-based quantization
strategies for finite dimensional spaces and analyze their performance.

Building upon the vector lower bound of [15], a new lower bound is derived in
Section IV which is in the spirit of large-deviations-based information-
theoretic bounds for finite-length communication problems666An alternative
Central Limit Theorem (CLT)-based approach has also been used in the
information-theory literature [37, 39, 38]. In [39, 38], the approach is used
to obtain extremely tight approximations at moderate blocklengths for
Shannon’s noisy communication problem. (e.g. [40, 41, 42, 43]). In particular,
our new bound extends the tools in [43] to a setting with unbounded distortion
measure. In Section V, we combine the lattice-based upper bound (Section III)
and the large-deviations lower bound (Section IV) to show that lattice-based
quantization strategies attain within a constant factor of the optimal cost
for any finite length, uniformly over all problem parameters. For example,
this constant factor is numerically found to be smaller than $8$ for the
original scalar problem. We also provide a constant factor that holds
uniformly over all vector lengths.

To understand the significance of the result, consider the following. At
$k=0.01$ and $\sigma_{0}=500$, the cost attained by the optimal linear scheme
is close to $1$. The cost attained by a quantization-based777The quantization
points are regularly spaced about $9.92$ units apart. This results in a first
stage cost of about $8.2\times 10^{-4}$ and a second stage cost of about
$6.7\times 10^{-5}$. scheme is $8.894\times 10^{-4}$. Our new lower bound on
the cost is $3.170\times 10^{-4}$. Despite the small value of the lower bound,
the ratio of the quantization-based upper bound and the lower bound for this
choice of parameters is less than three!

We conclude in Section VI outlining directions of future research and
speculating on the form of finite-dimensional strategies (following [15]) that
we conjecture might be optimal.

##  II Notation and problem statement

Figure 1: Block-diagram for vector version of Witsenhausen’s counterexample of
length $m$.

Vectors are denoted in bold. Upper case tends to be used for random variables,
while lower case symbols represent their realizations.
$W(m,k^{2},\sigma_{0}^{2})$ denotes the vector version of Witsenhausen’s
problem of length $m$, defined as follows (shown in Fig. 1):

  * •

The initial state $\mathbf{X}^{m}_{0}$ is Gaussian, distributed
$\mathcal{N}(0,\sigma_{0}^{2}\mathbb{I}_{m})$, where $\mathbb{I}_{m}$ is the
identity matrix of size $m\times m$.

  * •

The state transition functions describe the state evolution with time. The
state transitions are linear:

$\displaystyle\mathbf{X}^{m}_{1}$ $\displaystyle=$
$\displaystyle\mathbf{X}^{m}_{0}+\mathbf{U}^{m}_{1},\;\;\;\text{and}$
$\displaystyle\mathbf{X}^{m}_{2}$ $\displaystyle=$
$\displaystyle\mathbf{X}^{m}_{1}-\mathbf{U}^{m}_{2}.$

  * •

The outputs observed by the controllers:

$\displaystyle\mathbf{Y}^{m}_{1}$ $\displaystyle=$
$\displaystyle\mathbf{X}^{m}_{0},\;\;\;\text{ and}$
$\displaystyle\mathbf{Y}^{m}_{2}$ $\displaystyle=$
$\displaystyle\mathbf{X}^{m}_{1}+\mathbf{Z}^{m},$ (1)

where $\mathbf{Z}^{m}\sim\mathcal{N}(0,\sigma_{Z}^{2}\mathbb{I}_{m})$ is
Gaussian distributed observation noise.

  * •

The control objective is to minimize the expected cost, averaged over the
random realizations of $\mathbf{X}^{m}_{0}$ and $\mathbf{Z}^{m}$. The total
cost is a quadratic function of the state and the input given by the sum of
two terms:

$\displaystyle J_{1}(\mathbf{x}^{m}_{1},\mathbf{u}^{m}_{1})$ $\displaystyle=$
$\displaystyle\frac{1}{m}k^{2}\|\mathbf{u}^{m}_{1}\|^{2},\;\text{and}$
$\displaystyle J_{2}(\mathbf{x}^{m}_{2},\mathbf{u}^{m}_{2})$ $\displaystyle=$
$\displaystyle\frac{1}{m}\|\mathbf{x}^{m}_{2}\|^{2}$

where $\|\cdot\|$ denotes the usual Euclidean 2-norm. The cost expressions are
normalized by the vector-length $m$ to allow for natural comparisons between
different vector-lengths. A control strategy is denoted by
$\gamma=(\gamma_{1},\gamma_{2})$, where $\gamma_{i}$ is the function that maps
the observation $\mathbf{y}^{m}_{i}$ at $\underline{\underline{\text{C}_{i}}}$
to the control input $\mathbf{u}^{m}_{i}$. For a fixed $\gamma$,
$\mathbf{x}^{m}_{1}=\mathbf{x}^{m}_{0}+\gamma_{1}(\mathbf{x}^{m}_{0})$ is a
function of $\mathbf{x}^{m}_{0}$. Thus the first stage cost can instead be
written as a function
$J_{1}^{(\gamma)}(\mathbf{x}^{m}_{0})=J_{1}(\mathbf{x}^{m}_{0}+\gamma_{1}(\mathbf{x}^{m}_{0}),\gamma_{1}(\mathbf{x}^{m}_{0}))$
and the second stage cost can be written as
$J_{2}^{(\gamma)}(\mathbf{x}^{m}_{0},\mathbf{z}^{m})=J_{2}(\mathbf{x}^{m}_{0}+\gamma_{1}(\mathbf{x}^{m}_{0})-\gamma_{2}(\mathbf{x}^{m}_{0}+\gamma_{1}(\mathbf{x}^{m}_{0})+\mathbf{z}^{m}),\gamma_{2}(\mathbf{x}^{m}_{0}+\gamma_{1}(\mathbf{x}^{m}_{0})+\mathbf{z}^{m}))$.

For given $\gamma$, the expected costs (averaged over $\mathbf{x}^{m}_{0}$ and
$\mathbf{z}^{m}$) are denoted by $\bar{J}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})$
and $\bar{J}_{i}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})$ for $i=1,2$. We define
$\bar{J}^{(\gamma)}_{\min}(m,k^{2},\sigma_{0}^{2})$ as follows

$\bar{J}_{\min}(m,k^{2},\sigma_{0}^{2}):=\inf_{\gamma}\bar{J}^{(\gamma)}(m,k^{2},\sigma_{0}^{2}).$
(2)

We note that for the scalar case of $m=1$, the problem is Witsenhausen’s
original counterexample [1].

Observe that scaling $\sigma_{0}$ and $\sigma_{Z}$ by the same factor
essentially does not change the problem — the solution can also be scaled by
the same factor (with the resulting cost scaling quadratically with it). Thus,
without loss of generality, we assume that the variance of the Gaussian
observation noise is $\sigma_{Z}^{2}=1$ (as is also assumed in [1]). The pdf
of the noise $\mathbf{Z}^{m}$ is denoted by $f_{Z}(\cdot{})$. In our proof
techniques, we also consider a hypothetical observation noise
$\mathbf{Z}^{m}_{G}\sim\mathcal{N}(0,\sigma_{G}^{2})$ with the variance
$\sigma_{G}^{2}\geq 1$. The pdf of this test noise is denoted by
$f_{G}(\cdot{})$. We use $\psi(m,r)$ to denote $\Pr(\|\mathbf{Z}^{m}\|\geq r)$
for $\mathbf{Z}^{m}\sim\mathcal{N}(0,\mathbb{I})$.

Subscripts in expectation expressions denote the random variable being
averaged over (e.g.
$\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\cdot{}}\right]$
denotes averaging over the initial state $\mathbf{X}^{m}_{0}$ and the test
noise $\mathbf{Z}^{m}_{G}$).

##  III Lattice-based quantization strategies

Figure 2: Covering and packing for the 2-dimensional hexagonal lattice. The
packing-covering ratio for this lattice is $\xi=\frac{2}{\sqrt{3}}\approx
1.15$ [44, Appendix C]. The first controller forces the initial state
$\mathbf{x}^{m}_{0}$ to the lattice point nearest to it. The second controller
estimates $\mathbf{\widehat{x}}^{m}_{1}$ to be a lattice point at the centre
of the sphere if it falls in one of the packing spheres. Else it essentially
gives up and estimates $\mathbf{\widehat{x}}^{m}_{1}=\mathbf{y}^{m}_{2}$, the
received output itself. A hexagonal lattice-based scheme would perform better
for the 2-D Witsenhausen problem than the square lattice (of
$\xi=\sqrt{2}\approx 1.41$ [44, Appendix C]) because it has a smaller $\xi$.

Lattice-based quantization strategies are the natural generalizations of
scalar quantization-based strategies [9]. An introduction to lattices can be
found in [45, 46]. Relevant definitions are reviewed below. $\mathcal{B}$
denotes the unit ball in $\mathbb{R}^{m}$.

######  Definition 1 (Lattice)

An $m$-dimensional lattice $\Lambda$ is a set of points in $\mathbb{R}^{m}$
such that if $\mathbf{x}^{m},\mathbf{y}^{m}\in\Lambda$, then
$\mathbf{x}^{m}+\mathbf{y}^{m}\in\Lambda$, and if $\mathbf{x}^{m}\in\Lambda$,
then $-\mathbf{x}^{m}\in\Lambda$.

######  Definition 2 (Packing and packing radius)

Given an $m$-dimensional lattice $\Lambda$ and a radius $r$, the set
$\Lambda+r\mathcal{B}$ is a packing of Euclidean $m$-space if for all points
$\mathbf{x}^{m},\mathbf{y}^{m}\in\Lambda$,
$(\mathbf{x}^{m}+r\mathcal{B})\bigcap(\mathbf{y}^{m}+r\mathcal{B})=\emptyset$.
The packing radius $r_{p}$ is defined as
$r_{p}:=\sup\\{r:\Lambda+r\mathcal{B}\;\text{is a packing}\\}$.

######  Definition 3 (Covering and covering radius)

Given an $m$-dimensional lattice $\Lambda$ and a radius $r$, the set
$\Lambda+r\mathcal{B}$ is a covering of Euclidean $m$-space if
$\mathbb{R}^{m}\subseteq\Lambda+r\mathcal{B}$. The covering radius $r_{c}$ is
defined as $r_{c}:=\inf\\{r:\Lambda+r\mathcal{B}\;\text{is a covering}\\}$.

######  Definition 4 (Packing-covering ratio)

The packing-covering ratio (denoted by $\xi$) of a lattice $\Lambda$ is the
ratio of its covering radius to its packing radius, $\xi=\frac{r_{c}}{r_{p}}$.

Because it creates no ambiguity, we do not include the dimension $m$ and the
choice of lattice $\Lambda$ in the notation of $r_{c}$, $r_{p}$ and $\xi$,
though these quantities depend on $m$ and $\Lambda$.

For a given dimension $m$, a natural control strategy that uses a lattice
$\Lambda$ of covering radius $r_{c}$ and packing radius $r_{p}$ is as follows.
The first controller uses the input $\mathbf{u}^{m}_{1}$ to force the state
$\mathbf{x}^{m}_{0}$ to the lattice point nearest to $\mathbf{x}^{m}_{0}$. The
second controller estimates $\mathbf{x}^{m}_{1}$ to be the lattice point
nearest to $\mathbf{y}^{m}_{2}$. For analytical ease, we instead consider an
inferior strategy where the second controller estimates $\mathbf{x}^{m}_{1}$
to be a lattice point only if the lattice point lies within the sphere of
radius $r_{p}$ around $\mathbf{y}^{m}_{2}$. If no lattice point exists in the
sphere, the second controller estimates $\mathbf{x}^{m}_{1}$ to be
$\mathbf{y}^{m}_{2}$, the received vector itself. The actions
$\gamma_{1}(\cdot{})$ of $\underline{\underline{\text{C}_{1}}}$ and
$\gamma_{2}(\cdot{})$ of $\underline{\underline{\text{C}_{2}}}$ are therefore
given by

$\displaystyle\gamma_{1}(\mathbf{x}^{m}_{0})$ $\displaystyle=$
$\displaystyle-\mathbf{x}^{m}_{0}+\underset{{\mathbf{x}^{m}_{1}}\in\Lambda}{\text{arg
min}}\;\|\mathbf{x}^{m}_{1}-\mathbf{x}^{m}_{0}\|^{2},$
$\displaystyle\gamma_{2}(\mathbf{y}^{m}_{2})$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{cc}\mathbf{\widetilde{x}}^{m}_{1}&\text{if}\;\exists\;\mathbf{\widetilde{x}}^{m}_{1}\in\Lambda\;\text{s.t.}\;\|\mathbf{y}^{m}_{2}-\mathbf{\widetilde{x}}^{m}_{1}\|^{2}<r_{p}^{2}\\\
\mathbf{y}^{m}_{2}&\text{otherwise}\end{array}\right..$

The event where there exists no such
$\mathbf{\widetilde{x}}^{m}_{1}\in\Lambda$ is referred to as decoding failure.
In the following, we denote $\gamma_{2}(\mathbf{y}^{m}_{2})$ by
$\mathbf{\widehat{x}}^{m}_{1}$, the estimate of $\mathbf{x}^{m}_{1}$.

###### Theorem 1

Using a lattice-based strategy (as described above) for
$W(m,k^{2},\sigma_{0}^{2})$ with $r_{c}$ and $r_{p}$ the covering and the
packing radius for the lattice, the total average cost is upper bounded by

$\displaystyle\bar{J}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})\leq\inf_{P\geq
0}k^{2}P+\left(\sqrt{\psi(m+2,r_{p})}+\sqrt{\frac{P}{\xi^{2}}}\sqrt{\psi(m,r_{p})}\right)^{2},$

where $\xi=\frac{r_{c}}{r_{p}}$ is the packing-covering ratio for the lattice,
and $\psi(m,r)=\Pr(\|\mathbf{Z}^{m}\|\geq r)$. The following looser bound also
holds

$\displaystyle\bar{J}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})\leq\inf_{P>\xi^{2}}k^{2}P+\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)^{2}e^{-\frac{mP}{2\xi^{2}}+\frac{m+2}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)}.$

Remark: The latter loose bound is useful for analytical manipulations when
proving explicit bounds on the ratio of the upper and lower bounds in Section
V.

###### Proof:

Note that because $\Lambda$ has a covering radius of $r_{c}$,
$\|\mathbf{x}^{m}_{1}-\mathbf{x}^{m}_{0}\|^{2}\leq r_{c}^{2}$. Thus the first
stage cost is bounded above by $\frac{1}{m}k^{2}r_{c}^{2}$. A tighter bound
can be provided for a specific lattice and finite $m$ (for example, for $m=1$,
the first stage cost is approximately $k^{2}\frac{r_{c}^{2}}{3}$ if
$r_{c}^{2}\ll\sigma_{0}^{2}$ because the distribution of $\mathbf{x}^{m}_{0}$
conditioned on it lying in any of the quantization bins is approximately
uniform at least for the most likely bins).

For the second stage, observe that

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{1},\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}}\right]=\mathbb{E}_{\mathbf{X}^{m}_{1}}\left[{\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{X}^{m}_{1}}\right]}\right].$
(4)

Denote by $\mathcal{E}_{m}$ the event $\\{\|\mathbf{Z}^{m}\|^{2}\geq
r_{p}^{2}\\}$. Observe that under the event $\mathcal{E}_{m}^{c}$,
$\mathbf{\widehat{X}}^{m}_{1}=\mathbf{X}^{m}_{1}$, resulting in a zero second-
stage cost. Thus,

$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{X}^{m}_{1}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}|\mathbf{X}^{m}_{1}}\right]+\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}^{c}\right\\}}|\mathbf{X}^{m}_{1}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}|\mathbf{X}^{m}_{1}}\right].$

We now bound the squared-error under the error event $\mathcal{E}_{m}$, when
either $\mathbf{x}^{m}_{1}$ is decoded erroneously, or there is a decoding
failure. If $\mathbf{x}^{m}_{1}$ is decoded erroneously to a lattice point
$\mathbf{\widetilde{x}}^{m}_{1}\neq\mathbf{x}^{m}_{1}$, the squared-error can
be bounded as follows

$\displaystyle\|\mathbf{x}^{m}_{1}-\mathbf{\widetilde{x}}^{m}_{1}\|^{2}=\|\mathbf{x}^{m}_{1}-\mathbf{y}^{m}_{2}+\mathbf{y}^{m}_{2}-\mathbf{\widetilde{x}}^{m}_{1}\|^{2}\leq\left(\|\mathbf{x}^{m}_{1}-\mathbf{y}^{m}_{2}\|+\|\mathbf{y}^{m}_{2}-\mathbf{\widetilde{x}}^{m}_{1}\|\right)^{2}\leq\left(\|\mathbf{z}^{m}\|+r_{p}\right)^{2}.$

If $\mathbf{x}^{m}_{1}$ is decoded as $\mathbf{y}^{m}_{2}$, the squared-error
is simply $\|\mathbf{z}^{m}\|^{2}$, which we also upper bound by
$\left(\|\mathbf{z}^{m}\|+r_{p}\right)^{2}$. Thus, under event
$\mathcal{E}_{m}$, the squared error
$\|\mathbf{x}^{m}_{1}-\mathbf{\widehat{x}}^{m}_{1}\|^{2}$ is bounded above by
$\left(\|\mathbf{z}^{m}\|+r_{p}\right)^{2}$, and hence

$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{X}^{m}_{1}}\right]$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}|\mathbf{X}^{m}_{1}}\right]$
(5) $\displaystyle\overset{(a)}{=}$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right],$

where $(a)$ uses the fact that the pair
$(\mathbf{Z}^{m},{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}})$ is independent of
$\mathbf{X}^{m}_{1}$. Now, let $P=\frac{r_{c}^{2}}{m}$, so that the first
stage cost is at most $k^{2}P$. The following lemma helps us derive the upper
bound.

###### Lemma 1

For a given lattice with
$r_{p}^{2}=\frac{r_{c}^{2}}{\xi^{2}}=\frac{mP}{\xi^{2}}$, the following bound
holds

$\displaystyle\frac{1}{m}\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]\leq\left(\sqrt{\psi(m+2,r_{p})}+\sqrt{\frac{P}{\xi^{2}}}\sqrt{\psi(m,r_{p})}\right)^{2}.$

The following (looser) bound also holds as long as $P>\xi^{2}$,

$\displaystyle\frac{1}{m}\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]\leq\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)^{2}e^{-\frac{mP}{2\xi^{2}}+\frac{m+2}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)}.$

###### Proof:

See Appendix A. ∎

The theorem now follows from (4), (5) and Lemma 1. ∎

##  IV Lower bounds on the cost

Figure 3: A pictorial representation of the proof for the lower bound assuming
$\sigma_{0}^{2}=30$. The solid curves show the vector lower bound of [15] for
various values of observation noise variances, denoted by $\sigma_{G}^{2}$.
Conceptually, multiplying these curves by the probability of that channel
behavior yields the shadow curves for the particular $\sigma_{G}^{2}$, shown
by dashed curves. The scalar lower bound is then obtained by taking the
maximum of these shadow curves. The circles at points along the scalar bound
curve indicate the optimizing value of $\sigma_{G}$ for obtaining that point
on the bound.

Bansal and Basar [3] use information-theoretic techniques related to rate-
distortion and channel capacity to show the optimality of linear strategies in
a modified version of Witsenhausen’s counterexample where the cost function
does not contain a product of two decision variables. Following the same
spirit, in [15] we derive the following lower bound for Witsenhausen’s
counterexample itself.

###### Theorem 2

For $W(m,k^{2},\sigma_{0}^{2})$, if for a strategy $\gamma(\cdot{})$ the
average power
$\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{U}^{m}_{1}\|^{2}}\right]=P$,
the following lower bound holds on the second stage cost

$\bar{J}_{2}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})\geq\left(\left(\sqrt{\kappa(P,\sigma_{0}^{2})}-\sqrt{P}\right)^{+}\right)^{2},$

where $(\cdot{})^{+}$ is shorthand for $\max(\cdot{},0)$ and

$\kappa(P,\sigma_{0}^{2})=\frac{\sigma_{0}^{2}}{\sigma_{0}^{2}+P+2\sigma_{0}\sqrt{P}+1}.$
(6)

The following lower bound thus holds on the total cost

$\bar{J}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})\geq\inf_{P\geq
0}k^{2}P+\left(\left(\sqrt{\kappa(P,\sigma_{0}^{2})}-\sqrt{P}\right)^{+}\right)^{2}.$

###### Proof:

We refer the reader to [15] for the full proof. We outline it here because
these ideas are used in the derivation of the new lower bound in Theorem 3.

Using a triangle inequality argument, we show

$\displaystyle\sqrt{\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}}\right]}\leq\sqrt{\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{X}^{m}_{1}\|^{2}}\right]}+\sqrt{\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}}\right]}.$
(7)

The first term on the RHS is $\sqrt{P}$. It therefore suffices to lower bound
the term on the LHS to obtain a lower bound on
$\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}}\right]$.
To that end, we interpret $\mathbf{\widehat{X}}^{m}_{1}$ as an estimate for
$\mathbf{X}^{m}_{0}$, which is a problem of transmitting a source across a
channel. For an iid Gaussian source to be transmitted across a memoryless
power-constrained additive-noise Gaussian channel (with one channel use per
source symbol), the optimal strategy that minimizes the mean-square error is
merely scaling the source symbol so that the average power constraint is met
[47]. The estimation at the second controller is then merely the linear MMSE
estimation of $\mathbf{X}^{m}_{0}$, and the obtained MMSE is
$\kappa(P,\sigma_{0}^{2})$. The lemma now follows from (7). ∎

Observe that the lower bound expression is the same for all vector lengths. In
the following, large-deviation arguments [48, 49] (called sphere-packing style
arguments for historical reasons) are extended following [41, 42, 43] to a
joint source-channel setting where the distortion measure is unbounded. The
obtained bounds are tighter than those in Theorem 2 and depend explicitly on
the vector length $m$.

###### Theorem 3

For $W(m,k^{2},\sigma_{0}^{2})$, if for a strategy $\gamma(\cdot{})$ the
average power
$\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{U}^{m}_{1}\|^{2}}\right]=P$,
the following lower bound holds on the second stage cost for any choice of
$\sigma_{G}^{2}\geq 1$ and $L>0$

$\bar{J}_{2}^{(\gamma)}(m,k^{2},\sigma_{0}^{2})\geq\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L).$

where

$\displaystyle\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)=\frac{\sigma_{G}^{m}}{c_{m}(L)}\exp\left(-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}\right)\left(\left(\sqrt{\kappa_{2}(P,\sigma_{0}^{2},\sigma_{G}^{2},L)}-\sqrt{P}\right)^{+}\right)^{2},$

where $\kappa_{2}(P,\sigma_{0}^{2},\sigma_{G}^{2},L):=$

$\displaystyle\frac{\sigma_{0}^{2}\sigma_{G}^{2}}{c_{m}^{\frac{2}{m}}(L)e^{1-d_{m}(L)}\left((\sigma_{0}+\sqrt{P})^{2}+d_{m}(L)\sigma_{G}^{2}\right)},$

$c_{m}(L):=\frac{1}{\Pr(\|\mathbf{Z}^{m}\|^{2}\leq
mL^{2})}=\left(1-\psi(m,L\sqrt{m})\right)^{-1}$,
$d_{m}(L):=\frac{\Pr(\|\mathbf{Z}^{m+2}\|^{2}\leq
mL^{2})}{\Pr(\|\mathbf{Z}^{m}\|^{2}\leq
mL^{2})}=\frac{1-\psi(m+2,L\sqrt{m})}{1-\psi(m,L\sqrt{m})}$,
$0<d_{m}(L)<1$, and $\psi(m,r)=\Pr(\|\mathbf{Z}^{m}\|\geq r)$. Thus the
following lower bound holds on the total cost

$\bar{J}_{\min}(m,k^{2},\sigma_{0}^{2})\geq\inf_{P\geq
0}k^{2}P+\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L),$ (8)

for any choice of $\sigma_{G}^{2}\geq 1$ and $L>0$ (the choice can depend on
$P$). Further, these bounds are at least as tight as those of Theorem 2 for
all values of $k$ and $\sigma_{0}^{2}$.

###### Proof:

From Theorem 2, for a given $P$, a lower bound on the average second stage
cost is $\left(\left(\sqrt{\kappa}-\sqrt{P}\right)^{+}\right)^{2}$. We derive
another lower bound that is equal to the expression for
$\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)$. The high-level intuition behind
this lower bound is presented in Fig. 3.

Define $\mathcal{S}_{L}^{G}:=\\{\mathbf{z}^{m}:\|\mathbf{z}^{m}\|^{2}\leq
mL^{2}\sigma_{G}^{2}\\}$ and use subscripts to denote which probability model
is being used for the second stage observation noise. $Z$ denotes white
Gaussian of variance $1$ while $G$ denotes white Gaussian of variance
$\sigma_{G}^{2}\geq 1$.

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m})}\right]$
$\displaystyle=$
$\displaystyle\int_{\mathbf{z}^{m}}\int_{\mathbf{x}^{m}_{0}}J_{2}^{(\gamma)}(\mathbf{x}^{m}_{0},\mathbf{z}^{m})f_{0}(\mathbf{x}^{m}_{0})f_{Z}(\mathbf{z}^{m})d\mathbf{x}^{m}_{0}d\mathbf{z}^{m}$
(9) $\displaystyle\geq$
$\displaystyle\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}\left(\int_{\mathbf{x}^{m}_{0}}J_{2}^{(\gamma)}(\mathbf{x}^{m}_{0},\mathbf{z}^{m})f_{0}(\mathbf{x}^{m}_{0})d\mathbf{x}^{m}_{0}\right)f_{Z}(\mathbf{z}^{m})d\mathbf{z}^{m}$
$\displaystyle=$
$\displaystyle\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}\left(\int_{\mathbf{x}^{m}_{0}}J_{2}^{(\gamma)}(\mathbf{x}^{m}_{0},\mathbf{z}^{m})f_{0}(\mathbf{x}^{m}_{0})d\mathbf{x}^{m}_{0}\right)\frac{f_{Z}(\mathbf{z}^{m})}{f_{G}(\mathbf{z}^{m})}f_{G}(\mathbf{z}^{m})d\mathbf{z}^{m}.$

The ratio of the two probability density functions is given by

$\displaystyle\frac{f_{Z}(\mathbf{z}^{m})}{f_{G}(\mathbf{z}^{m})}=\frac{e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2}}}{\left(\sqrt{2\pi}\right)^{m}}\frac{\left(\sqrt{2\pi\sigma_{G}^{2}}\right)^{m}}{e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2\sigma_{G}^{2}}}}=\sigma_{G}^{m}e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2}\left(1-\frac{1}{\sigma_{G}^{2}}\right)}.$

Observe that $\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}$,
$\|\mathbf{z}^{m}\|^{2}\leq mL^{2}\sigma_{G}^{2}$. Using $\sigma_{G}^{2}\geq
1$, we obtain

$\frac{f_{Z}(\mathbf{z}^{m})}{f_{G}(\mathbf{z}^{m})}\geq\sigma_{G}^{m}e^{-\frac{mL^{2}\sigma_{G}^{2}}{2}\left(1-\frac{1}{\sigma_{G}^{2}}\right)}=\sigma_{G}^{m}e^{-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}}.$
(10)

Using (9) and (10),

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m})}\right]$
$\displaystyle\geq$
$\displaystyle\sigma_{G}^{m}e^{-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}}\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}\left(\int_{\mathbf{x}^{m}_{0}}J_{2}^{(\gamma)}(\mathbf{x}^{m}_{0},\mathbf{z}^{m})f_{0}(\mathbf{x}^{m}_{0})d\mathbf{x}^{m}_{0}\right)f_{G}(\mathbf{z}^{m})d\mathbf{z}^{m}$
(11) $\displaystyle=$
$\displaystyle\sigma_{G}^{m}e^{-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}){1{1}}_{\left\\{\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}\right\\}}}\right]$
$\displaystyle=$
$\displaystyle\sigma_{G}^{m}e^{-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G})|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]\Pr(\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}).$

Analyzing the probability term in (11),

$\displaystyle\Pr(\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G})$ $\displaystyle=$
$\displaystyle\Pr\left(\|\mathbf{Z}^{m}_{G}\|^{2}\leq
mL^{2}\sigma_{G}^{2}\right)=\Pr\left(\left(\frac{\|\mathbf{Z}^{m}_{G}\|}{\sigma_{G}}\right)^{2}\leq
mL^{2}\right)$ (12) $\displaystyle=$ $\displaystyle
1-\Pr\left(\left(\frac{\|\mathbf{Z}^{m}_{G}\|}{\sigma_{G}}\right)^{2}>mL^{2}\right)=1-\psi(m,L\sqrt{m})=\frac{1}{c_{m}(L)},$

because
$\frac{\mathbf{Z}^{m}_{G}}{\sigma_{G}}\sim\mathcal{N}(0,\mathbb{I}_{m})$. From
(11) and (12),

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m})}\right]$
$\displaystyle\geq$
$\displaystyle\sigma_{G}^{m}e^{-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G})|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right](1-\psi(m,L\sqrt{m}))$
(13) $\displaystyle=$
$\displaystyle\frac{\sigma_{G}^{m}e^{-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}}}{c_{m}(L)}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G})|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right].$

We now need the following lemma, which connects the new finite-length lower
bound to the infinite-length lower bound of [15].

###### Lemma 2

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G})|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]\geq\left(\left(\sqrt{\kappa_{2}(P,\sigma_{0}^{2},\sigma_{G}^{2},L)}-\sqrt{P}\right)^{+}\right)^{2},$

for any $L>0$.

###### Proof:

See Appendix B. ∎

The lower bound on the total average cost now follows from (13) and Lemma 2.

We now verify that $d_{m}(L)\in(0,1)$. That $d_{m}(L)>0$ is clear from
definition. $d_{m}(L)<1$ because
$\\{\mathbf{z}^{m+2}:\|\mathbf{z}^{m+2}\|^{2}\leq
mL^{2}\sigma_{G}^{2}\\}\subset\\{\mathbf{z}^{m+2}:\|\mathbf{z}^{m}\|^{2}\leq
mL^{2}\sigma_{G}^{2}\\}$, _i.e._ , a sphere sits inside a cylinder.

Finally we verify that this new lower bound is at least as tight as the one in
Theorem 2. Choosing $\sigma_{G}^{2}=1$ in the expression for
$\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)$,

$\displaystyle\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)\geq\sup_{L>0}\frac{1}{c_{m}(L)}\left(\left(\sqrt{\kappa_{2}(P,\sigma_{0}^{2},1,L)}-\sqrt{P}\right)^{+}\right)^{2}.$

Now notice that $c_{m}(L)$ and $d_{m}(L)$ converge to $1$ as
$L\rightarrow\infty$. Thus
$\kappa_{2}(P,\sigma_{0}^{2},1,L)\overset{L\rightarrow\infty}{\longrightarrow}\kappa(P,\sigma_{0}^{2})$
and therefore, $\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)$ is lower bounded by
$\left(\left(\sqrt{\kappa}-\sqrt{P}\right)^{+}\right)^{2}$, the lower bound in
Theorem 2.

∎

##  V Combination of linear and lattice-based strategies attain within a
constant factor of the optimal cost

######  Theorem 4 (Constant-factor optimality)

The costs for $W(m,k^{2},\sigma_{0}^{2})$ are bounded as follows

$\displaystyle\inf_{P\geq 0}\sup_{\sigma_{G}^{2}\geq
1,L>0}k^{2}P+\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)\leq\bar{J}_{min}(m,k^{2},\sigma_{0}^{2})\leq\mu\left(\inf_{P\geq
0}\sup_{\sigma_{G}^{2}\geq
1,L>0}k^{2}P+\eta(P,\sigma_{0}^{2},\sigma_{G}^{2},L)\right),$

where $\mu=100\xi^{2}$, $\xi$ is the packing-covering ratio of any lattice in
$\mathbb{R}^{m}$, and $\eta(\cdot)$ is as defined in Theorem 3. For any $m$,
$\mu<1600$. Further, depending on the $(m,k^{2},\sigma_{0}^{2})$ values, the
upper bound can be attained by lattice-based quantization strategies or linear
strategies. For $m=1$, a numerical calculation (MATLAB code available at [50])
shows that $\mu<8$ (see Fig. 5).

###### Proof:

Figure 4: The ratio of the upper and the lower bounds for the scalar
Witsenhausen problem (top), and the 2-D Witsenhausen problem (bottom, using
hexagonal lattice of $\xi=\frac{2}{\sqrt{3}}$) for a range of values of $k$
and $\sigma_{0}$. The ratio is bounded above by $17$ for the scalar problem,
and by $14.75$ for the 2-D problem. Figure 5: An exact calculation of the
first and second stage costs yields an improved maximum ratio smaller than $8$
for the scalar Witsenhausen problem.

Let $P^{*}$ denote the power $P$ in the lower bound in Theorem 3. We show here
that for any choice of $P^{*}$, the ratio of the upper and the lower bound is
bounded.

Consider the two simple linear strategies of zero-forcing
($\mathbf{u}^{m}_{1}=-\mathbf{x}^{m}_{0}$) and zero-input
($\mathbf{u}^{m}_{1}=0$) followed by LLSE estimation at
$\underline{\underline{\text{C}_{2}}}$. It is easy to see [15] that the
average cost attained using these two strategies is $k^{2}\sigma_{0}^{2}$ and
$\frac{\sigma_{0}^{2}}{\sigma_{0}^{2}+1}<1$ respectively. An upper bound is
obtained using the best amongst the two linear strategies and the lattice-
based quantization strategy.

Case 1: $P^{*}\geq\frac{\sigma_{0}^{2}}{100}$.
The first stage cost is larger than $k^{2}\frac{\sigma_{0}^{2}}{100}$.
Consider the upper bound of $k^{2}\sigma_{0}^{2}$ obtained by zero-forcing.
The ratio of the upper bound and the lower bound is no larger than $100$.

Case 2: $P^{*}<\frac{\sigma_{0}^{2}}{100}$ and $\sigma_{0}^{2}<16$.
Using the bound from Theorem 2 (which is a special case of the bound in
Theorem 3),

$\displaystyle\kappa$ $\displaystyle=$
$\displaystyle\frac{\sigma_{0}^{2}}{(\sigma_{0}+\sqrt{P^{*}})^{2}+1}\overset{\left(P^{*}<\frac{\sigma_{0}^{2}}{100}\right)}{\geq}\frac{\sigma_{0}^{2}}{\sigma_{0}^{2}\left(1+\frac{1}{\sqrt{100}}\right)^{2}+1}$
$\displaystyle\overset{(\sigma_{0}^{2}<16)}{\geq}$
$\displaystyle\frac{\sigma_{0}^{2}}{16\left(1+\frac{1}{\sqrt{100}}\right)^{2}+1}=\frac{\sigma_{0}^{2}}{20.36}\geq\frac{\sigma_{0}^{2}}{21}.$

Thus, for $\sigma_{0}^{2}<16$ and $P^{*}\leq\frac{\sigma_{0}^{2}}{100}$,

$\displaystyle\bar{J}_{min}$ $\displaystyle\geq$
$\displaystyle\left((\sqrt{\kappa}-\sqrt{P^{*}})^{+}\right)^{2}\geq\sigma_{0}^{2}\left(\frac{1}{\sqrt{21}}-\frac{1}{\sqrt{100}}\right)^{2}\approx
0.014\sigma_{0}^{2}\geq\frac{\sigma_{0}^{2}}{72}.$

Using the zero-input upper bound of $\frac{\sigma_{0}^{2}}{\sigma_{0}^{2}+1}$,
the ratio of the upper and lower bounds is at most
$\frac{72}{\sigma_{0}^{2}+1}\leq 72$.

Case 3: $P^{*}\leq\frac{\sigma_{0}^{2}}{100},\sigma_{0}^{2}\geq
16,P^{*}\leq\frac{1}{2}$.
In this case,

$\displaystyle\kappa$ $\displaystyle=$
$\displaystyle\frac{\sigma_{0}^{2}}{(\sigma_{0}+\sqrt{P^{*}})^{2}+1}\overset{(P^{*}\leq\frac{1}{2})}{\geq}\frac{\sigma_{0}^{2}}{(\sigma_{0}+\sqrt{0.5})^{2}+1}$
$\displaystyle\overset{(a)}{\geq}$
$\displaystyle\frac{16}{(\sqrt{16}+\sqrt{0.5})^{2}+1}\approx 0.6909\geq 0.69,$

where $(a)$ uses $\sigma_{0}^{2}\geq 16$ and the observation that
$\frac{x^{2}}{(x+b)^{2}+1}=\frac{1}{\left(1+\frac{b}{x}\right)^{2}+\frac{1}{x^{2}}}$
is an increasing function of $x$ for $x,b>0$. Thus,

$\displaystyle\left((\sqrt{\kappa}-\sqrt{P})^{+}\right)^{2}\geq((\sqrt{0.69}-\sqrt{0.5})^{+})^{2}\approx
0.0153\geq 0.015.$

Using the upper bound of $\frac{\sigma_{0}^{2}}{\sigma_{0}^{2}+1}<1$, the
ratio of the upper and the lower bounds is smaller than $\frac{1}{0.015}<67$.

Case 4: $\sigma_{0}^{2}>16$, $\frac{1}{2}<P^{*}\leq\frac{\sigma_{0}^{2}}{100}$

Using $L=2$ in the lower bound,

$\displaystyle c_{m}(L)$ $\displaystyle=$
$\displaystyle\frac{1}{\Pr(\|\mathbf{Z}^{m}\|^{2}\leq
mL^{2})}=\frac{1}{1-\Pr(\|\mathbf{Z}^{m}\|^{2}>mL^{2})}$
$\displaystyle\overset{\text{(Markov's ineq.)}}{\leq}$
$\displaystyle\frac{1}{1-\frac{m}{mL^{2}}}\overset{(L=2)}{=}\frac{4}{3},$

Similarly,

$\displaystyle d_{m}(2)$ $\displaystyle=$
$\displaystyle\frac{\Pr(\|\mathbf{Z}^{m+2}\|^{2}\leq
mL^{2})}{\Pr(\|\mathbf{Z}^{m}\|^{2}\leq mL^{2})}$ $\displaystyle\geq$
$\displaystyle\Pr(\|\mathbf{Z}^{m+2}\|^{2}\leq
mL^{2})=1-\Pr(\|\mathbf{Z}^{m+2}\|^{2}>mL^{2})$
$\displaystyle\overset{\text{(Markov's ineq.)}}{\geq}$ $\displaystyle
1-\frac{m+2}{mL^{2}}=1-\frac{1+\frac{2}{m}}{4}\overset{(m\geq
1)}{\geq}1-\frac{3}{4}=\frac{1}{4}.$

In the bound, we are free to use any $\sigma_{G}^{2}\geq 1$. Using
$\sigma_{G}^{2}=6P^{*}>1$,

$\displaystyle\kappa_{2}$ $\displaystyle=$
$\displaystyle\frac{\sigma_{G}^{2}\sigma_{0}^{2}}{\left((\sigma_{0}+\sqrt{P^{*}})^{2}+d_{m}(2)\sigma_{G}^{2}\right)c_{m}^{\frac{2}{m}}(2)e^{1-d_{m}(2)}}$
$\displaystyle\overset{(a)}{\geq}$
$\displaystyle\frac{6P^{*}\sigma_{0}^{2}}{\left((\sigma_{0}+\frac{\sigma_{0}}{10})^{2}+\frac{6\sigma_{0}^{2}}{100}\right)\left(\frac{4}{3}\right)^{\frac{2}{m}}e^{\frac{3}{4}}}\overset{(m\geq
1)}{\geq}1.255P^{*}.$

where $(a)$ uses
$\sigma_{G}^{2}=6P^{*},P^{*}<\frac{\sigma_{0}^{2}}{100},c_{m}(2)\leq\frac{4}{3}$
and $1>d_{m}(2)\geq\frac{1}{4}$. Thus,

$\left((\sqrt{\kappa_{2}}-\sqrt{P^{*}})^{+}\right)^{2}\geq
P^{*}(\sqrt{1.255}-1)^{2}\geq\frac{P^{*}}{70}.$ (14)

Now, using the lower bound on the total cost from Theorem 3, and substituting
$L=2$,

$\displaystyle\bar{J}_{min}(m,k^{2},\sigma_{0}^{2})$ $\displaystyle\geq$
$\displaystyle
k^{2}P^{*}+\frac{\sigma_{G}^{m}}{c_{m}(2)}\exp\left(-\frac{mL^{2}(\sigma_{G}^{2}-1)}{2}\right)\left(\left(\sqrt{\kappa_{2}}-\sqrt{P^{*}}\right)^{+}\right)^{2}$
(15) $\displaystyle\overset{(\sigma_{G}^{2}=6P^{*})}{\geq}$ $\displaystyle
k^{2}P^{*}+\frac{(6P^{*})^{m}}{c_{m}(2)}\exp\left(-\frac{4m(6P^{*}-1)}{2}\right)\;\frac{P^{*}}{70}$
$\displaystyle\overset{(a)}{\geq}$ $\displaystyle
k^{2}P^{*}+\frac{3^{m}}{\frac{4}{3}}e^{2m}e^{-12P^{*}m}\;\frac{1}{70\times 2}$
$\displaystyle\overset{(m\geq 1)}{\geq}$ $\displaystyle
k^{2}P^{*}+\frac{3\times 3\times e^{2}}{4\times 70\times 2}e^{-12mP^{*}}$
$\displaystyle>$ $\displaystyle k^{2}P^{*}+\frac{1}{9}e^{-12mP^{*}},$

where $(a)$ uses $c_{m}(2)\leq\frac{4}{3}$ and $P^{*}\geq\frac{1}{2}$. We
loosen the lattice-based upper bound from Theorem 1 and bring it into a form
similar to (15). Here, $P$ is a part of the optimization:

$\displaystyle\bar{J}_{min}(m,k^{2},\sigma_{0}^{2})$ (16) $\displaystyle\leq$
$\displaystyle\inf_{P>\xi^{2}}k^{2}P+\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)^{2}e^{-\frac{mP}{2\xi^{2}}+\frac{m+2}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)}$
$\displaystyle\leq$
$\displaystyle\inf_{P>\xi^{2}}k^{2}P+\frac{1}{9}e^{-\frac{0.5mP}{\xi^{2}}+\frac{m+2}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)+2\ln\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)+\ln\left(9\right)}$
$\displaystyle\leq$
$\displaystyle\inf_{P>\xi^{2}}k^{2}P+\frac{1}{9}e^{-m\left(\frac{0.5P}{\xi^{2}}-\frac{m+2}{2m}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)-\frac{2}{m}\ln\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)-\frac{\ln\left(9\right)}{m}\right)}$
$\displaystyle=$
$\displaystyle\inf_{P>\xi^{2}}k^{2}P+\frac{1}{9}e^{-\frac{0.12mP}{\xi^{2}}}\times
e^{-m\left(\frac{0.38P}{\xi^{2}}-\frac{1+\frac{2}{m}}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)-\frac{2}{m}\ln\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)-\frac{\ln\left(9\right)}{m}\right)}$
$\displaystyle\overset{(m\geq 1)}{\leq}$
$\displaystyle\inf_{P>\xi^{2}}k^{2}P+\frac{1}{9}e^{-\frac{0.12mP}{\xi^{2}}}e^{-m\left(\frac{0.38P}{\xi^{2}}-\frac{3}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)-2\ln\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)-\ln\left(9\right)\right)}$
$\displaystyle\leq$ $\displaystyle\inf_{P\geq
34\xi^{2}}k^{2}P+\frac{1}{9}e^{-\frac{0.12mP}{\xi^{2}}},$

where the last inequality follows from the fact that
$\frac{0.38P}{\xi^{2}}>\frac{3}{2}\left(1+\ln\left(\frac{P}{\xi^{2}}\right)\right)+2\ln\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)+\ln\left(9\right)$
for $\frac{P}{\xi^{2}}>34$. This can be checked easily by plotting it.888It
can also be verified symbolically by examining the expression
$g(b)=0.38b^{2}-\frac{3}{2}(1+\ln b^{2})-2\ln(1+b)-\ln\left(9\right)$, taking
its derivative $g^{\prime}(b)=0.76b-\frac{3}{b}-\frac{2}{1+b}$, and second
derivative $g^{\prime\prime}(b)=0.76+\frac{3}{b^{2}}+\frac{2}{(1+b)^{2}}>0$.
Thus $g(\cdot{})$ is convex-$\cup$. Further, $g^{\prime}(\sqrt{34})\approx
3.62>0$, and $g(\sqrt{34})\approx 0.09$ and so $g(b)>0$ whenever
$b\geq\sqrt{34}$.

Using $P=100\xi^{2}P^{*}\geq 50\xi^{2}>34\xi^{2}$ (since
$P^{*}\geq\frac{1}{2}$) in (16),

$\displaystyle\bar{J}_{min}(m,k^{2},\sigma_{0}^{2})$ $\displaystyle\leq$
$\displaystyle k^{2}100\xi^{2}P^{*}+\frac{1}{9}e^{-m\frac{0.12\times
100\xi^{2}P^{*}}{\xi^{2}}}$ (17) $\displaystyle=$ $\displaystyle
k^{2}100\xi^{2}P^{*}+\frac{1}{9}e^{-12mP^{*}}.$

Using (15) and (17), the ratio of the upper and the lower bounds is bounded
for all $m$ since

$\mu\leq\frac{k^{2}100\xi^{2}P^{*}+\frac{1}{9}e^{-12mP^{*}}}{k^{2}P^{*}+\frac{1}{9}e^{-12mP^{*}}}\leq\frac{k^{2}100\xi^{2}P^{*}}{k^{2}P^{*}}=100\xi^{2}.$
(18)

For $m=1$, $\xi=1$, and thus in the proof the ratio $\mu\leq 100$. For $m$
large, $\xi\approx 2$ [46], and $\mu\lesssim 400$. For arbitrary $m$, using
the recursive construction in [51, Theorem 8.18], $\xi\leq 4$, and thus
$\mu\leq 1600$ regardless of $m$. ∎

Though the proof above succeeds in showing that the ratio is uniformly bounded
by a constant, it is not very insightful and the constant is large. However,
since the underlying vector bound can be tightened (as shown in [32]), it is
not worth improving the proof for increased elegance at this time. The
important thing is that such a uniform constant exists.

A numerical evaluation of the upper and lower bounds (of Theorem 1 and 3
respectively) shows that the ratio is smaller than $17$ for $m=1$ (see Fig.
4). A precise calculation of the cost of the quantization strategy improves
the upper bound to yield a maximum ratio smaller than $8$ (see Fig. 5).

A simple grid lattice has a packing-covering ratio $\xi=\sqrt{m}$. Therefore,
while the grid lattice has the best possible packing-covering ratio of $1$ in
the scalar case, it has a rather large packing covering ratio of
$\sqrt{2}\;(\approx 1.41)$ for $m=2$. On the other hand, a hexagonal lattice
(for $m=2$) has an improved packing-covering ratio of
$\frac{2}{\sqrt{3}}\approx 1.15$. In contrast with $m=1$, where the ratio of
upper and lower bounds of Theorem 1 and 3 is approximately $17$, a hexagonal
lattice yields a ratio smaller than $14.75$, despite having a larger packing-
covering ratio. This is a consequence of the tightening of the sphere-packing
lower bound (Theorem 3) as $m$ gets large999Indeed, in the limit
$m\rightarrow\infty$, the ratio of the asymptotic average costs attained by a
vector-quantization strategy and the vector lower bound of Theorem 2 is
bounded by $4.45$ [15]..

##  VI Discussions of numerical explorations and Conclusions

Though lattice-based quantization strategies allow us to get within a constant
factor of the optimal cost for the vector Witsenhausen problem, they are not
optimal. This is known for the scalar [5] and the infinite-length case [15].
It is shown in [15] that the “slopey-quantization” strategy of Lee, Lau and Ho
[5] that is believed to be very close to optimal in the scalar case can be
viewed as an instance of a linear scaling followed by a dirty-paper coding
(DPC) strategy. Such DPC-based strategies are also the best known strategies
in the asymptotic infinite-dimensional case, requiring optimal power $P$ to
attain $0$ asymptotic mean-square error in the estimation of
$\mathbf{x}^{m}_{1}$, and attaining costs within a factor of $1.3$ of the
optimal [32] for all $(k,\sigma_{0}^{2})$. This leads us to conjecture that a
DPC-like strategy might be optimal for finite-vector lengths as well. In the
following, we numerically explore the performance of DPC-like strategies.

Figure 6: Ratio of the achievable costs to the scalar lower bound along
$k\sigma_{0}=10^{-0.5}$ for various strategies. Quantization with MMSE-
estimation at the second controller outperforms quantization with MLE, or even
scaled MLE. For slopey-quantization with heuristic DPC-parameter, the
parameter $\alpha$ in DPC-based scheme is borrowed from the infinite-length
analysis. The figure suggests that along this path ($k\sigma_{0}=\sqrt{10}$),
the difference between optimal-DPC and heuristic DPC is not substantial.
However, Fig. 7 (b) shows that this is not true in general.  Figure 7: (a)
shows the ratio of cost attained by linear+quantization (with MMSE decoding)
to DPC with parameter $\alpha$ obtained by brute-force optimization. DPC can
do up to $15\%$ better than the optimal quantization strategy. Also the
maximum is attained along $k\approx 0.6$ which is different from $k=0.2$ of
the benchmark problem [5]. (b) shows the ratio of cost attained by
linear+quantization to DPC with $\alpha$ borrowed from infinite-length
optimization. Heuristic DPC does not outperform linear+quantization (with MMSE
estimation) substantially.

It is natural to ask how much there is to gain using a DPC-based strategy over
a simple quantization strategy. Notice that the DPC-strategy gains not only
from the slopey quantization, but also from the MMSE-estimation at the second
controller. In Fig. 6, we eliminate the latter advantage by considering first
a uniform quantization-based strategy with an appropriate scaling of the MLE
so that it approximates the MMSE-estimation performance, and then the actual
MMSE-estimation strategy for uniform quantization. Along the curve
$k\sigma_{0}=\sqrt{10}$, there is significant gain in using this approximate-
MMSE estimation over MLE, and further gain in using MMSE-estimation itself.
This also shows that there is an interesting tradeoff between the complexity
of the second controller and the system performance.

From Fig. 6, along the curve $k\sigma_{0}=\sqrt{10}$, the DPC-based strategy
performs only negligibly better than a quantization-based strategy with MMSE
estimation. Fig. 7 (a) shows that this is not true in general. A DPC-based
strategy can perform up to $15\%$ better than a simple quantization-based
scheme depending on the problem parameters. Interestingly, the advantage of
using a DPC-based strategy for the case of $k=0.2,\sigma_{0}=5$ (which is used
as the benchmark case in many papers, e.g. [5, 8]) is quite small. The maximum
gain of about $15\%$ is obtained at $k\approx 10^{-0.2}\approx 0.63$, and
$\sigma_{0}=1$ (and indeed, any $\sigma_{0}>1$. In the future, we suggest the
community use the point $(0.63,1)$ as the benchmark case.

Given that there is an advantage in using a DPC-like strategy, an interesting
question is whether the DPC parameter $\alpha$ that optimizes the DPC-based
strategy’s performance at infinite-lengths (in [15]) gives good performance
for the scalar case as well. Fig. 7 (b) answers this question at least
partially in the negative. This heuristic-DPC does only slightly better than a
quantization strategy with MMSE estimation, whereas other values of $\alpha$
do significantly better.

Finally, we observe that while uniform bin-size quantization or DPC-based
strategies are designed for atypical noise behavior, atypical behavior of the
the initial state is better accommodated by using nonuniform bin-sizes (such
as those in [5, 8]). Table I compares the two. Clearly, the advantage in
having nonuniform slopey-quantization is small, but not negligible. It would
be interesting to calibrate the advantage of nonuniform-bin sizes for
$(k,\sigma_{0})=(0.63,1)$, a maximum gain point for uniform-bin size slopey-
quantization strategies.

TABLE I: Costs attained for the benchmark case of $k=0.2$, $\sigma_{0}=5$. | linear+quantization | Slopey-quantization
---|---|---
Lee, Lau and Ho [5] | 0.1713946 | 0.1673132
Li, Marden and Shamma [8] | — | 0.1670790
This paper | 0.1715335 | 0.1673654

There are plenty of open problems that arise naturally. Both the lower and the
upper bounds have room for improvement. The lower bound can be improved by
tightening the vector lower bound of [15] (one such tightening is performed in
[32]) and obtaining corresponding finite-length results using the sphere-
packing tools developed here.

Tightening the upper bound can be performed by using DPC-based techniques over
lattices. Further, an exact analysis of the required first-stage power when
using a lattice would yield an improvement (as pointed out earlier, for $m=1$,
$\frac{1}{m}k^{2}r_{c}^{2}$ overestimates the required first-stage cost),
especially for small $m$. Improved lattice designs with better packing-
covering ratios would also improve the upper bound.

Perhaps a more significant set of open problems are the next steps in
understanding more realistic versions of Witsenhausen’s problem, specifically
those that include costs on all the inputs and all the states [13], with noisy
state evolution and noisy observations at both controllers. The hope is that
solutions to these problems can then be used as the basis for provably-good
nonlinear controller synthesis for larger distributed systems. Further, tools
developed for solving these problems might help address multiuser problems in
information theory, in the spirit of [52, 53].

## Acknowledgments

We gratefully acknowledge the support of the National Science Foundation
(CNS-403427, CNS-093240, CCF-0917212 and CCF-729122), Sumitomo Electric and
Samsung. We thank Amin Gohari, Bobak Nazer and Anand Sarwate for helpful
discussions, and Gireeja Ranade for suggesting improvements in the paper.

##  Appendix A Proof of Lemma 1

$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]+r_{p}^{2}\Pr(\mathcal{E}_{m})+2r_{p}\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left({1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}\right)\left(\|\mathbf{Z}^{m}\|{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}\right)}\right]$
(19) $\displaystyle\overset{(a)}{\leq}$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]+r_{p}^{2}\Pr(\mathcal{E}_{m})+2r_{p}\sqrt{\mathbb{E}_{\mathbf{Z}^{m}}\left[{{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]}\sqrt{\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]}$
$\displaystyle=$
$\displaystyle\left(\sqrt{\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]}+r_{p}\sqrt{\Pr(\mathcal{E}_{m})}\right)^{2},$

where $(a)$ uses the Cauchy-Schwartz inequality [54, Pg. 13].

We wish to express
$\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]$
in terms of $\psi(m,r_{p}):=\Pr(\|\mathbf{Z}^{m}\|\geq
r_{p})=\int_{\|\mathbf{z}^{m}\|\geq
r_{p}}\frac{e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2}}}{\left(\sqrt{2\pi}\right)^{m}}d\mathbf{z}^{m}$.

Denote by
$\mathcal{A}_{m}(r):=\frac{2\pi^{\frac{m}{2}}r^{m-1}}{\Gamma\left(\frac{m}{2}\right)}$
the surface area of a sphere of radius $r$ in $\mathbb{R}^{m}$ [55, Pg. 458],
where $\Gamma(\cdot{})$ is the Gamma-function satisfying
$\Gamma(m)=(m-1)\Gamma(m-1)$, $\Gamma(1)=1$, and
$\Gamma(\frac{1}{2})=\sqrt{\pi}$. Dividing the space $\mathbb{R}^{m}$ into
shells of thickness $dr$ and radii $r$,

$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]$
$\displaystyle=$ $\displaystyle\int_{\|\mathbf{z}^{m}\|\geq
r_{p}}\|\mathbf{z}^{m}\|^{2}\frac{e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2}}}{\left(\sqrt{2\pi}\right)^{m}}d\mathbf{z}^{m}=\int_{r\geq
r_{p}}r^{2}\frac{e^{-\frac{r^{2}}{2}}}{\left(\sqrt{2\pi}\right)^{m}}\mathcal{A}_{m}(r)dr$
(20) $\displaystyle=$ $\displaystyle\int_{r\geq
r_{p}}r^{2}\frac{e^{-\frac{r^{2}}{2}}}{\left(\sqrt{2\pi}\right)^{m}}\frac{2\pi^{\frac{m}{2}}r^{m-1}}{\Gamma\left(\frac{m}{2}\right)}dr$
$\displaystyle=$ $\displaystyle\int_{r\geq
r_{p}}\frac{e^{-\frac{r^{2}}{2}}2\pi}{\left(\sqrt{2\pi}\right)^{m+2}}\frac{2\pi^{\frac{m+2}{2}}r^{m+1}}{\pi\frac{2}{m}\Gamma\left(\frac{m+2}{2}\right)}dr=m\psi(m+2,r_{p}).$

Using (19), (20), and $r_{p}=\sqrt{\frac{mP}{\xi^{2}}}$

$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]\leq
m\left(\sqrt{\psi(m+2,r_{p})}+\sqrt{\frac{P}{\xi^{2}}}\sqrt{\psi(m,r_{p})}\right)^{2},$

which yields the first part of Lemma 1. To obtain a closed-form upper bound we
consider $P>\xi^{2}$. It suffices to bound $\psi(\cdot{},\cdot{})$.

$\displaystyle\psi(m,r_{p})$ $\displaystyle=$
$\displaystyle\Pr(\|\mathbf{Z}^{m}\|^{2}\geq
r_{p}^{2})=\Pr(\exp(\rho\sum_{i=1}^{m}Z_{i}^{2})\geq\exp(\rho r_{p}^{2}))$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\exp(\rho\sum_{i=1}^{m}Z_{i}^{2})}\right]e^{-\rho
r_{p}^{2}}=\mathbb{E}_{Z_{1}}\left[{\exp(\rho Z_{1}^{2})}\right]^{m}e^{-\rho
r_{p}^{2}}\overset{(\text{for}\;0<\rho<0.5)}{=}\frac{1}{(1-2\rho)^{\frac{m}{2}}}e^{-\rho
r_{p}^{2}},$

where $(a)$ follows from the Markov inequality, and the last inequality
follows from the fact that the moment generating function of a standard
$\chi_{2}^{2}$ random variable is $\frac{1}{(1-2\rho)^{\frac{1}{2}}}$ for
$\rho\in(0,0.5)$ [56, Pg. 375]. Since this bound holds for any
$\rho\in(0,0.5)$, we choose the minimizing
$\rho^{*}=\frac{1}{2}\left(1-\frac{m}{r_{p}^{2}}\right)$. Since
$r_{p}^{2}=\frac{mP}{\xi^{2}}$, $\rho^{*}$ is indeed in $(0,0.5)$ as long as
$P>\xi^{2}$. Thus,

$\displaystyle\psi(m,r_{p})\leq\frac{1}{(1-2\rho^{*})^{\frac{m}{2}}}e^{-\rho^{*}r_{p}^{2}}=\left(\frac{r_{p}^{2}}{m}\right)^{\frac{m}{2}}e^{-\frac{1}{2}\left(1-\frac{m}{r_{p}^{2}}\right)r_{p}^{2}}=e^{-\frac{r_{p}^{2}}{2}+\frac{m}{2}+\frac{m}{2}\ln\left(\frac{r_{p}^{2}}{m}\right)}.$

Using the substitutions $r_{c}^{2}=mP$, $\xi=\frac{r_{c}}{r_{p}}$ and
$r_{p}^{2}=\frac{mP}{\xi^{2}}$,

$\displaystyle\Pr(\mathcal{E}_{m})=\psi(m,r_{p})=\psi\left(m,\sqrt{\frac{mP}{\xi^{2}}}\right)\leq
e^{-\frac{mP}{2\xi^{2}}+\frac{m}{2}+\frac{m}{2}\ln\left(\frac{P}{\xi^{2}}\right)},\;\text{and}$
(21)
$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\|\mathbf{Z}^{m}\|^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]\leq
m\psi\left(m+2,\sqrt{\frac{mP}{\xi^{2}}}\right)\leq
me^{-\frac{mP}{2\xi^{2}}+\frac{m+2}{2}+\frac{m+2}{2}\ln\left(\frac{mP}{(m+2)\xi^{2}}\right)}.$
(22)

From (19), (21) and (22),

$\displaystyle\mathbb{E}_{\mathbf{Z}^{m}}\left[{\left(\|\mathbf{Z}^{m}\|+r_{p}\right)^{2}{1{1}}_{\left\\{\mathcal{E}_{m}\right\\}}}\right]$
$\displaystyle\leq$
$\displaystyle\bigg{(}\sqrt{m}e^{-\frac{mP}{4\xi^{2}}+\frac{m+2}{4}+\frac{m+2}{4}\ln\left(\frac{mP}{(m+2)\xi^{2}}\right)}\sqrt{\frac{mP}{\xi^{2}}}e^{-\frac{mP}{4\xi^{2}}+\frac{m}{4}+\frac{m}{4}\ln\left(\frac{P}{\xi^{2}}\right)}\bigg{)}^{2}$
$\displaystyle\overset{(\text{since}\;P>\xi^{2})}{<}$
$\displaystyle\left(\sqrt{m}\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)e^{-\frac{mP}{4\xi^{2}}+\frac{m+2}{4}+\frac{m+2}{4}\ln\left(\frac{P}{\xi^{2}}\right)}\right)^{2}$
$\displaystyle=$ $\displaystyle
m\left(1+\sqrt{\frac{P}{\xi^{2}}}\right)^{2}e^{-\frac{mP}{2\xi^{2}}+\frac{m+2}{2}+\frac{m+2}{2}\ln\left(\frac{P}{\xi^{2}}\right)}.$

##  Appendix B Proof of Lemma 2

The following lemma is taken from [15].

###### Lemma 3

For any three random variables $A$, $B$ and $C$,

$\displaystyle\mathbb{E}\left[{\|B-C\|^{2}}\right]\geq\left(\left(\sqrt{\mathbb{E}\left[{\|A-C\|^{2}}\right]}-\sqrt{\mathbb{E}\left[{\|A-B\|^{2}}\right]}\right)^{+}\right)^{2}.$

###### Proof:

See [15, Appendix II]. ∎

Choosing $A=\mathbf{X}^{m}_{0}$, $B=\mathbf{X}^{m}_{1}$ and
$C=\mathbf{\widehat{X}}^{m}_{1}$,

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G})|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]=\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{1}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]$
(23) $\displaystyle\geq$
$\displaystyle\bigg{(}\bigg{(}\sqrt{\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]}-\sqrt{\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{X}^{m}_{1}\|^{2}|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]}\bigg{)}^{+}\bigg{)}^{2}$
$\displaystyle=$
$\displaystyle\bigg{(}\bigg{(}\sqrt{\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{Z}^{m}_{L}\in\mathcal{S}_{L}^{G}}\right]}-\sqrt{P}\bigg{)}^{+}\bigg{)}^{2},$

since $\mathbf{X}^{m}_{0}-\mathbf{X}^{m}_{1}=\mathbf{U}^{m}_{1}$ is
independent of $\mathbf{Z}^{m}_{G}$ and
$\mathbb{E}\left[{\|\mathbf{U}^{m}_{1}\|^{2}}\right]=mP$. Define
$\mathbf{Y}^{m}_{L}:=\mathbf{X}^{m}_{1}+\mathbf{Z}^{m}_{L}$ to be the output
when the observation noise $\mathbf{Z}^{m}_{L}$ is distributed as a truncated
Gaussian distribution:

$f_{Z_{L}}(\mathbf{z}^{m}_{L})=\left\\{\begin{array}[]{ll}c_{m}(L)\frac{e^{-\frac{\|\mathbf{z}^{m}_{L}\|^{2}}{2\sigma_{G}^{2}}}}{\left(\sqrt{2\pi\sigma_{G}^{2}}\right)^{m}}&\mathbf{z}^{m}_{L}\in\mathcal{S}_{L}^{G}\\\
0&\text{otherwise.}\end{array}\right.$ (24)

Let the estimate at the second controller on observing $\mathbf{y}^{m}_{L}$ be
denoted by $\mathbf{\widehat{X}}^{m}_{L}$. Then, by the definition of
conditional expectations,

$\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{1}\|^{2}|\mathbf{Z}^{m}_{G}\in\mathcal{S}_{L}^{G}}\right]=\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{L}\|^{2}}\right].$
(25)

To get a lower bound, we now allow the controllers to optimize themselves with
the additional knowledge that the observation noise $\mathbf{z}^{m}$ must fall
in $\mathcal{S}_{L}^{G}$. In order to prevent the first controller from
“cheating” and allocating different powers to the two events (_i.e._
$\mathbf{z}^{m}$ falling or not falling in $\mathcal{S}_{L}^{G}$), we enforce
the constraint that the power $P$ must not change with this additional
knowledge. Since the controller’s observation $\mathbf{X}^{m}_{0}$ is
independent of $\mathbf{Z}^{m}$, this constraint is satisfied by the original
controller (without the additional knowledge) as well, and hence the cost for
the system with the additional knowledge is still a valid lower bound to that
of the original system.

The rest of the proof uses ideas from channel coding and the rate-distortion
theorem [57, Ch. 13] from information theory. We view the problem as a problem
of implicit communication from the first controller to the second. Notice that
for a given $\gamma(\cdot{})$, $\mathbf{X}^{m}_{1}$ is a function of
$\mathbf{X}^{m}_{0}$,
$\mathbf{Y}^{m}_{L}=\mathbf{X}^{m}_{1}+\mathbf{Z}^{m}_{L}$ is conditionally
independent of $\mathbf{X}^{m}_{0}$ given $\mathbf{X}^{m}_{1}$ (since the
noise $\mathbf{Z}^{m}_{L}$ is additive and independent of $\mathbf{X}^{m}_{1}$
and $\mathbf{X}^{m}_{0}$). Further, $\mathbf{\widehat{X}}^{m}_{L}$ is a
function of $\mathbf{Y}^{m}_{L}$. Thus
$\mathbf{X}^{m}_{0}-\mathbf{X}^{m}_{1}-\mathbf{Y}^{m}_{L}-\mathbf{\widehat{X}}^{m}_{L}$
form a Markov chain. Using the data-processing inequality [57, Pg. 33],

$I(\mathbf{X}^{m}_{0};\mathbf{\widehat{X}}^{m}_{L})\leq
I(\mathbf{X}^{m}_{1};\mathbf{Y}^{m}_{L}),$ (26)

where $I(A,B)$ is the expression for mutual information expression between two
random variables $A$ and $B$ (see, for example, [57, Pg. 18, Pg. 231]). To
estimate the distortion to which $\mathbf{X}^{m}_{0}$ can be communicated
across this truncated Gaussian channel (which, in turn, helps us lower bound
the MMSE in estimating $\mathbf{X}^{m}_{1}$), we need to upper bound the term
on the RHS of (26).

###### Lemma 4

$\frac{1}{m}I(\mathbf{X}^{m}_{1};\mathbf{Y}^{m}_{L})\leq\frac{1}{2}\log_{2}\left(\frac{e^{1-d_{m}(L)}(\bar{P}+d_{m}(L)\sigma_{G}^{2})c_{m}^{\frac{2}{m}}(L)}{\sigma_{G}^{2}}\right).$

###### Proof:

We first obtain an upper bound to the power of $\mathbf{X}^{m}_{1}$ (this
bound is the same as that used in [15]):

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{X}^{m}_{0}+\mathbf{U}^{m}_{1}\|^{2}}\right]=\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{X}^{m}_{0}\|^{2}}\right]+\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{U}^{m}_{1}\|^{2}}\right]+2\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{{\mathbf{X}^{m}_{0}}^{T}\mathbf{U}^{m}_{1}}\right]$
$\displaystyle\overset{(a)}{\leq}$
$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{X}^{m}_{0}\|^{2}}\right]+\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{U}^{m}_{1}\|^{2}}\right]+2\sqrt{\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{X}^{m}_{0}\|^{2}}\right]}\sqrt{\mathbb{E}_{\mathbf{X}^{m}_{0}}\left[{\|\mathbf{U}^{m}_{1}\|^{2}}\right]}$
$\displaystyle\leq$ $\displaystyle m(\sigma_{0}+\sqrt{P})^{2},$

where $(a)$ follows from the Cauchy-Schwartz inequality. We use the following
definition of differential entropy $h(A)$ of a continuous random variable $A$
[57, Pg. 224]:

$h(A)=-\int_{S}f_{A}(a)\log_{2}\left(f_{A}(a)\right)da,$ (27)

where $f_{A}(a)$ is the pdf of $A$, and $S$ is the support set of $A$.
Conditional differential entropy is defined similarly [57, Pg. 229].

Let $\bar{P}:=(\sigma_{0}+\sqrt{P})^{2}$. Now,
$\mathbb{E}\left[{Y_{L,i}^{2}}\right]=\mathbb{E}\left[{X_{1,i}^{2}}\right]+\mathbb{E}\left[{Z_{L,i}^{2}}\right]$
(since $X_{1,i}$ is independent of $Z_{L,i}$ and by symmetry, $Z_{L,i}$ are
zero mean random variables). Denote
$\bar{P}_{i}=\mathbb{E}\left[{X_{1,i}^{2}}\right]$ and
$\sigma_{G,i}^{2}=\mathbb{E}\left[{Z_{L,i}^{2}}\right]$. In the following, we
derive an upper bound $C_{G,L}^{(m)}$ on
$\frac{1}{m}I(\mathbf{X}^{m}_{1};\mathbf{Y}^{m}_{L})$.

$\displaystyle C_{G,L}^{(m)}$ $\displaystyle:=$
$\displaystyle\sup_{p(\mathbf{X}^{m}_{1}):\mathbb{E}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]\leq
m\bar{P}}\frac{1}{m}I(\mathbf{X}^{m}_{1};\mathbf{Y}^{m}_{L})$ (28)
$\displaystyle\overset{(a)}{=}$
$\displaystyle\sup_{p(\mathbf{X}^{m}_{1}):\mathbb{E}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]\leq
m\bar{P}}\frac{1}{m}h(\mathbf{Y}^{m}_{L})-\frac{1}{m}h(\mathbf{Y}^{m}_{L}|\mathbf{X}^{m}_{1})$
$\displaystyle\overset{}{=}$
$\displaystyle\sup_{p(\mathbf{X}^{m}_{1}):\mathbb{E}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]\leq
m\bar{P}}\frac{1}{m}h(\mathbf{Y}^{m}_{L})-\frac{1}{m}h(\mathbf{X}^{m}_{1}+\mathbf{Z}^{m}_{L}|\mathbf{X}^{m}_{1})$
$\displaystyle\overset{(b)}{=}$
$\displaystyle\sup_{p(\mathbf{X}^{m}_{1}):\mathbb{E}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]\leq
m\bar{P}}\frac{1}{m}h(\mathbf{Y}^{m}_{L})-\frac{1}{m}h(\mathbf{Z}^{m}_{L}|\mathbf{X}^{m}_{1})$
$\displaystyle\overset{(c)}{=}$
$\displaystyle\sup_{p(\mathbf{X}^{m}_{1}):\mathbb{E}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]\leq
m\bar{P}}\frac{1}{m}h(\mathbf{Y}^{m}_{L})-\frac{1}{m}h(\mathbf{Z}^{m}_{L})$
$\displaystyle\overset{(d)}{\leq}$
$\displaystyle\sup_{p(\mathbf{X}^{m}_{1}):\mathbb{E}\left[{\|\mathbf{X}^{m}_{1}\|^{2}}\right]\leq
m\bar{P}}\frac{1}{m}\sum_{i=1}^{m}h(Y_{L,i})-\frac{1}{m}h(\mathbf{Z}^{m}_{L})$
$\displaystyle\overset{(e)}{\leq}$
$\displaystyle\sup_{\bar{P}_{i}:\sum_{i=1}^{m}\bar{P}_{i}\leq
m\bar{P}}\frac{1}{m}\sum_{i=1}^{m}\frac{1}{2}\log_{2}\left(2\pi
e(\bar{P}_{i}+\sigma_{G,i}^{2})\right)-\frac{1}{m}h(\mathbf{Z}^{m}_{L})$
$\displaystyle\overset{(f)}{\leq}$ $\displaystyle\frac{1}{2}\log_{2}\left(2\pi
e(\bar{P}+d_{m}(L)\sigma_{G}^{2})\right)-\frac{1}{m}h(\mathbf{Z}^{m}_{L}).$

Here, $(a)$ follows from the definition of mutual information [57, Pg. 231],
$(b)$ follows from the fact that translation does not change the differential
entropy [57, Pg. 233], $(c)$ uses independence of $\mathbf{Z}^{m}_{L}$ and
$\mathbf{X}^{m}_{1}$, and $(d)$ uses the chain rule for differential entropy
[57, Pg. 232] and the fact that conditioning reduces entropy [57, Pg. 232]. In
$(e)$, we used the fact that Gaussian random variables maximize differential
entropy. The inequality $(f)$ follows from the concavity-$\cap$ of the
$\log(\cdot{})$ function and an application of Jensen’s inequality [57, Pg.
25]. We also use the fact that
$\frac{1}{m}\sum_{i=1}^{m}\sigma_{G,i}^{2}=d_{m}(L)\sigma_{G}^{2}$, which can
be proven as follows

$\displaystyle\frac{1}{m}\mathbb{E}\left[{\sum_{i=1}^{m}Z_{L,i}^{2}}\right]$
$\displaystyle\overset{(\text{using}~{}\eqref{eq:fz})}{=}$
$\displaystyle\frac{\sigma_{G}^{2}}{m}\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}\frac{\|\mathbf{z}^{m}\|^{2}}{\sigma_{G}^{2}}c_{m}(L)\frac{\exp\left(-\frac{\|\mathbf{z}^{m}_{G}\|^{2}}{2\sigma_{G}^{2}}\right)}{\left(\sqrt{2\pi\sigma_{G}^{2}}\right)^{m}}d\mathbf{z}^{m}_{G}$
(29) $\displaystyle=$
$\displaystyle\frac{c_{m}(L)\sigma_{G}^{2}}{m}\mathbb{E}\left[{\|\mathbf{Z}^{m}_{G}\|^{2}{1{1}}_{\left\\{\|\mathbf{Z}^{m}_{G}\|\leq\sqrt{mL^{2}\sigma_{G}^{2}}\right\\}}}\right]$
$\displaystyle\overset{(\mathbf{\widetilde{Z}}^{m}:=\frac{\mathbf{Z}^{m}_{G}}{\sigma_{G}})}{=}$
$\displaystyle\frac{c_{m}(L)\sigma_{G}^{2}}{m}\mathbb{E}\left[{\|\mathbf{\widetilde{Z}}^{m}\|^{2}{1{1}}_{\left\\{\|\mathbf{\widetilde{Z}}^{m}\|\leq\sqrt{mL^{2}}\right\\}}}\right]$
$\displaystyle=$
$\displaystyle\frac{c_{m}(L)\sigma_{G}^{2}}{m}\bigg{(}\mathbb{E}\left[{\|\mathbf{\widetilde{Z}}^{m}\|^{2}}\right]-\mathbb{E}\left[{\|\mathbf{\widetilde{Z}}^{m}\|^{2}{1{1}}_{\left\\{\|\mathbf{\widetilde{Z}}^{m}\|>\sqrt{mL^{2}}\right\\}}}\right]\bigg{)}$
$\displaystyle\overset{(\text{using}~{}\eqref{eq:psinplus2})}{=}$
$\displaystyle\frac{c_{m}(L)\sigma_{G}^{2}}{m}\left(m-m\psi(m+2,\sqrt{mL^{2}})\right)$
$\displaystyle=$ $\displaystyle
c_{m}(L)\left(1-\psi(m+2,L\sqrt{m})\right)\sigma_{G}^{2}=d_{m}(L)\sigma_{G}^{2}.$

We now compute $h(\mathbf{Z}^{m}_{L})$

$\displaystyle h(\mathbf{Z}^{m}_{L})$ $\displaystyle=$
$\displaystyle\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}f_{Z_{L}}(\mathbf{z}^{m})\log_{2}\left(\frac{1}{f_{Z_{L}}(\mathbf{z}^{m})}\right)d\mathbf{z}^{m}=\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}f_{Z_{L}}(\mathbf{z}^{m})\log_{2}\left(\frac{\left(\sqrt{2\pi\sigma_{G}^{2}}\right)^{m}}{c_{m}(L)e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2\sigma_{G}^{2}}}}\right)d\mathbf{z}^{m}$
(30) $\displaystyle=$
$\displaystyle-\log_{2}\left(c_{m}(L)\right)+\frac{m}{2}\log_{2}\left(2\pi\sigma_{G}^{2}\right)+\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}c_{m}(L)f_{G}(\mathbf{z}^{m})\frac{\|\mathbf{z}^{m}\|^{2}}{2\sigma_{G}^{2}}\log_{2}\left(e\right)d\mathbf{z}^{m}.$

Analyzing the last term of (30),

$\displaystyle\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}c_{m}(L)f_{G}(\mathbf{z}^{m})\frac{\|\mathbf{z}^{m}\|^{2}}{2\sigma_{G}^{2}}\log_{2}\left(e\right)d\mathbf{z}^{m}$
$\displaystyle=$
$\displaystyle\frac{\log_{2}\left(e\right)}{2\sigma_{G}^{2}}\int_{\mathbf{z}^{m}\in\mathcal{S}_{L}^{G}}c_{m}(L)\frac{e^{-\frac{\|\mathbf{z}^{m}\|^{2}}{2\sigma_{G}^{2}}}}{\left(\sqrt{2\pi\sigma_{G}^{2}}\right)^{m}}\|\mathbf{z}^{m}\|^{2}d\mathbf{z}^{m}$
(31) $\displaystyle=$
$\displaystyle\frac{\log_{2}\left(e\right)}{2\sigma_{G}^{2}}\int_{\mathbf{z}^{m}}f_{Z_{L}}(\mathbf{z}^{m})\|\mathbf{z}^{m}\|^{2}d\mathbf{z}^{m}$
$\displaystyle\overset{(\text{using}~{}\eqref{eq:fz})}{=}$
$\displaystyle\frac{\log_{2}\left(e\right)}{2\sigma_{G}^{2}}\mathbb{E}_{G}\left[{\|\mathbf{Z}^{m}_{L}\|^{2}}\right]=\frac{\log_{2}\left(e\right)}{2\sigma_{G}^{2}}\mathbb{E}_{G}\left[{\sum_{i=1}^{m}Z_{L,i}^{2}}\right]$
$\displaystyle\overset{(\text{using}~{}\eqref{eq:expectzl})}{=}$
$\displaystyle\frac{\log_{2}\left(e\right)}{2\sigma_{G}^{2}}md_{m}(L)\sigma_{G}^{2}=\frac{m\log_{2}\left(e^{d_{m}(L)}\right)}{2}.$

The expression $C_{G,L}^{(m)}$ can now be upper bounded using (28), (30) and
(31) as follows.

$\displaystyle C_{G,L}^{(m)}$ $\displaystyle\leq$
$\displaystyle\frac{1}{2}\log_{2}\left(2\pi
e(\bar{P}+d_{m}(L)\sigma_{G}^{2})\right)+\frac{1}{m}\log_{2}\left(c_{m}(L)\right)-\frac{1}{2}\log_{2}\left(2\pi\sigma_{G}^{2}\right)-\frac{1}{2}\log_{2}\left(e^{d_{m}(L)}\right)$
(32) $\displaystyle=$ $\displaystyle\frac{1}{2}\log_{2}\left(2\pi
e(\bar{P}+d_{m}(L)\sigma_{G}^{2})\right)+\frac{1}{2}\log_{2}\left(c_{m}^{\frac{2}{m}}(L)\right)-\frac{1}{2}\log_{2}\left(2\pi\sigma_{G}^{2}\right)-\frac{1}{2}\log_{2}\left(e^{d_{m}(L)}\right)$
$\displaystyle=$ $\displaystyle\frac{1}{2}\log_{2}\left(\frac{2\pi
e(\bar{P}+d_{m}(L)\sigma_{G}^{2})c_{m}^{\frac{2}{m}}(L)}{2\pi\sigma_{G}^{2}e^{d_{m}(L)}}\right)=\frac{1}{2}\log_{2}\left(\frac{e^{1-d_{m}(L)}(\bar{P}+d_{m}(L)\sigma_{G}^{2})c_{m}^{\frac{2}{m}}(L)}{\sigma_{G}^{2}}\right).$

∎

Now, recall that the rate-distortion function $D_{m}(R)$ for squared error
distortion for source $\mathbf{X}^{m}_{0}$ and reconstruction
$\mathbf{\widehat{X}}^{m}_{L}$ is,

$D_{m}(R):=\inf_{\scriptsize\begin{array}[]{c}p(\mathbf{\widehat{X}}^{m}_{L}|\mathbf{X}^{m}_{0})\\\
\frac{1}{m}I(\mathbf{X}^{m}_{0};\mathbf{\widehat{X}}^{m}_{L})\leq
R\end{array}}\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{L}\|^{2}}\right],$
(33)

which is the dual of the rate-distortion function [57, Pg. 341]. Since
$I(\mathbf{X}^{m}_{0};\mathbf{\widehat{X}}^{m}_{L})\leq mC_{G,L}^{(m)}$, using
the converse to the rate distortion theorem [57, Pg. 349] and the upper bound
on the mutual information represented by $C_{G,L}^{(m)}$,

$\frac{1}{m}\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{\|\mathbf{X}^{m}_{0}-\mathbf{\widehat{X}}^{m}_{L}\|^{2}}\right]\geq
D_{m}(C_{G,L}^{(m)}).$ (34)

Since the Gaussian source is iid, $D_{m}(R)=D(R)$, where
$D(R)=\sigma_{0}^{2}2^{-2R}$ is the distortion-rate function for a Gaussian
source of variance $\sigma_{0}^{2}$ [57, Pg. 346]. Thus, using (23), (25) and
(34),

$\displaystyle\mathbb{E}_{\mathbf{X}^{m}_{0},\mathbf{Z}^{m}_{G}}\left[{J_{2}^{(\gamma)}(\mathbf{X}^{m}_{0},\mathbf{Z}^{m})|\mathbf{Z}^{m}\in\mathcal{S}_{L}^{G}}\right]\geq\left(\left(\sqrt{D(C_{G,L}^{(m)})}-\sqrt{P}\right)^{+}\right)^{2}.$

Substituting the bound on $C_{G,L}^{(m)}$ from (32),

$\displaystyle
D(C_{G,L}^{(m)})=\sigma_{0}^{2}2^{-2C_{G,L}^{(m)}}=\frac{\sigma_{0}^{2}\sigma_{G}^{2}}{c_{m}^{\frac{2}{m}}(L)e^{1-d_{m}(L)}(\bar{P}+d_{m}(L)\sigma_{G}^{2})}.$

Using (23), this completes the proof of the lemma. Notice that
$c_{m}(L)\rightarrow 1$ and $d_{m}(L)\rightarrow 1$ for fixed $m$ as
$L\rightarrow\infty$, as well as for fixed $L>1$ as $m\rightarrow\infty$. So
the lower bound on $D(C_{G,L}^{(m)})$ approaches $\kappa$ of Theorem 2 in both
of these two limits.

## References

  * [1] H. S. Witsenhausen, “A counterexample in stochastic optimum control,” _SIAM Journal on Control_ , vol. 6, no. 1, pp. 131–147, Jan. 1968.
  * [2] Y.-C. Ho, “Review of the Witsenhausen problem,” _Proceedings of the 47th IEEE Conference on Decision and Control (CDC)_ , pp. 1611–1613, 2008.
  * [3] R. Bansal and T. Basar, “Stochastic teams with nonclassical information revisited: When is an affine control optimal?” _IEEE Trans. Automat. Contr._ , vol. 32, pp. 554–559, Jun. 1987.
  * [4] M. Baglietto, T. Parisini, and R. Zoppoli, “Nonlinear approximations for the solution of team optimal control problems,” _Proceedings of the IEEE Conference on Decision and Control (CDC)_ , pp. 4592–4594, 1997.
  * [5] J. T. Lee, E. Lau, and Y.-C. L. Ho, “The Witsenhausen counterexample: A hierarchical search approach for nonconvex optimization problems,” _IEEE Trans. Automat. Contr._ , vol. 46, no. 3, pp. 382–397, 2001.
  * [6] Y.-C. Ho and T. Chang, “Another look at the nonclassical information structure problem,” _IEEE Trans. Automat. Contr._ , vol. 25, no. 3, pp. 537–540, 1980.
  * [7] C. H. Papadimitriou and J. N. Tsitsiklis, “Intractable problems in control theory,” _SIAM Journal on Control and Optimization_ , vol. 24, no. 4, pp. 639–654, 1986.
  * [8] N. Li, J. R. Marden, and J. S. Shamma, “Learning approaches to the Witsenhausen counterexample from a view of potential games,” _Proceedings of the 48th IEEE Conference on Decision and Control (CDC)_ , 2009.
  * [9] S. K. Mitter and A. Sahai, “Information and control: Witsenhausen revisited,” in _Learning, Control and Hybrid Systems: Lecture Notes in Control and Information Sciences 241_ , Y. Yamamoto and S. Hara, Eds. New York, NY: Springer, 1999, pp. 281–293.
  * [10] T. Basar, “Variations on the theme of the Witsenhausen counterexample,” _Proceedings of the 47th IEEE Conference on Decision and Control (CDC)_ , pp. 1614–1619, 2008.
  * [11] M. Rotkowitz, “On information structures, convexity, and linear optimality,” _Proceedings of the 47th IEEE Conference on Decision and Control (CDC)_ , pp. 1642–1647, 2008.
  * [12] M. Rotkowitz and S. Lall, “A characterization of convex problems in decentralized control,” _IEEE Trans. Automat. Contr._ , vol. 51, no. 2, pp. 1984–1996, Feb. 2006.
  * [13] P. Grover, S. Y. Park, and A. Sahai, “On the generalized Witsenhausen counterexample,” in _Proceedings of the Allerton Conference on Communication, Control, and Computing_ , Monticello, IL, Oct. 2009.
  * [14] M. Rotkowitz, “Linear controllers are uniformly optimal for the Witsenhausen counterexample,” _Proceedings of the 45th IEEE Conference on Decision and Control (CDC)_ , pp. 553–558, Dec. 2006.
  * [15] P. Grover and A. Sahai, “Vector Witsenhausen counterexample as assisted interference suppression,” _To appear in the special issue on Information Processing and Decision Making in Distributed Control Systems of the International Journal on Systems, Control and Communications (IJSCC)_ , Sep. 2009. [Online]. Available: http://www.eecs.berkeley.edu/$\sim$sahai/
  * [16] N. C. Martins, “Witsenhausen’s counter example holds in the presence of side information,” _Proceedings of the 45th IEEE Conference on Decision and Control (CDC)_ , pp. 1111–1116, 2006.
  * [17] A. S. Avestimehr, S. Diggavi, and D. N. C. Tse, “A deterministic approach to wireless relay networks,” in _Proc. of the Allerton Conference on Communications, Control and Computing_ , October 2007.
  * [18] A. S. Avestimehr, “Wireless network information flow: A deterministic approach,” Ph.D. dissertation, UC Berkeley, Berkeley, CA, 2008.
  * [19] A. S. Avestimehr, S. Diggavi, and D. N. C. Tse, “Wireless network information flow: a deterministic approach,” _Submitted to IEEE Transactions on Information Theory_ , Jul. 2009.
  * [20] K. Shoarinejad, J. L. Speyer, and I. Kanellakopoulos, “A stochastic decentralized control problem with noisy communication,” _SIAM Journal on Control and optimization_ , vol. 41, no. 3, pp. 975–990, 2002.
  * [21] J. Doyle, Panel Discussions at Paths Ahead in the Science of Information and Decision Systems, Cambridge, MA, Nov. 2009.
  * [22] S. Y. Park, P. Grover, and A. Sahai, “A constant-factor approximately optimal solution to the Witsenhausen counterexample,” _Proceedings of the 48th IEEE Conference on Decision and Control (CDC)_ , Dec. 2009.
  * [23] P. Grover and A. Sahai, “A vector version of Witsenhausen’s counterexample: Towards convergence of control, communication and computation,” _Proceedings of the 47th IEEE Conference on Decision and Control (CDC)_ , Dec. 2008.
  * [24] M. Costa, “Writing on dirty paper,” _IEEE Trans. Inform. Theory_ , vol. 29, no. 3, pp. 439–441, May 1983.
  * [25] H. Weingarten, Y. Steinberg, and S. Shamai, “The capacity region of the Gaussian multiple-input multiple-output broadcast channel,” _IEEE Transactions on Information Theory_ , vol. 52, no. 9, pp. 3936–3964, 2006.
  * [26] N. Devroye, P. Mitran, and V. Tarokh, “Achievable rates in cognitive radio channels,” _IEEE Trans. Inform. Theory_ , vol. 52, no. 5, pp. 1813–1827, May 2006.
  * [27] A. Jovicic and P. Viswanath, “Cognitive radio: An information-theoretic perspective,” in _Proceedings of the 2006 International Symposium on Information Theory, Seattle, WA_ , Seattle, WA, Jul. 2006, pp. 2413–2417.
  * [28] Y.-H. Kim, A. Sutivong, and T. M. Cover, “State amplification,” _IEEE Trans. Inform. Theory_ , vol. 54, no. 5, pp. 1850–1859, May 2008.
  * [29] N. Merhav and S. Shamai, “Information rates subject to state masking,” _IEEE Trans. Inform. Theory_ , vol. 53, no. 6, pp. 2254–2261, Jun. 2007\.
  * [30] T. Philosof, A. Khisti, U. Erez, and R. Zamir, “Lattice strategies for the dirty multiple access channel,” in _Proceedings of the IEEE Symposium on Information Theory_ , Nice, France, Jul. 2007, pp. 386–390.
  * [31] S. Kotagiri and J. Laneman, “Multiaccess channels with state known to some encoders and independent messages,” _EURASIP Journal on Wireless Communications and Networking_ , no. 450680, 2008.
  * [32] P. Grover, A. B. Wagner, and A. Sahai, “Information embedding meets distributed control,” _In preparation for submission to IEEE Transactions on Information Theory_ , 2009.
  * [33] G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi, _Complexity and Approximation: Combinatorial optimization problems and their approximability properties_. Springer Verlag, 1999.
  * [34] R. Cogill and S. Lall, “Suboptimality bounds in stochastic control: A queueing example,” in _American Control Conference, 2006_ , Jun. 2006, pp. 1642–1647.
  * [35] R. Cogill, S. Lall, and J. P. Hespanha, “A constant factor approximation algorithm for event-based sampling,” in _American Control Conference, 2007\. ACC ’07_ , Jul. 2007, pp. 305–311.
  * [36] R. Etkin, D. Tse, and H. Wang, “Gaussian interference channel capacity to within one bit,” _IEEE Trans. Inform. Theory_ , vol. 54, no. 12, Dec. 2008\.
  * [37] D. Baron, M. A. Khojastepour, and R. G. Baraniuk, “Non-asymptotic performance of symmetric Slepian-Wolf coding,” in _39th Conference on Information Sciences and Systems_ , Princeton, NJ, Mar. 2005.
  * [38] Y. Polyanskiy, H. V. Poor, and S. Verdu, “Dispersion of Gaussian channels,” in _IEEE International Symposium on Information Theory_ , Seoul, Korea, 2009\.
  * [39] ——, “New channel coding achievability bounds,” in _IEEE International Symposium on Information Theory_ , Toronto, Canada, 2008.
  * [40] R. G. Gallager, _Information Theory and Reliable Communication_. New York, NY: John Wiley, 1971.
  * [41] M. S. Pinsker, “Bounds on the probability and of the number of correctable errors for nonblock codes,” _Problemy Peredachi Informatsii_ , vol. 3, no. 4, pp. 44–55, Oct./Dec. 1967.
  * [42] A. Sahai, “Why block-length and delay behave differently if feedback is present,” _IEEE Trans. Inform. Theory_ , no. 5, pp. 1860–1886, May 2008\.
  * [43] A. Sahai and P. Grover, “The price of certainty : “waterslide curves” and the gap to capacity,” Dec. 2007. [Online]. Available: http://arXiv.org/abs/0801.0352v1
  * [44] R. F. H. Fisher, _Precoding and Signal Shaping for Digital Transmission_. New York, NY: John Wiley, 2002.
  * [45] J. H. Conway and N. J. A. Sloane, _Sphere packings, lattices and groups_. New York: Springer-Verlag, 1988\.
  * [46] U. Erez, S. Litsyn, and R. Zamir, “Lattices which are good for (almost) everything,” _IEEE Trans. Inform. Theory_ , vol. 51, no. 10, pp. 3401–3416, Oct. 2005.
  * [47] T. J. Goblick, “Theoretical limitations on the transmission of data from analog sources,” _IEEE Trans. Inform. Theory_ , vol. 11, no. 4, Oct. 1965\.
  * [48] R. Blahut, “A hypothesis testing approach to information theory,” Ph.D. dissertation, Cornell University, Ithaca, NY, 1972.
  * [49] I. Csiszár and J. Körner, _Information Theory: Coding Theorems for Discrete Memoryless Systems_. New York: Academic Press, 1981.
  * [50] “Code for performance of lattice-based strategies for Witsenhausen’s counterexample.” [Online]. Available: http://www.eecs.berkeley.edu/$\sim$pulkit/FiniteWitsenhausenCode.htm
  * [51] D. Micciancio and S. Goldwasser, _Complexity of Lattice Problems: A Cryptographic Perspective_. Springer, 2002\.
  * [52] W. Wu, S. Vishwanath, and A. Arapostathis, “Gaussian interference networks with feedback: Duality, sum capacity and dynamic team problems,” in _Proceedings of the Allerton Conference on Communication, Control, and Computing_ , Monticello, IL, Oct. 2005.
  * [53] N. Elia, “When Bode meets Shannon: control-oriented feedback communication schemes,” _IEEE Trans. Automat. Contr._ , vol. 49, no. 9, pp. 1477–1488, Sep. 2004.
  * [54] R. Durrett, _Probability: Theory and Examples_ , 1st ed. Belmont, CA: Brooks/Cole, 2005.
  * [55] R. Courant, F. John, A. A. Blank, and A. Solomon, _Introduction to Calculus and Analysis_. Springer, 2000\.
  * [56] S. M. Ross, _A first course in probability_ , 6th ed. Prentice Hall, 2001.
  * [57] T. M. Cover and J. A. Thomas, _Elements of Information Theory_ , 1st ed. New York: Wiley, 1991.