a diagram must always have at least one bad neighbour). Then $P$ has a
subdiagram $S_{\ell}$ corresponding to a face $P(S_{\ell})$ which is a
$(d-4(\ell+1))$-polytope with $d+k-5(\ell+1)$ facets, where $\ell$ is the
maximum non-negative integer such that

$d>k+3\ell\,,$

and such that $\Sigma_{S_{\ell}}=\overline{S_{\ell}}$.

###### Proof.

Fix $m$ such that $d\geq k+3m$. We proceed by induction on $m$, showing at
each step that $P$ has a subdiagram $S_{m}$ corresponding to a face $P(S_{m})$
which is a $(d-4(m+1))$-polytope with $d+k-5(m+1)$ facets satisfying
$\Sigma_{S_{m}}=\overline{S_{m}}$. Note that in particular, $P(S_{m})$
contains missing faces of size only $2$ and $5$, as its Coxeter diagram is a
subdiagram of the diagram for $P$. The base case $m=0$ is trivial, as we can
view $P$ as a face of itself and take $S_{0}$ to be the empty diagram.

Now suppose that we have fixed a subdiagram $S_{m-1}$ with the necessary
properties. Since we have $d>k+3m$, then we have

$2(d-4m)>d+k-5m\,.$

Thus, by Lemma 10.6, a $(d-4m)$-polytope with $d+k-5m$ facets cannot be
$3$-free. Hence the polytope $P(S_{m-1})$ must have a missing face of size
$5$. The corresponding Lannér diagram must contain a subdiagram $T_{m}$ of
type $H_{4}$ or $F_{4}$. Let $S_{m}=S_{m-1}\cup T_{m}$. By our hypotheses,
$T_{m}$ has precisely one bad neighbour, hence $P(S_{m})$ is a compact Coxeter
$(d-4(m+1))$-polytope with $d+k-5(m+1)$ facets, as desired. ∎

######  Lemma 10.15.

Suppose there exist a compact Coxeter $12$-polytope $P$ with $18$ facets whose
missing faces have size either $2$ and $5$. Then $P$ contains a subdiagram of
the type $H_{4}$, $F_{4}$ with at least $2$ bad neighbours.

###### Proof.

By Lemma 10.14, $P$ must have a subdiagram $\Sigma_{P^{\prime}}$ corresponding
to a face $P^{\prime}$ that is a compact Coxeter $4$-polytope with $8$ facets.
However, it can be checked that each of these contains a subdiagram of type
$D_{4}$ with $4$ bad neighbours or of type $B_{3}$ with at least $3$ bad
neighbours, respectively. Looking at the faces corresponding to these
subdiagrams in $\Sigma$ would yield a compact Coxeter $8$-polytope with at
most $10$ facets or a compact Coxeter $9$-polytope with at most $12$ facets,
both of which do not exist. ∎

###  10.3. Polytopes with $d+7$ facets

######  Lemma 10.16.

There is no compact Coxeter $16$-polytope with $23$ facets.

###### Proof.

By Lemma 10.14, this must have a face which is a $4$-polytope with $8$ facets.
But by the argument in Lemma 10.15, these each contain either a subdiagram of
type $D_{4}$ with $4$ bad neighbours or $B_{3}$ with at least $3$ bad
neighbours, respectively. Looking at the face corresponding to such a
subdiagram in $\Sigma$ would yield a compact Coxeter $12$-polytope with at
most $15$ facets or a compact Coxeter $13$-polytope with at most $17$ facets,
both of which do not exist. ∎

######  Corollary 10.17.

We have $D(7)\leq 15$.

######  Lemma 10.18.

Suppose there exist a compact Coxeter $15$-polytope $P$ with $22$ facets whose
missing faces have size either $2$ and $5$. Then $P$ contains a subdiagram of
the type $H_{4}$ or $F_{4}$ with at least $2$ bad neighbours.

###### Proof.

By Lemma 10.14, $P$ must have a subdiagram $\Sigma_{P^{\prime}}$ corresponding
to a face $P^{\prime}$ that is a compact Coxeter $3$-polytope with $7$ facets.
By [10, Satz 6.9], there is precisely one possible combinatorial type. It is
fairly straightforward to check that no such polytope can have only angles
$\pi/2$ or $\pi/3$ (this can be accomplished with the code described in
Section 5). If this contains a subdiagram of the type $G_{2}^{(m)}$ for $m\geq
4$, then it must have at least $3$ bad neighbours (as any two vertices not
joined by a dashed edge in the diagram are together adjacent to at least $3$
dashed edges). So there is a face of $P^{\prime}$ which is a compact Coxeter
$13$-polytope with at most $17$ facets, which does not exist. ∎

###  10.4. Polytopes with $d+8$ facets

######  Lemma 10.19.

There is no compact Coxeter $19$-polytope with $27$ facets.

###### Proof.

By Lemma 10.5, $P$ must have missing faces only of size $2$ or $5$. By Lemma
10.14, this must have a face which is a $15$-polytope with $22$ facets. By
Lemma 10.18, this must have a subdiagram of type $H_{4}$ or $F_{4}$ with at
least two bad neighbours. But then this yields a face which is a compact
Coxeter $15$-polytope with at most $21$ facets, contradicting that $D(i)<15$
for $i\leq 6$. ∎

######  Corollary 10.20.

We have $D(8)\leq 18$.

While in the previous cases we were able to reduce the dimension by one via
showing that there are certain subdiagrams with at least two bad neighbours,
we were not able to obtain such a reduction in this case. Lemma 10.14
guarantees that such a polytope has a face which is a compact $2$-polytope
with $6$ facets. However, by the classification in [5] there are many of these
for which every subdiagram not of type $A_{n}$ or $D_{5}$ has at most one bad
neighbour.

###  10.5. Polytopes with $d+9$ or $d+10$ facets

As mentioned previously, in these cases we could not reduce the dimension by
one.

######  Corollary 10.21.

We have $D(9)\leq 22$.

###### Proof.

This follows directly from Theorem 10.7 and the results proved above that
$D(k)\leq 18$ for $k<9$. ∎

######  Corollary 10.22.

We have $D(10)\leq 26$.

###### Proof.

This follows directly from Theorem 10.7 and the results proved above that
$D(k)\leq 22$ for $k<10$. ∎

For $k\geq 11$, the bounds we obtain from repeated application of Theorem 10.7
are weaker than Vinberg’s bound $D(k)\leq 29$ [30].

##  11\. Further Directions

By the results presented in this paper, along with the earlier work of
Felikson and Tumarkin [12], the only dimension where compact Coxeter
$d$-polytopes with $d+4$ facets have not been classified is $d=6$. A list of
potential combinatorial types can be generated in the same manner as in
Section 3, but the large number of point set order types with $10$ points
makes this computationally challenging. With such a list in hand, the analysis
of each combinatorial type seems likely to be fairly straightforward, as was
the case in dimension $5$. The author plans to continue this work and is
hopeful that the computational difficulties can be handled.

We also provide many new examples of compact Coxeter polytopes in dimension
$4$ and $5$. This includes the first known example in dimension higher than
three with a dihedral angle of less than $\frac{\pi}{10}$, as well as the
first known example in dimension higher than three with an angle of
$\frac{\pi}{7}$. It may be interesting to further study the properties of many
of these polytopes, especially those that are essential.

In Section 10, we provide improved upper bounds on the dimension of compact
Coxeter $d$-polytopes with $d+k$ facets for $5\leq k\leq 10$. Thus far, there
are no compact Coxeter polytopes known in dimension larger than $8$. These
bounds can be viewed as further evidence that there are perhaps no higher
dimensional examples, or that such polytopes may be fairly complicated. It
seems quite likely that the bounds provided can be improved by a constant
factor with more detailed analysis. This may also be the case for the bound on
compact Coxeter $3$-free $d$-polytopes obtained in Section 9, as examples are
known only up through dimension $5$ (see, e.g., the cubes classified in [19]).
Already this has been achieved by Alexandrov [3] in showing $d\leq 12$, but
perhaps the bound can be improved further.

##  12\. Acknowledgements

The majority of this work was completed as part of the author’s thesis [8] for
the Mathematical Sciences Master of Science by Research program at Durham
University. The author would like to sincerely thank her advisor, Pavel
Tumarkin, for his expert support throughout the course of this research and
for introducing her to this fascinating topic. His thorough reading and
helpful suggestions have been crucial to the development of this work. She is
also grateful to Anna Felikson, Ruth Kellerhals, and Norbert Peyerimhoff for
their helpful comments and suggestions. The author extends her thanks to
Jiming Ma and Fangting Zheng, whose similar work helped her to correct a
minors errors in the list of polytopes. Additional thanks are due to the
Marshall Commission for making the author’s study in the UK possible.

## References

  * [1] Oswin Aichholzer, Franz Aurenhammer, and Hannes Krasser. Enumerating order types for small point sets with applications. _Order_ , 19 (2002), 265–281.
  * [2] Oswin Aichholzer and Hannes Krasser. The point set order type data base: a collection of applications and results. _In Proceedings of the 13th Annual Canadian Conference on Computational Geometry_ , Waterloo, Ontario, Canada (2001), 17–20.
  * [3] Stepan Alexandrov. Lannér diagrams and combinatorial properties of compact hyperbolic Coxeter polytopes. arXiv:2203.07248 [math.GT], (2022).
  * [4] Daniel Allcock. Infinitely many hyperbolic Coxeter groups through dimension 19. _Geometry & Topology_, 10 (2006), 737--758.
  * [5] Evgeniy M. Andreev. On convex polyhedra in Lobachevskii spaces. _Mathematics of the USSR-Sbornik_ , 10 (1970), 413--440.
  * [6] Richard Borcherds. Coxeter groups, Lorentzian lattices, and K3 surfaces. _International Mathematics Research Notices_ , 19 (1998), 1011--1031.
  * [7] Vadim Olegovich Bugaenko. Groups of automorphisms of unimodular hyperbolic quadratic forms over the ring $\mathbb{Z}\left[\frac{\sqrt{5}+1}{2}\right]$. _Moscow University Mathematics Bulletin_ , 39 (1984), 6--14.
  * [8] Amanda Burcroff. On Compact Coxeter Polytopes with Few Facets. _Durham University Master’s Thesis_ , http://etheses.dur.ac.uk/14202/, (2021).
  * [9] Harold Scott MacDonald Coxeter. Discrete groups generated by reflections. _Annals of Mathematics_ , 35 (1934), 588--621.
  * [10] Frank Esselmann. Über kompakte hyperbolische Coxeter-polytope mit wenigen facetten. _Universität Bielefeld Doctoral Dissertation_ , Sonderforschungsbereich 343 (1994), Preprint 94-087.
  * [11] Frank Esselmann. The classification of compact hyperbolic Coxeter $d$-polytopes with $d+2$ facets. _Commentarii Mathematici Helvetici_ 71 (1996), 229--242.
  * [12] Anna Felikson and Pavel Tumarkin. On compact hyperbolic $d$-polytopes with $d+4$ facets. _Transactions of the Moscow Mathematical Society_ , 69 (2008), 105--151.
  * [13] Anna Felikson and Pavel Tumarkin. On hyperbolic Coxeter polytopes with mutually intersecting facets. _Journal of Combinatorial Theory, Series A_ , 115 (2008), 121--146.
  * [14] Anna Felikson and Pavel Tumarkin. Coxeter polytopes with a unique pair of non-intersecting facets. _Journal of Combinatorial Theory, Series A_ , 116 (2009), 875--902.
  * [15] Anna Felikson and Pavel Tumarkin. Essential hyperbolic Coxeter polytopes. _Israel Journal of Mathematics_ , 199(1) (2014), 113--161.
  * [16] David Gale. Neighboring vertices on a convex polyhedron. In: _Linear Inequalities and Related Systems_ , Annals of Mathematics Studies, Princeton, Volume 38 (1956), 255--263.
  * [17] Branko Grünbaum and Geoffrey C. Shephard. Convex polytopes. _Bulletin of the London Mathematical Society_ , 1(3) (1969), 257--300.
  * [18] Branko Grünbaum and V. P. Sreedharan. An enumeration of simplicial 4-polytopes with 8 vertices. _Journal of Combinatorial Theory_ , 2 (1967), 437--465.
  * [19] Matthieu Jacquemet and Steven T. Tschantz. All hyperbolic Coxeter $n$-cubes. _Journal of Combinatorial Theory, Series A_ , 158 (2018), 387--406.
  * [20] I. M. Kaplinskaja. Discrete groups generated by reflections in the faces of simplicial prisms in Lobachevskian spaces. _Mathematical Notes of the Academy of Sciences of the USSR_ , 15(1) (1974), 88--91.
  * [21] Ruth Kellerhals. Hyperbolic orbifolds of minimal volume. _Computational Methods and Function Theory_ , 14(2-3) (2014), 465--481.
  * [22] Folke Lannér. On complexes with transitive groups of automorphisms. _Communications du Séminaire Mathématique de l’Université de Lund_ , 11 (1950), 1--71.
  * [23] Jiming Ma and Fangting Zheng. Compact hyperbolic Coxeter $4$-polytopes with $8$ facets. arXiv:2201.00154 [math.GT], (2022).
  * [24] Jiming Ma and Fangting Zheng. Compact hyperbolic Coxeter five-dimensional polytopes with nine facets. arXiv:2203.16049 [math.GT], (2022).
  * [25] Jiri Matousek. Lectures on Discrete Geometry. _Graduate Texts in Mathematics, Springer-Verlag_ , New York, Volume 212 (2013).
  * [26] Viacheslav V. Nikulin. On the classification of arithmetic groups generated by reflections in Lobachevskii spaces. _Mathematics of the USSR-Izvestiya_ , 18 (1982), 99--123.
  * [27] Mike Roberts. A classification of non-compact Coxeter polytopes with $n+3$ facets and one non-simple vertex. arXiv:1511.08451 [math.MG], (2020).
  * [28] Pavel Tumarkin. Compact hyperbolic Coxeter $n$-polytopes with $n+3$ facets. _The Electronic Journal of Combinatorics_ 14 (2007), R69.
  * [29] Ernest Borisovich Vinberg. Hyperbolic reflection groups. _Russian Mathematical Surveys_ , 40 (1985), 31--75.
  * [30] Ernest Borisovich Vinberg. The absence of crystallographic groups of reflections in Lobachevsky spaces of large dimensions. _Trudy Moskovskogo Matematicheskogo Obshchestva [Transactions of the Moscow Mathematical Society]_ , 47 (1984), 68--102.

##  Appendix A List of Combinatorial Types

The first table contains the missing face list of the $34$ possible
combinatorial types of compact hyperbolic $4$-polytopes with $8$ facets having
at least one pair of disjoint facets, as described in Subsection 3.2. The
second table contains the missing face list of the $111$ possible
combinatorial types of compact hyperbolic $5$-polytopes with $9$ facets having
at least two pairs of disjoint facets. Each list of missing faces is presented
in its lexicographically least form, with respect to relabellings of the
facets. A missing face $f=f_{i_{1}}\cap\dots\cap f_{i_{s}}$ is denoted by the
string $i_{1}\dots i_{s}$ where $i_{1}<\dots<i_{s}$.

Type | Missing Face List |  | Number of
---
Polytopes
$G_{1}$ | 01, 02, 03, 12, 14, 25, 3467, 3567, 4567 | 130
$G_{2}$ | 01, 02, 03, 12, 14, 2567, 34, 3567, 4567 | 115
$G_{3}$ | 01, 02, 03, 1245, 1456, 27, 36, 37, 4567 | 49
$G_{4}$ | 01, 23, 45, 67 | 12
$G_{5}$ | 01, 02, 13, 24, 34, 567 | 3
$G_{6}$ | 01, 02, 03, 124, 145, 26, 357, 367, 4567 | 2
$G_{7}$ | 01, 02, 03, 12, 14, 256, 347, 3567, 4567 | 2
$G_{8}$ | 01, 02, 03, 1245, 146, 257, 36, 37, 4567 | 1
$G_{9}$ | 01, 02, 03, 14, 25, 367, 4567 | 15
$G_{10}$ | 01, 02, 034, 134, 156, 256, 27, 347, 567 | 1
$G_{11}$ | 01, 02, 13, 245, 345, 67 | 8
$G_{12}$ | 01, 02, 034, 134, 15, 256, 267, 347, 567 | 4
$G_{13}$ | 01, 02, 034, 15, 26, 347, 567 | 4
$G_{14}$ | 01, 023, 145, 236, 237, 46, 57 | 2
$G_{15}$ | 01, 02, 03, 12, 145, 267, 345, 367, 4567 | 0
$G_{16}$ | 01, 02, 034, 125, 156, 27, 346, 347, 567 | 0
$G_{17}$ | 01, 02, 03, 124, 145, 267, 35, 367, 4567 | 0
$G_{18}$ | 01, 02, 03, 124, 125, 146, 257, 346, 357, 367, 4567 | 0
$G_{19}$ | 01, 02, 03, 124, 135, 145, 246, 267, 357, 367, 4567 | 0
$G_{20}$ | 01, 02, 034, 135, 156, 247, 26, 347, 567 | 0
$G_{21}$ | 01, 02, 134, 135, 246, 267, 346, 57 | 0
$G_{22}$ | 01, 02, 03, 124, 1456, 27, 356, 37, 4567 | 0
$G_{23}$ | 01, 02, 034, 134, 15, 25, 267, 3467, 567 | 0
Type | Missing Face List |  | Number of
---
Polytopes
$G_{24}$ | 01, 02, 034, 135, 16, 247, 26, 3457, 567 | 0
$G_{26}$ | 01, 023, 024, 156, 157, 234, 236, 356, 47, 567 | 0
$G_{27}$ | 01, 02, 034, 134, 135, 156, 247, 256, 267, 347, 567 | 0
$G_{28}$ | 01, 02, 034, 135, 136, 157, 246, 247, 257, 346, 567 | 0
$G_{29}$ | 01, 02, 034, 125, 136, 156, 247, 257, 346, 347, 567 | 0
$G_{30}$ | 01, 023, 024, 135, 156, 237, 247, 357, 46, 567 | 0
$G_{31}$ | 01, 023, 024, 035, 126, 157, 167, 234, 246, 345, 357, 467, 567 | 0
$G_{32}$ | 01, 023, 024, 035, 124, 146, 156, 237, 247, 356, 357, 467, 567 | 0
$G_{33}$ | 01, 023, 024, 035, 146, 157, 167, 234, 235, 246, 357, 467, 567 | 0
$G_{34}$ | 01, 023, 024, 035, 126, 137, 167, 245, 246, 345, 357, 467, 567 | 0
Type | Missing Face List |  | Number of
---
Polytopes
$H_{1}$ | 01, 02, 03, 12, 14, 25678, 34, 35678, 45678 | 22
$H_{2}$ | 01, 02, 03, 12456, 14567, 28, 37, 38, 45678 | 18
$H_{3}$ | 01, 02, 03, 12, 14, 256, 3478, 35678, 45678 | 6
$H_{4}$ | 01, 02, 03, 1245, 1456, 27, 368, 378, 45678 | 3
$H_{5}$ | 01, 02, 034, 134, 15, 256, 2678, 3478, 5678 | 1
$H_{6}$ | 01, 02, 03, 12, 14, 25, 34678, 35678, 45678 | 1
$H_{7}$ | 01, 02, 03, 12456, 1457, 267, 268, 38, 45678 | 0
$H_{8}$ | 01, 02, 03, 12456, 1457, 268, 37, 38, 45678 | 0
$H_{9}$ | 01, 02, 03, 12, 14, 2567, 348, 35678, 45678 | 0
$H_{10}$ | 01, 02, 03, 124, 14567, 28, 3567, 38, 45678 | 0
$H_{11}$ | 01, 02, 03, 1245, 14567, 28, 367, 38, 45678 | 0
$H_{12}$ | 01, 02, 034, 134, 15, 25, 2678, 34678, 5678 | 0
$H_{13}$ | 01, 02, 03, 12, 145, 267, 3458, 3678, 45678 | 0
$H_{14}$ | 01, 02, 03, 12, 145, 2678, 345, 3678, 45678 | 0
$H_{15}$ | 01, 02, 03, 124, 145, 2678, 35, 3678, 45678 | 0
$H_{16}$ | 01, 02, 034, 135, 16, 2478, 26, 34578, 5678 | 0
$H_{17}$ | 01, 02, 034, 1345, 16, 26, 278, 34578, 5678 | 0
$H_{18}$ | 01, 02, 03, 124, 125, 146, 2578, 346, 3578, 3678, 45678 | 0
$H_{19}$ | 01, 02, 03, 1245, 1346, 1456, 257, 278, 368, 378, 45678 | 0
$H_{20}$ | 01, 02, 03, 124, 1256, 147, 2568, 347, 3568, 378, 45678 | 0
$H_{21}$ | 01, 02, 03, 1245, 1456, 278, 36, 378, 45678 | 0
$H_{22}$ | 01, 02, 03, 1245, 1246, 1457, 268, 357, 368, 378, 45678 | 0
$H_{23}$ | 01, 02, 03, 1245, 146, 2578, 36, 378, 45678 | 0
$H_{24}$ | 01, 02, 03, 124, 1356, 1456, 247, 278, 3568, 378, 45678 | 0
$H_{25}$ | 01, 02, 03, 124, 1456, 27, 3568, 378, 45678 | 0
$H_{26}$ | 01, 02, 03, 124, 145, 26, 3578, 3678, 45678 | 0
$H_{27}$ | 01, 02, 03, 124, 125, 146, 257, 3468, 3578, 3678, 45678 | 0
$H_{28}$ | 01, 02, 03, 124, 135, 145, 246, 2678, 3578, 3678, 45678 | 0
$H_{29}$ | 01, 02, 03, 124, 1356, 145, 247, 278, 3568, 3678, 45678 | 0
$H_{30}$ | 01, 02, 03, 124, 145, 267, 358, 3678, 45678 | 0
$H_{31}$ | 01, 02, 03, 124, 1456, 278, 356, 378, 45678 | 0
$H_{32}$ | 01, 02, 03, 124, 1456, 278, 356, 378, 45678 | 0
$H_{33}$ | 01, 02, 03, 14, 25, 3678, 45678 | 0
Type | Missing Face List |  | Number of
---
Polytopes
$H_{34}$ | 01, 02, 03, 14, 256, 378, 45678 | 0
$H_{35}$ | 01, 02, 034, 15, 256, 267, 3478, 5678 | 0
$H_{36}$ | 01, 02, 034, 1256, 157, 268, 347, 348, 5678 | 0
$H_{37}$ | 01, 02, 034, 1345, 156, 267, 278, 348, 5678 | 0
$H_{38}$ | 01, 02, 13, 2456, 3456, 78 | 0
$H_{39}$ | 01, 02, 034, 134, 156, 2567, 278, 348, 5678 | 0
$H_{40}$ | 01, 02, 034, 125, 156, 278, 346, 3478, 5678 | 0
$H_{41}$ | 01, 02, 034, 135, 156, 2478, 267, 348, 5678 | 0
$H_{42}$ | 01, 023, 1456, 27, 38, 4567, 4568 | 0
$H_{43}$ | 01, 02, 034, 13, 1567, 248, 2567, 348, 5678 | 0
$H_{44}$ | 01, 02, 034, 125, 156, 27, 3468, 3478, 5678 | 0
$H_{45}$ | 01, 02, 034, 135, 136, 157, 2468, 2478, 2578, 346, 5678 | 0
$H_{46}$ | 01, 02, 034, 135, 16, 2478, 2678, 345, 5678 | 0
$H_{47}$ | 01, 02, 034, 134, 135, 156, 2478, 2567, 2678, 348, 5678 | 0
$H_{48}$ | 01, 02, 034, 135, 1567, 248, 267, 348, 5678 | 0
$H_{49}$ | 01, 02, 0345, 1346, 17, 258, 278, 3456, 678 | 0
$H_{50}$ | 01, 02, 034, 134, 1567, 2567, 28, 348, 5678 | 0
$H_{51}$ | 01, 02, 0345, 1345, 16, 267, 278, 3458, 678 | 0
$H_{52}$ | 01, 02, 0345, 1345, 1346, 167, 258, 267, 278, 3458, 678 | 0
$H_{53}$ | 01, 02, 0345, 1346, 137, 178, 2456, 258, 278, 3456, 678 | 0
$H_{54}$ | 01, 02, 0345, 1345, 136, 167, 2458, 267, 278, 3458, 678 | 0
$H_{55}$ | 01, 02, 034, 1256, 1567, 28, 347, 348, 5678 | 0
$H_{56}$ | 01, 02, 0345, 134, 136, 167, 2458, 2578, 267, 3458, 678 | 0
$H_{57}$ | 01, 02, 034, 1345, 16, 267, 278, 3458, 5678 | 0
$H_{58}$ | 01, 02, 0345, 1346, 1347, 168, 257, 258, 268, 3457, 678 | 0
$H_{59}$ | 01, 02, 034, 135, 156, 2478, 26, 3478, 5678 | 0
$H_{60}$ | 01, 023, 024, 135, 156, 2467, 2478, 38, 4567, 5678 | 0
$H_{61}$ | 01, 02, 034, 125, 126, 157, 268, 3457, 3468, 3478, 5678 | 0
$H_{62}$ | 01, 023, 024, 1356, 1567, 238, 248, 3568, 47, 5678 | 0
$H_{63}$ | 01, 02, 034, 1256, 137, 1567, 248, 2568, 347, 348, 5678 | 0
$H_{64}$ | 01, 02, 0345, 16, 27, 3458, 678 | 0
$H_{65}$ | 01, 02, 0345, 134, 167, 258, 267, 3458, 678 | 0
$H_{66}$ | 01, 023, 024, 156, 237, 3567, 48, 5678 | 0
Type | Missing Face List |  | Number of
---
Polytopes
$H_{67}$ | 01, 02, 134, 135, 146, 2578, 2678, 357, 468 | 0
$H_{68}$ | 01, 02, 034, 134, 15, 2567, 2678, 348, 5678 | 0
$H_{69}$ | 01, 02, 034, 134, 135, 156, 2478, 256, 2678, 3478, 5678 | 0
$H_{70}$ | 01, 02, 034, 135, 1367, 158, 2467, 248, 258, 3467, 5678 | 0
$H_{71}$ | 01, 02, 034, 125, 1567, 28, 3467, 348, 5678 | 0
$H_{72}$ | 01, 02, 034, 135, 136, 157, 2468, 2478, 257, 3468, 5678 | 0
$H_{73}$ | 01, 02, 034, 135, 16, 2478, 267, 3458, 5678 | 0
$H_{74}$ | 01, 02, 034, 1345, 156, 167, 2348, 267, 278, 3458, 5678 | 0
$H_{75}$ | 01, 02, 034, 1345, 136, 167, 2458, 267, 278, 3458, 5678 | 0
$H_{76}$ | 01, 02, 034, 1345, 1356, 167, 248, 267, 278, 3458, 5678 | 0
$H_{77}$ | 01, 02, 034, 1345, 1567, 267, 28, 348, 5678 | 0
$H_{78}$ | 01, 02, 034, 1345, 1346, 157, 257, 268, 278, 3468, 5678 | 0
$H_{79}$ | 01, 02, 034, 1345, 156, 26, 278, 3478, 5678 | 0
$H_{80}$ | 01, 023, 024, 1356, 1567, 247, 248, 38, 4567, 5678 | 0
$H_{81}$ | 01, 02, 0345, 126, 1347, 167, 258, 268, 3457, 3458, 678 | 0
$H_{82}$ | 01, 023, 024, 156, 157, 2348, 2368, 3568, 47, 5678 | 0
$H_{83}$ | 01, 02, 034, 125, 136, 156, 2478, 2578, 346, 3478, 5678 | 0
$H_{84}$ | 01, 023, 024, 135, 156, 2378, 2478, 3578, 46, 5678 | 0
$H_{85}$ | 01, 023, 024, 135, 1567, 2467, 248, 38, 4567, 5678 | 0
$H_{86}$ | 01, 02, 034, 135, 136, 1578, 246, 2478, 2578, 346, 5678 | 0
$H_{87}$ | 01, 023, 024, 1356, 157, 2368, 248, 3568, 47, 5678 | 0
$H_{88}$ | 01, 02, 034, 1256, 1357, 1567, 248, 268, 347, 348, 5678 | 0
$H_{89}$ | 01, 02, 034, 1345, 1356, 1567, 248, 267, 278, 348, 5678 | 0
$H_{90}$ | 01, 02, 034, 125, 1346, 156, 257, 278, 3468, 3478, 5678 | 0
$H_{91}$ | 01, 023, 024, 156, 1578, 234, 2378, 3578, 46, 5678 | 0
$H_{92}$ | 01, 02, 034, 134, 1356, 1567, 248, 2567, 278, 348, 5678 | 0
$H_{93}$ | 01, 02, 034, 125, 136, 156, 2478, 257, 3468, 3478, 5678 | 0
$H_{94}$ | 01, 02, 134, 135, 2467, 2678, 3467, 58 | 0
$H_{95}$ | 01, 02, 134, 1356, 2567, 278, 3567, 48 | 0
$H_{96}$ | 01, 023, 024, 1567, 1568, 234, 237, 3567, 48, 5678 | 0
$H_{97}$ | 01, 02, 034, 135, 167, 248, 267, 3458, 5678 | 0
$H_{98}$ | 01, 02, 034, 134, 156, 256, 278, 3478, 5678 | 0
$H_{99}$ | 01, 02, 034, 15, 26, 3478, 5678 | 0
Type | Missing Face List |  | Number of
---
Polytopes
$H_{100}$ | 01, 02, 034, 134, 135, 1567, 248, 2567, 2678, 348, 5678 | 0
$H_{101}$ | 01, 02, 034, 12, 156, 278, 3456, 3478, 5678 | 0
$H_{102}$ | 01, 02, 13, 24, 34, 5678 | 0
$H_{103}$ | 01, 023, 145, 236, 2378, 46, 578 | 0
$H_{104}$ | 01, 023, 1456, 237, 238, 457, 68 | 0
$H_{105}$ | 01, 02, 134, 135, 246, 2678, 346, 578 | 0
$H_{106}$ | 01, 02, 034, 15, 267, 348, 5678 | 0
$H_{107}$ | 01, 02, 134, 156, 278, 347, 568 | 0
$H_{108}$ | 01, 02, 134, 256, 3456, 78 | 0
$H_{109}$ | 01, 23, 45, 678 | 0
$H_{110}$ | 01, 02, 13, 245, 345, 678 | 0
$H_{111}$ | 01, 023, 145, 236, 456, 78 | 0

See pages - of polytope_list.pdf


# A Distributionally Robust Approach to Shannon Limits using the Wasserstein
Distance

Vikrant Malik, Taylan Kargin, Victoria Kostina, Babak Hassibi
Department of Electrical Engineering
Caltech
Pasadena, CA, USA
Email: {vmalik, tkargin, vkostina<EMAIL_ADDRESS>
###### Abstract

We consider the rate-distortion function for lossy source compression, as well
as the channel capacity for error correction, through the lens of
distributional robustness. We assume that the distribution of the source or of
the additive channel noise is unknown and lies within a Wasserstein-2
ambiguity set of a given radius centered around a specified nominal
distribution, and we look for the worst-case asymptotically optimal coding
rate over such an ambiguity set. Varying the radius of the ambiguity set
allows us to interpolate between the worst-case and stochastic scenarios using
probabilistic tools. Our problem setting fits into the paradigm of compound
source / channel models introduced by Sakrison [1] and Blackwell [2],
respectively. This paper shows that if the nominal distribution is Gaussian,
then so is the worst-case source / noise distribution, and the compound rate-
distortion / channel capacity functions admit convex formulations with Linear
Matrix Inequality (LMI) constraints. These formulations yield simple closed-
form expressions in the scalar case, offering insights into the behavior of
Shannon limits with the changing radius of the Wasserstein-2 ambiguity set.

_Keywords-_ distributionally robust compression, universal compression,
Wasserstein distance, lossy source coding, rate-distortion function,
distributionally robust coding, compound channel.

##  I Introduction

###  I-A Literature context

Rapid technological advancements in recent years have spurred a significant
increase in data production and usage. Major technological forces driving this
data era include 5G/6G, the Internet of Things, machine learning, and
autonomous vehicles. Core to these technologies are compression and
reconstruction algorithms, which provide essential means for data storage and
transmission. For example, video streaming services require efficient data
compression, yet the source distribution can vary greatly. Similarly,
autonomous vehicles depend on sensor data, which is prone to distributional
shifts that can lead to critical errors if not adequately addressed. In
machine learning, models are often trained on a dataset that has undergone
compression and decompression. These applications underscore the need for
compression and error correction schemes that are resilient to distributional
changes.

Variable-length universal codes that adapt their encoding rate to the source /
noise distribution they observe have been a topic of longstanding interest in
the information theory community. Perhaps the most famous of these is the
Lempel-Ziv family of lossless codes [3, 4, 5] that learn the source
distribution on the fly, while asymptotically achieving the entropy rate of
the source. Lempel-Ziv codes have also been extended to apply to lossy
compression [6, 7]. An approach to universal lossy compression that utilizes
Markov chain Monte Carlo with the reconstruction alphabet changing over time
is proposed in [8] (continuous sources),[9] (finite alphabet sources).
Variable-rate universal codes for channel coding are presented in [10, 11, 12,
13, 14].

The idea that enables the aforementioned coding strategies [3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14] is that of variable-length coding, i.e., the length of
the codeword being transmitted is adapted to the data that is being seen.
However, many physical systems and much of coding theory require all codewords
to be of the same length. In that scenario, the relevant figure of merit is
the worst-case performance over a family of source / noise distributions,
known as _compound_ rate-distortion function / channel capacity-cost function,
and the corresponding asymptotic fundamental limits are given by minimax
convex optimization problems [1], [2]. In the context of compression, [15]
considers the distributional class of stationary random processes with bounded
$4^{th}$ order moment, whereas [16] examines a class of sources determined by
spectral capacities. In the context of error correction, [17] extends the
compound channel capacity formula of [2] to random coding, to arbitrarily
varying channels (AVCs), and to adversarial channels, [18] shows the worst-
case capacity of a class of arbitrarily varying Gaussian channels, and [19]
studies compound capacity of broadcast channels; see [20] for a survey.

In this work, we employ Wasserstein-2 ($\operatorname{W_{2}}$) distance as the
measure of distributional shifts from a nominal distribution to define a
distributional family. The $\operatorname{W_{2}}$-distance between
distributions $P_{1},P_{2}$ on $\mathbb{R}^{d}$ is defined as [21]

$\displaystyle\operatorname{W_{2}}(P_{1},P_{2})\coloneqq\left({\inf_{P_{XY}\in\Pi(P_{1},P_{2})}\mathbb{E}\left[\|{X-Y}\|_{\text{}}^{2}\right]}\right)^{\tfrac{1}{2}},$
(1)

where $\Pi(P_{1},P_{2})$ denotes the set of all joint distributions with
marginals $P_{1}$ and $P_{2}$.

In contrast to other commonly used statistical distances such as total-
variation distance, Kullback–Leibler divergence, Hellinger distance, the
$\operatorname{W_{2}}$-distance incorporates information from the geometric
structure of the underlying domain, making it more suitable for handling
structured real-world data. Furthermore, the $\operatorname{W_{2}}$-distance
accounts for the cost of transporting mass from one probability distribution
to another. This makes the $\operatorname{W_{2}}$-distance a particularly
suitable tool for quantifying robustness in communication systems, as it
reflects the potential impact of variations in signal distributions on the
fidelity of communication. For instance, in scenarios where small
perturbations in a signal could lead to disproportionately large errors, the
$\operatorname{W_{2}}$-distance provides a measure of how these perturbations
affect system performance. This makes it a natural choice for modeling
scenarios where the goal is to maintain high fidelity in the presence of
uncertain or varying signal distributions, thereby enhancing the reliability
and efficiency of communication systems under distributionally robust
frameworks.

Owing to its geometric interpretability and tractable formulation,
$\operatorname{W_{2}}$-distance has recently gained popularity as a
statistical distance in diverse fields such as control [22], filtering [23],
and machine learning [24]. In [25], a controller that minimizes the worst-case
regret across all disturbance distributions within a
$\operatorname{W_{2}}$-ambiguity set is proposed. The controller’s parameters
are obtained via a solution to a semi-definite program (SDP), which is
formulated leveraging the tractability of $\operatorname{W_{2}}$-distance.
Unlike prior robust control approaches, such as $H_{\infty}$ [26], where the
controller is designed to minimize worst-case cost against an adversarially
generated disturbance, and regret-optimal control [27], where the controller
is designed to minimize the regret with respect to a hypothetical optimal
noncausal controller, the controller in [25] is designed to attain the desired
level of robustness via adjusting the size of the ambiguity set. Additionally,
[25] demonstrates that the worst-case disturbance follows a Gaussian
distribution if the nominal distribution is Gaussian. Subsequent contributions
[28] and [22] extend the framework in [25] to control scenarios involving
measurement noise and infinite horizon, respectively. In the domain of lossy
source coding, [29] trains a deep neural network compressor that achieves
distributional robustness by incorporating $\operatorname{W_{2}}$
transportation cost into the optimization problem. The
$\operatorname{W_{2}}$-distance has also been used to measure the perceptual
quality of the decompressed message [30] using what is called the Rate-
Distortion-Perception (RDP) function. The work [31] characterizes the
analytical bounds for the Gaussian RDP function.

###  I-B Contributions

We investigate the minimax rate-distortion function (RDF) formulated in [1]
and the minimax capacity formulated in [2] for an unknown source / noise
distribution residing within a $\operatorname{W_{2}}$-ambiguity set centered
at a given nominal distribution. In the case of source compression, we assume
that the source distributions in the ambiguity set have a finite
$2\\!+\\!\epsilon$-th moment for an arbitrarily small $\epsilon\\!>\\!0$. The
finiteness of $(2\\!+\\!\epsilon)$-th moment is a common assumption on the
source distributions in rate-distortion theory to control the growth of the
mean square error distortion (see [32, Sec. 23.3]).

In the case of a Gaussian nominal source distribution, we show that the worst-
case source / noise distribution in the $\operatorname{W_{2}}$ ambiguity set
is also Gaussian. To do so, we leverage the Gelbrich bound [33, Thm. 2.1] on
the $\operatorname{W_{2}}$ distance and the Gaussian saddle point properties
of mutual information [32, Thm. 5.11]. Our analysis reveals an expression of
the minimax rate-distortion function / channel capacity solely in terms of the
covariance matrices of distributions within the ambiguity set and the radius
of the $\operatorname{W_{2}}$-ball. Adjusting the radius of the
$\operatorname{W_{2}}$-ball enables a gradual interpolation from a known
nominal source distribution (at a radius of 0) to an uncertain distribution as
the radius increases. In the scalar case, we derive closed-form expressions
demonstrating the effect of the varying radius on those fundamental limits.

Notation. The set of real numbers is denoted by $\mathbb{R}$. For a real-
valued function $f$, we denote $f^{+}(\cdot)\coloneqq\max\\{0,f(\cdot)\\}$.
For a vector $x\in\mathbb{R}^{d}$, we denote by $\|{x}\|_{\text{}}$, the
Euclidean norm of $x$. For a matrix $A\in\mathbb{R}^{d\times m}$, its
transpose is denoted by $A^{T}\in\mathbb{R}^{m\times d}$. For square matrices,
$\operatorname{tr}(\cdot)$ and $|{\cdot}|$ are the trace and the determinant
operation. The notations $\mathbb{S}_{+}^{d}$ and $\mathbb{S}_{++}^{d}$
represent the sets of $d\times d$ symmetric, positive semidefinite and
positive definite matrices, respectively. For two positive semidefinite
matrices, $\succeq$ denotes the Löwner order. The set of all probability
distributions over $\mathbb{R}^{n}$ with bounded $p^{\textrm{th}}$-moment is
denoted by $\mathcal{P}_{p}(\mathbb{R}^{n})$. For a random variable $X$ over
$\mathbb{R}^{n}$, we denote its probability distribution by $P_{X}$. The
conditional distribution of a random variable $Y$ given $X$ is denoted by
$P_{Y|X}$. The expectation with respect to the distribution $P_{X}$ is denoted
by $\operatorname{\mathbb{E}}_{P_{X}}[\cdot]$. The Gaussian distribution with
mean $\mu\in\mathbb{R}^{d}$ and covariance $\Sigma\in\mathbb{S}_{+}^{d}$ is
denoted by $\operatorname{\mathcal{N}}(\mu,\Sigma)$. The mutual information
between random variables $X$ and $Y$ is denoted by $I(X;Y)$. The differential
entropy of $X$ is denoted by $h(X)$, and the conditional differential entropy
of $X$ given $Y$ is given by $h(X|Y)$.

##  II Main results

In this section, we state our main results$\colon$ Theorem II.1 shows an SDP
for the worst-case RDF defined in (2), below, and Theorem II.3 shows an SDP
for the worst-case capacity, defined in (14).

###  II-A Source Compression

Fix $\epsilon>0$. Consider a source that generates i.i.d. symbols
$X_{i}\in\mathbb{R}^{d}$ following an unknown probability distribution
$P_{X}\in\mathcal{S}$, where
$\mathcal{S}\subseteq\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})$ is a
distributional family. An $n$-block of source symbols
$X^{n}=(X_{1},\ldots,X_{n})$ is mapped into one of the $\exp(nR)$ distinct
codewords $\widehat{X}^{n}=(\widehat{X}_{1},\ldots,\widehat{X}_{n})$ while
satisfying the average distortion constraint
$\frac{1}{n}\sum_{i=1}^{n}\operatorname{\mathbb{E}}[\|{X_{i}-\widehat{X}_{i}}\|_{\text{}}^{2}]\leq
D$.

The minimum universally achievable coding rate $R_{\mathcal{S},n}(D)$ is
defined as the minimum $R$ at which such a mapping exists, regardless of the
$P_{X}\in\mathcal{S}$. The minimum asymptotically achievable universal coding
rate is the operational compound RDF [1],
$R_{\mathcal{S}}(D)=\lim\sup_{n\to\infty}R_{\mathcal{S},n}(D)$. Sakrison [1]
established the following single-letter formula for the compound RDF:

$R_{\mathcal{S}}(D)=\inf_{\begin{subarray}{c}P_{\hat{X}|X}\colon\mathbb{R}^{d}\mapsto\mathbb{R}^{d}\\\
\mathbb{E}\left[\|X-\widehat{X}\|^{2}\right]\leq
D\end{subarray}}\sup_{P_{X}\in\mathcal{S}}I(X;\widehat{X}).$ (2)

The achievability result of the coding theorem in (2) assumes that the class
of distributions $\mathcal{S}$ is compact, a notion defined by [1] as follows:
a class of distributions $\mathcal{S}$ is compact if, for any $\epsilon>0$,
there is a totally bounded set $\mathcal{K}\subset\mathbb{R}^{d}$ and a
function $f\colon\mathbb{R}^{d}\to\mathbb{R}^{d}$ with range $\mathcal{K}$
such that,

$\sup_{P_{X}\in\mathcal{S}}\mathbb{E}_{P_{X}}\left[\|{X-f(X)}\|_{\text{}}^{2}\right]\leq\epsilon.$
(3)

Any class of distributions with bounded $2+\epsilon$ order moments for
$\epsilon>0$ satisfies the compactness definition given in [1]. However, the
distributions in the $\operatorname{W_{2}}$-ball do not necessarily satisfy
this condition. Therefore, to ensure that the function on the right side of
(2), whose computation constitutes one of our main results, has an operational
meaning, we consider only those distributions in the
$\operatorname{W_{2}}$-ball that have bounded $2+\epsilon$ order moments.

Our main result for source compression computes the compound rate-distortion
function (2) for the $\operatorname{W_{2}}$-ambiguity set of distributions
$\mathcal{S}=\left\\{{P\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})\mid\operatorname{W_{2}}(P,\,P_{\circ})\leq
r}\right\\}$. For brevity, we denote the compound rate-distortion function
with such a choice of the ambiguity set by

$\displaystyle R_{P_{\circ}}(D,r)\coloneqq R_{\mathcal{S}}(D).$ (4)

If $r=0$, (4) reduces to the rate-distortion function of the known
distribution $P_{\circ}$. In our analysis, we assume a Gaussian nominal
distribution.

To set the stage for our result, we denote the Bures-Wasserstein metric on the
positive semi-definite cone $\mathbb{S}_{+}^{d}$ [34] as,

$\operatorname{BW}(\Sigma,\Sigma_{\circ})\\!\coloneqq\\!\left(\operatorname{tr}(\Sigma)\\!+\\!\operatorname{tr}(\Sigma_{\circ})\\!-\\!2\operatorname{tr}(\Sigma^{\frac{1}{2}}\Sigma_{\circ}\Sigma^{\frac{1}{2}})\right)^{1/2}.$
(5)

Moreover, note that the RDF of a $d-$dimensional multivariate Gaussian vector
$X\stackrel{{\scriptstyle\text{}}}{{\sim}}\operatorname{\mathcal{N}}(0,\Sigma)$
is given by [35, Eqn. (13)]$\colon$

$\displaystyle
R_{\operatorname{\mathcal{N}}(0,\Sigma)}(D)=\inf_{\begin{subarray}{c}A\in\mathbb{R}^{d\times
d},\Sigma_{Z}\succeq 0\colon\\\
\operatorname{tr}((A\\!-\\!I)\Sigma(A\\!-\\!I)^{T}\\!+\\!\Sigma_{Z})\leq
D\end{subarray}}\frac{1}{2}\log\frac{\left|A\Sigma
A^{T}+\Sigma_{Z}\right|}{\left|\Sigma_{Z}\right|}.$ (6)

The reconstructed message $\widehat{X}$ follows the forward law
$\widehat{X}=AX+Z$, where
$Z\stackrel{{\scriptstyle\text{}}}{{\sim}}\operatorname{\mathcal{N}}(0,\Sigma_{Z})$
is independent of $X$. The solution to (6) is given by reverse-waterfilling on
the eigenvalues [36, Thm. 10.3.3]. If $d=1$, the RDF in (6) takes the form
(9), below.

######  Theorem II.1 (Compound RDF for $\operatorname{W_{2}}$ ambiguity set)

The compound RDF (4) with a Gaussian center
$P_{\circ}=\mathcal{N}\left(0,\Sigma_{\circ}\right)$ is given as,

$\displaystyle R_{P_{\circ}}(D,r)$
$\displaystyle\\!=\\!\sup_{\begin{subarray}{c}\Sigma\succeq 0,\\\
\operatorname{BW}(\Sigma,\Sigma_{\circ})\leq
r\end{subarray}}R_{\operatorname{\mathcal{N}}(0,\Sigma_{\circ})}(D),$ (7)

where the function $R_{P_{\circ}}(D,r)$ is achieved by a Gaussian $P_{X}$.

###### Proof:

We first refer to [1] to establish strong duality, see Lemma II.2, below. We
then present an upper bound on the compound RDF and show that it is achieved
by a Gaussian source distribution in the $\operatorname{W_{2}}$-ball if the
nominal source distribution $P_{\circ}$ is Gaussian. This extends the
classical result [35, Eqn. (13)] showing that, among all distributions with a
fixed second-order moment, a Gaussian source achieves the largest single
source RDF (See Section III for details). ∎

######  Lemma II.2 (Strong duality of the compound RDF)

The compound RDF (4) admits a dual formulation given by

$R_{P_{\circ}}(D,r)\\!=\\!\\!\sup_{\begin{subarray}{c}P_{X|X_{\circ}}\colon\mathbb{R}^{d}\mapsto\mathbb{R}^{d}\\\
P_{X}\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})\\\
\mathbb{E}\left[\|{X\\!-\\!X_{\circ}}\|_{\text{}}^{2}\right]\leq
r^{2}\end{subarray}}\inf_{\begin{subarray}{c}P_{\hat{X}|X}\colon\mathbb{R}^{d}\mapsto\mathbb{R}^{d}\\\
\mathbb{E}\left[\|{X-\widehat{X}}\|_{\text{}}^{2}\right]\leq
D\end{subarray}}I(X;\widehat{X}),$ (8)

where $X_{\circ}\sim P_{\circ}$.

###### Proof:

The result follows via an application of [1, Thm. Source Encoding] to mean
square error and a $\operatorname{W_{2}}$ ambiguity set. ∎

In (8), the nominal source $X_{\circ}\sim P_{\circ}$, the worst-case source
$X$ and the reconstructed signal $\widehat{X}$ can be regarded as a Markov
chain:

$X_{\circ}\xrightarrow{P_{X|X_{\circ}}}X\xrightarrow{P_{\hat{X}|X}\,}\widehat{X}.$

We can interpret (8) as a Nash equilibrium of a zero-sum game between two
competing channels: while the channel $P_{X|X_{\circ}}$ adversarially
maximizes the compression rate from $X$ to $\widehat{X}$ under the
transportation cost $\mathbb{E}\|{X\\!-\\!X_{\circ}}\|_{\text{}}^{2}\leq
r^{2}$ from the nominal source to "deceive" the encoder-decoder channel
$P_{\hat{X}|X}$, the channel $P_{\hat{X}|X}$ minimizes the compression rate
from $X$ to $\widehat{X}$ under the distortion constraint
$\mathbb{E}\|{X\\!-\\!\widehat{X}}\|_{\text{}}^{2}\leq D$ by assuming the
worst-case source from $P_{X|X_{\circ}}$.

To elucidate the tradeoff exposed in Theorem II.1, consider a scalar-source
RDF with an unknown distribution from a $\operatorname{W_{2}}$-ambiguity set
centered at $P_{\circ}=\mathcal{N}(0,\sigma^{2}_{\circ})$. First, recall the
RDF of a scalar Gaussian source [36, Eqn. (10.36)]:

$\displaystyle
R_{\operatorname{\mathcal{N}}(0,\sigma^{2})}(D)=\frac{1}{2}\log^{+}\frac{\sigma^{2}}{D}.$
(9)

Second, observe that the Bures-Wasserstein distance (5) between scalars is,

$\displaystyle\operatorname{BW}(\sigma^{2},\sigma^{2}_{\circ})=|\sigma-\sigma_{\circ}|.$
(10)

We now apply Theorem II.1. The compound RDF for the scalar case, using (7), is
given as,

$\displaystyle R_{\mathcal{N}(0,\sigma^{2}_{\circ})}(D,r)$
$\displaystyle=\sup_{|\sigma-\sigma_{\circ}|\leq
r}R_{\operatorname{\mathcal{N}}(0,\sigma^{2})}(D)$ (11)
$\displaystyle=\sup_{|\sigma-\sigma_{\circ}|\leq
r}\frac{1}{2}\log^{+}\frac{\sigma^{2}}{D}$ (12)
$\displaystyle=\frac{1}{2}\log^{+}\frac{(\sigma_{\circ}+r)^{2}}{D}.$ (13)

The expression (13) is immediate due to the fact that the logarithm is
monotonic. Note that for $r=0$, the compound RDF is the Shannon RDF for
$P_{\circ}$, and for $r>0$, it is the Shannon RDF for
$P_{X}=\mathcal{N}(0,(\sigma_{\circ}+r)^{2})$. Thus, as the radius of the
ambiguity set increases, the required number of bits to achieve the same
distortion increases.

Figure 1: The scalar compound capacity for $P_{\circ}=\mathcal{N}(0,1)$ for
$r=0$. The scalar compound capacity for $r=0$ is the Shannon capacity for
$P_{\circ}$ and for $r>0$ is the Shannon capacity for
$P_{Z}=\mathcal{N}(0,(1+r)^{2})$. As the radius of the ambiguity set
increases, the required input power $B$ to achieve the same capacity
increases.

###  II-B Channel Coding

Consider transmission of an equiprobable message
$W\in\left\\{1,\ldots,\exp(nR)\right\\}$ over an i.i.d. additive noise
channel, which, upon receiving $X_{i}\in\mathbb{R}^{d}$, outputs
$Y_{i}\in\mathbb{R}^{d}$, where $Y_{i}=HX_{i}+Z_{i}$, with $Z_{i}\sim P_{Z}$
independent of each other and of $X^{i}=(X_{1},\ldots,X_{i})$, and $H$ is
fixed. Here, $P_{Z}\in\mathcal{S}$ is fixed but unknown. The encoder
injectively maps $W$ to a codeword $X^{n}$ under the average power constraint
$\frac{1}{n}\sum_{i=1}^{n}\mathbb{E}\|X_{i}\|^{2}\leq B$. The codeword is
transmitted over the channel, and, upon receiving an $n$-block of channel
outputs $Y^{n}\\!=\\!(Y_{1},\ldots,Y_{n})$, the decoder outputs $\widehat{W}$,
an estimate of $W$.

The maximum universally achievable coding rate $C_{\mathcal{S},n}(B,\epsilon)$
compatible with average error probability
$\mathbb{P}\left[W\neq\widehat{W}\right]\leq\epsilon$ is defined as the
maximum rate $R$ for which such an encoder-decoder mapping exists, regardless
of $P_{Z}\in\mathcal{S}$. The maximum asymptotically achievable universal
coding rate is the operational compound capacity-cost function [2],
$C_{\mathcal{S},n}(B)=\lim_{\epsilon\to
0}\lim\inf_{n\to\infty}C_{\mathcal{S},n}(B,\epsilon)$. Blackwell [2]
established a single-letter formula for the compound capacity-cost function of
a discrete memoryless channel, which was extended to continuous alphabet
domain in [37, 38]$\colon$

$C_{\mathcal{S}}(B)=\sup_{\begin{subarray}{c}P_{X}\text{ on
}\mathbb{R}^{d}:\\\ \operatorname{tr}(\Sigma)\leq
B\end{subarray}}\inf_{\begin{subarray}{c}P_{Z}\in\mathcal{S}\end{subarray}}I(X;HX+Z),$
(14)

where $\Sigma$ is the covariance of $X\sim P_{X}$. Our main result for channel
coding computes the compound capacity (14) for the
$\operatorname{W_{2}}$-ambiguity set of additive channel noises

$\displaystyle\mathcal{S}=\left\\{{P\in\mathcal{P}_{2}(\mathbb{R}^{d})\mid\operatorname{W_{2}}(P,\,P_{\circ})\leq
r}\right\\}.$ (15)

Here, we assume that the nominal distribution
$P_{\circ}\in\mathcal{P}_{2}(\mathbb{R}^{d})$ to ensure weak compactness of
$\mathcal{S}$ [39, Thm. 1]. This assumption entails
$P\in\mathcal{P}_{2}(\mathbb{R}^{d})$ [39, Lem. 1] for all $P$ in the
$\operatorname{W_{2}}$ ball. For brevity, we denote the compound capacity-cost
function with such a choice of the ambiguity set by

$\displaystyle C_{P_{\circ}}(B,r)\coloneqq C_{\mathcal{S}}(B).$ (16)

Our problem setting satisfies the regularity conditions [37, H1-H4]$\colon$

  1. 1.

The input and output alphabets as well as the set of states (which correspond
to the probability measures in the $\operatorname{W_{2}}$ ball equipped with
the $\operatorname{W_{2}}$ distance) are separable metric spaces, and the
output alphabet is complete.

  2. 2.

The channel depends continuously on the input and states, i.e., for a sequence
of inputs $X_{n}\rightarrow X$ and states $P_{Z_{n}}\rightarrow P_{Z}$,
$P_{Y|X,P_{Z}}(\cdot|X_{n},P_{Z_{n}})$ converges weakly to
$P_{Y|X,P_{Z}}(\cdot|X,P_{Z})$. Here, $P_{Y|X,P_{Z}}(\cdot|X,P_{Z})$
represents a channel with a given input $X$ and a fixed noise distribution
$P_{Z}$ in the $\operatorname{W_{2}}$ ball. This follows from the fact that
the $\operatorname{W_{2}}$-ball is weakly compact whenever the nominal
distribution has a finite $2$-nd order moment [39, Thm. 1].

  3. 3.

The constraint function $\|{\cdot}\|_{\text{}}^{2}$ on the input is Borel
measurable.

  4. 4.

There exists a sequence of input alphabets that satisfy the given power
constraint.

The validity of the Blackwell formula (14) ensures that the function on the
right side of (14), whose computation constitutes one of our main results, has
an operational meaning.

Note that the capacity-cost function for a $d$-dimensional multivariate
Gaussian noise vector $Z_{g}\sim\mathcal{N}(0,\Sigma_{Z})$ is given by (See
[40, Thm. 9.1] and Lemma B.1 in Appendix B below),

$\displaystyle C_{\mathcal{N}(0,\Sigma_{Z})}(B)=$
$\displaystyle\sup_{\begin{subarray}{c}\Sigma\succeq 0\colon\\\
\text{tr}(\Sigma)\leq B\end{subarray}}\log\frac{|\Sigma_{Z}+H\Sigma
H^{T}|}{|\Sigma_{Z}|}.$ (17)

######  Theorem II.3 (Compound capacity-cost function for
$\operatorname{W_{2}}$ ambiguity set)

The compound capacity (16) with a Gaussian center
$P_{\circ}=\mathcal{N}\left(0,\Sigma_{\circ}\right)$ is given as,

$\displaystyle C_{P_{\circ}}(B,r)=$
$\displaystyle\inf_{\begin{subarray}{c}\Sigma_{Z}\succeq 0\\\
\operatorname{BW}(\Sigma_{Z},\Sigma_{\circ})\leq
r\end{subarray}}C_{\mathcal{N}(0,\Sigma_{Z})}(B).$ (18)

###### Proof:

The proof of Theorem II.3 is along the same lines as that of Theorem II.1. We
leverage the fact that Gaussian noise minimizes capacity for a given noise
covariance (See Lemma B.2 in Appendix B below). This helps us write the
compound capacity in terms of the second-order statistics of the distributions
in the $\operatorname{W_{2}}$ ball. The operational meaning of Gaussian being
the worst-case noise is discussed in [41]. See Appendix B for details. Also
note that a Gaussian nominal distribution ensures that distributions in the
$\operatorname{W_{2}}$-ball have bounded $2$-nd order moments [39, Lem. 1]. ∎

###### Lemma II.4

The compound capacity in (14) admits a dual formulation given by

$\displaystyle C_{P_{\circ}}(B,r)$
$\displaystyle\\!=\\!\\!\inf_{\begin{subarray}{c}P_{Z|Z_{\circ}}\colon\mathbb{R}^{d}\mapsto\mathbb{R}^{d}\\\
P_{Z}\in\mathcal{P}_{2}(\mathbb{R}^{d})\\\
\mathbb{E}\left[\|{Z-Z_{\circ}}\|_{\text{}}^{2}\right]\leq
r^{2}\end{subarray}}\sup_{\begin{subarray}{c}P_{X}\text{ on
}\mathbb{R}^{d}\colon\\\ \mathbb{E}\left[\|{X}\|_{\text{}}^{2}\right]\leq
B\end{subarray}}I(X;HX+Z).$ (19)

where the $\inf$ is achieved by a Gaussian noise distribution.

###### Proof:

The result follows from [37, Thm. 5], where the authors prove the above result
for the case of AVCs, which is a more general case of the setting that we
consider. ∎

Consider the compound capacity of a scalar additive channel with an unknown
additive noise distribution drawn from a $\operatorname{W_{2}}$-ambiguity set
centered at $P_{\circ}=\mathcal{N}(0,\sigma^{2}_{\circ})$. First, recall the
capacity of a scalar Gaussian channel [36, Eqn. (9.17)]:

$\displaystyle C_{\mathcal{N}(0,\sigma^{2}_{\circ})}(B)$
$\displaystyle=\frac{1}{2}\log\left(1+\frac{B}{\sigma^{2}}\right).$ (20)

We now apply Theorem II.3. Plugging (10) and (20) into (18) and using the fact
that logarithm is monotonic, we write the worst case capacity for
$P_{\circ}=\operatorname{\mathcal{N}}(0,\sigma_{\circ}^{2})$ as,

$\displaystyle C_{\mathcal{N}(0,\sigma^{2}_{\circ})}\left(B,r\right)$
$\displaystyle=\inf_{|\sigma-\sigma_{\circ}|\leq
r}C_{\mathcal{N}(0,\sigma^{2}_{\circ})}(B)$ (21)
$\displaystyle=\inf_{|\sigma-\sigma_{\circ}|\leq
r}\frac{1}{2}\log\left(1+\frac{B}{\sigma^{2}}\right)$ (22)
$\displaystyle=\frac{1}{2}\log\left(1+\frac{B}{(\sigma+r)^{2}}\right).$ (23)

Naturally, increasing the radius of ambiguity $r$ diminishes the compound
channel capacity. This effect can be observed in Fig 1.

##  III Proof of Theorem II.1

###  III-A Useful Results

If the source distribution $X\sim P_{\circ}$ is known, (2) reduces to the
standard RDF [36, Eqn. (10.12)]

$\displaystyle
R_{P_{\circ}}(D)=R_{P_{\circ}}(D,0)=\inf_{\begin{subarray}{c}P_{\hat{X}|X}\colon\mathbb{R}^{d}\mapsto\mathbb{R}^{d}\\\
\mathbb{E}\left[\|X-\widehat{X}\|^{2}\right]\leq
D\end{subarray}}I(X;\widehat{X}).$ (24)

The next lemma brings to light the significance of the Gaussian RDF in (6) as
the worst-case RDF among sources with the same covariance matrix.

######  Lemma III.1 (Gaussian is the hardest to encode, [35, Eqn. (13)])

Assume that the source distribution $P_{\circ}$ has a covariance
$\Sigma_{\circ}\in\mathbb{S}_{+}^{d}$. The RDF $R_{P_{\circ}}(D)$ satisfies

$R_{P_{\circ}}(D)\leq R_{\operatorname{\mathcal{N}}(0,\Sigma_{\circ})}(D),$
(25)

and the upper bound is attained by
$P_{\circ}=\mathcal{N}\left(0,\Sigma_{\circ}\right)$.

###### Proof:

This result is due to Kolmogorov [35, Eqn. (13)]. We provide a short proof in
Appendix A for completeness. ∎

Noting that

$\displaystyle\operatorname{W_{2}}(P,P_{\circ})^{2}\leq
r\Longleftrightarrow\operatorname{\mathbb{E}}[\|X-X_{\circ}\|^{2}]\leq r,$
(26)

we rewrite the dual formulation of the compound RDF in Lemma II.2 as,

$R_{P_{\circ}}(D,r)\\!=\\!\\!\sup_{\begin{subarray}{c}P\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})\colon\\\
\operatorname{W_{2}}(P,\,P_{\circ})\leq r\end{subarray}}R_{P}(D).$ (27)

###  III-B Proof of Theorem II.1: upper bound

Consider two distributions
$P_{\circ},P\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})$ with means
$\mu_{\circ},\mu\in\mathbb{R}^{d}$ and covariances
$\Sigma_{\circ},\Sigma\in\mathbb{S}_{+}^{d}$, respectively. The
$\operatorname{W_{2}}$-distance between them satisfies the Gelbrich bound [33,
Thm. 2.1],

$\displaystyle\operatorname{W_{2}}(P,P_{\circ})^{2}$
$\displaystyle\geq\operatorname{BW}(\Sigma,\Sigma_{\circ})^{2}\\!+\\!\|{\mu_{\circ}\\!-\\!\mu}\|_{\text{}}^{2},$
(28)

where equality is attained if both $P_{\circ}$ and $P$ are Gaussian
distributions. It follows that the $\operatorname{W_{2}}$-distance between
distributions upper-bounds the Bures-Wasserstein distance between their
covariance matrices:

$\displaystyle\operatorname{W_{2}}(P,\,P_{\circ})$
$\displaystyle\geq\operatorname{BW}(\Sigma,\,\Sigma_{\circ}).$ (29)

Applying (29) to (27), we obtain an upper bound on the worst-case RDF as:

$\displaystyle R_{P_{\circ}}(D,r)$
$\displaystyle\leq\sup_{\begin{subarray}{c}P\in\mathcal{P}_{2+\epsilon}(\mathbb{R}^{d})\colon\\\
\operatorname{BW}(\Sigma,\,\Sigma_{\circ})\leq r\end{subarray}}\ R_{P}(D)$
(30) $\displaystyle\leq\sup_{\operatorname{BW}(\Sigma,\Sigma_{\circ})\leq
r}R_{\operatorname{\mathcal{N}}(0,\Sigma)}(D),$ (31)

where (31) is by Lemma III.1. Plugging (6) into the right side of (31) yields
the $\leq$ direction of (7).

###  III-C Proof of Theorem II.1: lower bound

By Lemma III.1, equality is achieved in (31) by
$P=\operatorname{\mathcal{N}}(0,\Sigma)$. Since both $P_{\circ}$ and $P$ are
Gaussian, equality is achieved in (29), and, by extension, in (30) as well.

##  IV Conclusion

In this paper, we studied Sakrison’s [1] compound RDF and Blackwell’s compound
capacity [2], focusing on a scenario where the source / noise distribution
belongs to a Wasserstein-2 ambiguity set. Our key findings include the
identification of the Gaussian distribution as the worst-case scenario for
encoding within this set (Theorem II.1, Theorem II.3). The compound RDF
(Theorem II.1) and capacity (Theorem II.3) are expressed in terms of the
covariance matrices of Gaussian distributions. Future work could explore
ambiguity sets defined using distances beyond Wasserstein-2, tradeoffs between
coding and learning the distribution to decrease the size $r$ of the ambiguity
set, extensions to multiterminal settings, and to causal source and channel
coding.

## References

  * [1] D. J. Sakrison, “The rate distortion function for a class of sources,” _Information and Control_ , vol. 15, no. 2, pp. 165–195, June 1969.
  * [2] D. Blackwell, L. Breiman, and A. Thomasian, “The capacity of a class of channels,” _The Annals of Mathematical Statistics_ , pp. 1229–1241, Dec. 1959.
  * [3] J. Ziv and A. Lempel, “A universal algorithm for sequential data compression,” _IEEE Transactions on Information Theory_ , vol. 23, no. 3, pp. 337–343, May 1977.
  * [4] T. A. Welch, “A technique for high-performance data compression,” _Computer_ , vol. 17, no. 06, pp. 8–19, June 1984.
  * [5] J. Ziv and A. Lempel, “Compression of individual sequences via variable-rate coding,” _IEEE Transactions on Information Theory_ , vol. 24, no. 5, pp. 530–536, Sep. 1978.
  * [6] E. H. Yang and J. C. Kieffer, “Simple universal lossy data compression schemes derived from the Lempel-Ziv algorithm,” _IEEE Transactions on Information Theory_ , vol. 42, no. 1, pp. 239–245, Jan. 1996.
  * [7] E. H. Yang, Z. Zhang, and T. Berger, “Fixed-slope universal lossy data compression,” _IEEE Transactions on Information theory_ , vol. 43, no. 5, pp. 1465–1476, Sep. 1997.
  * [8] D. Baron and T. Weissman, “An MCMC approach to lossy compression of continuous sources,” in _2010 Data Compression Conference_ , Snowbird, UT, USA, Apr. 2010, pp. 40–48.
  * [9] S. Jalali and T. Weissman, “Block and sliding-block lossy compression via MCMC,” _IEEE Transactions on Communications_ , vol. 60, no. 8, pp. 2187–2198, Aug. 2012.
  * [10] A. Tchamkerten and E. Telatar, “A feedback strategy for binary symmetric channels,” in _2002 IEEE International Symposium on Information Theory Proceedings_ , Lausanne, Switzerland, June 2002, p. 362.
  * [11] D. J. MacKay, “Fountain codes,” _IEE Proceedings-Communications_ , vol. 152, no. 6, pp. 1062–1068, Dec. 2005.
  * [12] S. C. Draper, B. J. Frey, and F. R. Kschischang, “Efficient variable length channel coding for unknown DMCs,” in _2004 IEEE International Symposium on Information Theory Proceedings_ , Chicago, IL, USA, Jan. 2004, pp. 379–379.
  * [13] N. Shulman, “Communication over an unknown channel via common broadcasting,” Ph.D. dissertation, Tel Aviv University, July 2003.
  * [14] N. Blits and M. Feder, “Universal rateless coding with finite message set,” in _2012 IEEE International Symposium on Information Theory Proceedings_ , Cambridge, MA, USA, Aug. 2012, pp. 1772–1776.
  * [15] D. Sakrison, “The rate of a class of random processes,” _IEEE Transactions on Information Theory_ , vol. 16, no. 1, pp. 10–16, Jan. 1970.
  * [16] H. Poor, “The rate-distortion function on classes of sources determined by spectral capacities,” _IEEE Transactions on Information Theory_ , vol. 28, no. 1, pp. 19–26, Jan. 1982.
  * [17] D. Blackwell, L. Breiman, and A. Thomasian, “The capacities of certain channel classes under random coding,” _The Annals of Mathematical Statistics_ , vol. 31, no. 3, pp. 558–567, Sep. 1960.
  * [18] W. Root and P. Varaiya, “Capacity of classes of Gaussian channels,” _SIAM Journal on Applied Mathematics_ , vol. 16, no. 6, pp. 1350–1393, Nov. 1968.
  * [19] A. Gamal, “The capacity of a class of broadcast channels,” _IEEE Transactions on Information Theory_ , vol. 25, no. 2, pp. 166–169, Mar. 1979.
  * [20] A. Lapidoth and P. Narayan, “Reliable communication under channel uncertainty,” _IEEE Transactions on Information Theory_ , vol. 44, no. 6, pp. 2148–2177, Oct. 1998.
  * [21] C. Villani, _Optimal transport: old and new_. Springer, 2009, vol. 338.
  * [22] T. Kargin, J. Hajar, V. Malik, and B. Hassibi, “Wasserstein distributionally robust regret-optimal control in the infinite-horizon,” _arXiv preprint arXiv:2312.17376_ , Dec. 2023.
  * [23] S. Shafieezadeh Abadeh, V. A. Nguyen, D. Kuhn, and P. M. Mohajerin Esfahani, “Wasserstein distributionally robust Kalman filtering,” in _Advances in Neural Information Processing Systems_ , vol. 31, Montréal, Canada, Sep. 2018.
  * [24] D. Kuhn, P. M. Esfahani, V. A. Nguyen, and S. Shafieezadeh-Abadeh, “Wasserstein distributionally robust optimization: Theory and applications in machine learning,” in _Operations research & management science in the age of analytics_, Aug. 2019, pp. 130–166.
  * [25] F. Al Taha, S. Yan, and E. Bitar, “A distributionally robust approach to regret optimal control using the Wasserstein distance,” in _2023 62nd IEEE Conference on Decision and Control_ , Singapore, Apr. 2023, pp. 2768–2775.
  * [26] B. Hassibi, A. H. Sayed, and T. Kailath, _Indefinite-Quadratic estimation and control: a unified approach to H-2 and H-infinity theories_. SIAM, 1999.
  * [27] G. Goel and B. Hassibi, “Regret-optimal control in dynamic environments,” _Proceedings of Machine Learning Research_ , vol. 134, pp. 1–22, Feb. 2021.
  * [28] J. Hajar, T. Kargin, and B. Hassibi, “Wasserstein distributionally robust regret-optimal control under partial observability,” in _2023 59th Annual Allerton Conference on Communication, Control, and Computing_ , Monticello, Illinois, USA, Nov. 2023, pp. 1–6.
  * [29] E. Lei, H. Hassani, and S. S. Bidokhti, “Out-of-distribution robustness in deep learning compression,” _arXiv preprint arXiv:2110.07007_ , Oct. 2021.
  * [30] Y. Blau and T. Michaeli, “Rethinking lossy compression: The rate-distortion-perception tradeoff,” in _International Conference on Machine Learning_. Long Beach, California, USA: PMLR, July 2019, pp. 675–685.
  * [31] G. Serra, P. A. Stavrou, and M. Kountouris, “On the computation of the Gaussian rate-distortion-perception function,” _IEEE Journal on Selected Areas in Information Theory_ , pp. 1–1, Mar. 2024.
  * [32] Y. Polyanskiy and Y. Wu, “Information theory: From coding to learning,” _Book draft_ , 2022.
  * [33] M. Gelbrich, “On a formula for the L2 Wasserstein metric between measures on Euclidean and Hilbert spaces,” _Mathematische Nachrichten_ , vol. 147, no. 1, pp. 185–203, 1990.
  * [34] R. Bhatia, T. Jain, and Y. Lim, “On the Bures-Wasserstein distance between positive definite matrices,” _Expositiones Mathematicae_ , vol. 37, no. 2, pp. 165–191, June 2019.
  * [35] A. Kolmogorov, “On the Shannon theory of information transmission in the case of continuous signals,” _IRE Transactions on Information Theory_ , vol. 2, no. 4, pp. 102–108, Dec. 1956.
  * [36] T. M. Cover and J. A. Thomas, _Elements of information theory_. John Wiley & Sons, 1999.
  * [37] I. Csiszar, “Arbitrarily varying channels with general alphabets and states,” _IEEE Transactions on Information Theory_ , vol. 38, no. 6, pp. 1725–1742, Nov. 1992.
  * [38] S. Loyka and C. D. Charalambous, “A general formula for compound channel capacity,” _IEEE Transactions on Information Theory_ , vol. 62, no. 7, pp. 3971–3991, Apr. 2016.
  * [39] M.-C. Yue, D. Kuhn, and W. Wiesemann, “On linear optimization over wasserstein balls,” _Mathematical Programming_ , vol. 195, no. 1, pp. 1107–1122, June 2022.
  * [40] A. El Gamal and Y.-H. Kim, _Network information theory_. Cambridge university press, 2011.
  * [41] A. Lapidoth, “Nearest neighbor decoding for additive non-Gaussian noise channels,” _IEEE Transactions on Information Theory_ , vol. 42, no. 5, pp. 1520–1529, Sep. 1996.
  * [42] S. Ihara, “On the capacity of channels with additive non-Gaussian noise,” _Information and Control_ , vol. 37, no. 1, pp. 34–39, Apr. 1978.
  * [43] S. N. Diggavi and T. M. Cover, “The worst additive noise under a covariance constraint,” _IEEE Transactions on Information Theory_ , vol. 47, no. 7, pp. 3072–3081, Nov. 2001.

##  Appendix A Proof of Lemma III.1

Without loss of generality, assume that $X$ is zero-mean. We first state the
following useful lemma, which extends [32, Thm. 5.11] to a vector channel.

######  Lemma A.1 (Gaussian input maximizes the mutual information in an AWGN
channel)

Let $X$ be a random channel input in $\mathbb{R}^{d}$ with known covariance
$\Sigma\in\mathbb{S}^{d}_{+}$ and let $A\in\mathbb{R}^{d\times d}$ be a fixed
channel matrix. Let
$Z_{g}\stackrel{{\scriptstyle\text{}}}{{\sim}}\operatorname{\mathcal{N}}(0,\Sigma_{Z})$
be the additive Gaussian channel noise independent of $X$, with known
covariance $\Sigma_{Z}\in\mathbb{S}^{d}_{+}$. We have that;

$I(X,\;AX+Z_{g})\leq I(X_{g},\;AX_{g}+Z_{g}),$ (32)

where
$X_{g}\stackrel{{\scriptstyle\text{}}}{{\sim}}\operatorname{\mathcal{N}}(0,\Sigma)$
is independent of $Z_{g}$, and equality holds if
$X\sim\operatorname{\mathcal{N}}(0,\Sigma)$.

###### Proof:

The mutual information is given by,

$\displaystyle I(X,\,AX+Z_{g})$ $\displaystyle=h(AX+Z_{g})-h(AX+Z_{g}|X),$
(33) $\displaystyle=h(AX+Z_{g})-h(Z_{g}).$ (34)

The second term in the last equality does not depend on $X$, while the first
term, by the maximum entropy property of Gaussian random variables [36, Thm.
8.6.5], is bounded above by

$h(AX+Z_{g})\leq\frac{1}{2}\log\left|2\pi\mathrm{e}\,\widehat{\Sigma}\right|,$
(35)

where $\widehat{\Sigma}\coloneqq\operatorname{Cov}(AX+Z_{g})=A\Sigma
A^{T}+\Sigma_{Z}$ is the covariance of matrix of $AX+Z_{g}$. This upper bound
is achieved by a Gaussian input
$X_{g}\stackrel{{\scriptstyle\text{}}}{{\sim}}\mathcal{N}(0,\Sigma)$
independent of the channel noise $Z_{g}$. ∎

Consider the RDF for a known source distribution $P_{X}$ given in (24).
Restricting the infimization to linear mappings of the form

$\displaystyle\widehat{X}=AX+Z_{g},$ (36)

where $A\in\mathbb{R}^{d\times d}$, and $Z_{g}\sim\mathcal{N}(0,\Sigma_{Z})$
is independent of $X$, we get an upper bound on $R_{P_{X}}(D)$ as,

$\displaystyle R_{P_{X}}(D)$
$\displaystyle\leq\inf_{\begin{subarray}{c}A\in\mathbb{R}^{d\times
d},\Sigma_{Z}\succeq 0\colon\\\
\mathbb{E}\left[\|{X-\widehat{X}}\|_{\text{}}^{2}\right]\leq
D\end{subarray}}I(X;AX+Z_{g})$ (37)
$\displaystyle\leq\inf_{\begin{subarray}{c}A\in\mathbb{R}^{d\times
d},\Sigma_{Z}\succeq 0\colon\\\
\mathbb{E}\left[\|{X_{g}-\widehat{X}_{g}}\|_{\text{}}^{2}\right]\leq
D\end{subarray}}I(X_{g};AX_{g}+Z_{g})$ (38)
$\displaystyle=R_{\mathcal{N}(0,\Sigma)}(D),$ (39)

where $X_{g}\sim\mathcal{N}(0,\Sigma)$ and $\widehat{X}_{g}\coloneqq
AX_{g}+Z_{g}$. Inequality (38) is by Lemma A.1. Since the condition
$\mathbb{E}\left[\|{X_{g}-\widehat{X}_{g}}\|_{\text{}}^{2}\right]\leq D$ can
be written as
$\operatorname{tr}((A\\!-\\!I)\Sigma(A\\!-\\!I)^{T}\\!+\\!\Sigma_{Z})\leq D$,
and the mutual information between two Gaussian random vectors can be written
as,

$\displaystyle I(X_{g};AX_{g}+Z_{g})=\frac{1}{2}\log\frac{\left|A\Sigma
A^{T}+\Sigma_{Z}\right|}{\left|\Sigma_{Z}\right|},$ (40)

the right side of (38) is equal to the right side of (6). It remains to show
(39). Applying the argument in (37), (38) to $P_{X}=\mathcal{N}(0,\Sigma)$
yields the $\geq$ in (39). To show $\leq$, fix any $P_{\widehat{X}|X_{g}}$.
Using standard arguments, [36, Proof of Th. 10.3.2], we have,

$\displaystyle I(X_{g},\widehat{X})$
$\displaystyle=h(X_{g})-h(X_{g}|\widehat{X})$ (41)
$\displaystyle=\frac{1}{2}\log\left|2\pi\mathrm{e}\Sigma\right|-h(X_{g}-\widehat{X}|X_{g})$
(42)
$\displaystyle\geq\frac{1}{2}\log\left|2\pi\mathrm{e}\Sigma\right|-h(X_{g}-\widehat{X})$
(43)
$\displaystyle\geq\frac{1}{2}\log\left|2\pi\mathrm{e}\Sigma\right|-\frac{1}{2}\log\left|2\pi\mathrm{e}\Sigma_{X_{g}-\widehat{X}}\right|,$
(44)

where $\Sigma_{X_{g}-\widehat{X}}$ is the covariance of $X_{g}-\widehat{X}$.
Here, (43) holds because conditioning decreases entropy [36, Thm. 8.6.1 Cor.
2], and (44) is due to (35). The expression on the right-hand side of (44) is
the mutual information between the jointly Gaussian pair
$(X_{g},\widehat{X})$. It follows that $R_{\mathcal{N}(0,\Sigma)}(D)$ is lower
bounded by the right side of (38).

##  Appendix B Proof of Theorem II.3

We first state the following useful lemmas. In Lemma B.1, we state the
capacity of a Gaussian vector channel. To get Lemma B.1, we slightly modify
[40, Thm. 9.1] for our use case. In Lemma B.2, we show that for an additive
channel, Gaussian noise, among all noises with the same covariance, minimizes
the channel capacity. A similar result in the setting of stochastic processes
is established in [42].

######  Lemma B.1 (Capacity of an AWGN channel)

Consider the channel coding setting defined in the first paragraph of Section
II-B. The capacity-cost function for a $d$-dimensional multivariate Gaussian
noise vector $Z_{g}\sim\mathcal{N}(0,\Sigma_{Z})$ is given by,

$\displaystyle C_{\mathcal{N}(0,\Sigma_{Z})}(B)=$
$\displaystyle\sup_{\begin{subarray}{c}\Sigma\succeq 0\colon\\\
\text{tr}(\Sigma)\leq B\end{subarray}}\log\frac{|\Sigma_{Z}+H\Sigma
H^{T}|}{|\Sigma_{Z}|}.$ (45)

###### Proof:

The capacity for $Z_{g}\sim\mathcal{N}(0,I)$, is given by [40, Thm. 9.1],

$\displaystyle C_{\mathcal{N}(0,I)}(B)=$
$\displaystyle\sup_{\begin{subarray}{c}\Sigma\succeq 0\colon\\\
\text{tr}(\Sigma)\leq B\end{subarray}}\log|I+H\Sigma H^{T}|.$ (46)

The capacity for $Z_{g}\sim\mathcal{N}(0,\Sigma_{Z})$ can be obtained by
considering the channel matrix $\tilde{H}=\Sigma_{Z}^{-1/2}H$ [40, Rem. 9.1].

$\displaystyle C_{\mathcal{N}(0,\Sigma_{Z})}(B)=$
$\displaystyle\sup_{\begin{subarray}{c}\Sigma\succeq 0\colon\\\
\text{tr}(\Sigma)\leq B\end{subarray}}\log|I+\Sigma_{Z}^{-1/2}H\Sigma
H^{T}\Sigma_{Z}^{-T/2}|.$ (47)

Multiplying $I+\Sigma_{Z}^{-1/2}HQH^{T}\Sigma_{Z}^{-T/2}$ by
$\Sigma_{Z}^{1/2}$ on the left and $\Sigma_{Z}^{T/2}$ on the right, and
dividing the argument of $\log$ in (47) by $|\Sigma_{Z}|$, we get (45). ∎

######  Lemma B.2 (Gaussian noise minimizes the channel capacity of an
additive channel)

Let $Z$ be a random channel noise in $\mathbb{R}^{d}$ with known covariance
$\Sigma_{Z}\in\mathbb{R}^{d\times d}$ and let $H\in\mathbb{R}^{d\times d}$ be
a fixed channel matrix. Let
$Z_{g}\stackrel{{\scriptstyle\text{}}}{{\sim}}\operatorname{\mathcal{N}}(0,\Sigma_{Z})$
be the additive Gaussian channel noise, with the same covariance as $Z$,
independent of the channel input $X$. Then,

$\displaystyle C_{\mathcal{N}(0,\Sigma_{Z})}(B)\leq C_{P}(B),$ (48)

and equality is achieved by $P=\mathcal{N}(0,\Sigma_{Z})$.

###### Proof:

Consider $X_{g}\sim\mathcal{N}(0,\Sigma)$ where $\Sigma$ is the covariance of
$X$. Using (32) and then [43, Lem. II.2], we have the following set of
inequalities,

$\displaystyle I(X,\;HX+Z_{g})$ $\displaystyle\leq I(X_{g},\;HX_{g}+Z_{g}),$
(49) $\displaystyle\leq I(X_{g},\;HX_{g}+Z).$ (50)

Now note that,

$\displaystyle\sup_{\begin{subarray}{c}\Sigma\succeq 0\colon\\\
\mathbb{E}\left[\|{X_{g}}\|_{\text{}}^{2}\right]\leq
B\end{subarray}}I(X_{g},\;HX_{g}+Z)\leq\sup_{\begin{subarray}{c}P\text{ on
}\mathbb{R}^{d}\colon\\\ \mathbb{E}\left[\|{X}\|_{\text{}}^{2}\right]\leq
B\end{subarray}}I(X,HX+Z).$ (51)

The expression on the right-hand side of (51) is $C_{P}(B)$. The expression on
the left-hand side of (51) is lower bounded by
$C_{\mathcal{N}(0,\Sigma_{Z})}(B)$. Indeed, After applying inequalities (50)
and then (49) to lower-bound the left side of (51) and taking supremum over
all input distributions leads to (45). ∎

Proof of Theorem II.3:

####  B-1 Converse

Consider the dual formulation of the compound capacity (19) and a noise
distribution in the $\operatorname{W_{2}}$ ball $P$ with mean $\mu$ and
covariance $\Sigma$. We re-write the dual formulation as,

$\displaystyle
C_{P_{\circ}}(B,r)\\!=\\!\\!\inf_{\begin{subarray}{c}P\in\mathcal{P}_{2}(\mathbb{R}^{d})\colon\\\
\operatorname{W_{2}}(P,\,P_{\circ})\leq r\end{subarray}}C_{P}(B).$ (52)

By the Gelbrich bound [33, Thm. 2.1] we have (29). Applying (29) to (52), we
obtain a lower bound on the compound capacity as$\colon$

$\displaystyle C_{P_{\circ}}(B,r)$
$\displaystyle\geq\\!\inf_{\begin{subarray}{c}P\in\mathcal{P}_{2}(\mathbb{R}^{d})\colon\\\
\operatorname{BW}(\Sigma,\Sigma_{\circ})\leq r\end{subarray}}C_{P}(B)$ (53)
$\displaystyle\geq\\!\inf_{\begin{subarray}{c}P\in\mathcal{P}_{2}(\mathbb{R}^{d})\colon\\\
\operatorname{BW}(\Sigma,\Sigma_{\circ})\leq
r\end{subarray}}C_{\mathcal{N}(0,\Sigma)}(B),$ (54)

where (54) is by Lemma B.2. Plugging (45) into the right side of (54) yields
the $\geq$ direction of (18).

####  B-2 Achievability

Equality in (54) is achieved by Gaussian $P$ (48). Since we assume that
$P_{\circ}$ is Gaussian, equality is achieved in (29), and, by extension, in
(53) as well.