text:
\begin{document}
\title{Slim Sets of Binary Trees}
\author{\bf Stefan Gr{\"u}newald
\\CAS-MPG Partner Institute for Computational Biology
\\Shanghai Institutes for Biological Sciences
\\320 Yue Yang Road
\\Shanghai 200031, China
\\and
\\Max Planck Institute for Mathematics in the Sciences
\\Inselstra{\ss}e 22
\\04103 Leipzig, Germany
\\stefan@picb.ac.cn
\\Tel: +86 (21) 54920459
\\Fax: +86 (21) 54920451}

\date{\today}
\maketitle

\newpage
\begin{abstract}
A classical problem in phylogenetic tree analysis is to decide
whether there is a phylogenetic tree $T$ that contains all
information of a given collection $\cP$ of phylogenetic trees.
If the answer is ``yes'' we say that $\cP$ is compatible and $T$
displays $\cP$.
This decision problem is NP-complete even if all input trees are
quartets, that is binary trees with exactly four leaves. In this
paper, we prove a sufficient condition for a set of binary
phylogenetic trees to be compatible. That result is used to give a short and
self-contained proof of the known characterization of quartet sets of
minimal cardinality which are displayed by a unique phylogenetic tree.
\end{abstract}

{\bf Keywords:} Phylogenetics, Supertrees, Quartets

\section{Introduction}
Phylogenetic trees are used in computational biology to visualize the
evolutionary relationship between some taxa (e.g. species or
genes). For many methods in phylogenetic tree reconstruction, the required
running time grows at least exponentially with the
number of taxa. Hence, it is a natural and widely used approach to construct
a collection of phylogenetic trees with small taxa sets first and then a
supertree (see \cite{b04} for an overview), that is a phylogenetic tree
for all taxa that are contained in at least one of the small trees.
However, it is NP-complete to decide whether there is a supertree that
displays all input trees, even if each of them contains only four taxa
\cite{s92}.

Mathematically, a {\em phylogenetic tree} is a tree without
vertices of degree~2 and it is called {\em binary} if every interior
vertex has degree~3. The set of leaves or {\em taxa set} of a
phylogenetic tree $T$ is denoted by $L(T)$ and,
for a set $\cP$ of phylogenetic trees, we define $L(\cP)=
\displaystyle\bigcup_{T \in \cP}L(T)$. Let $T$ and $T'$ be two
phylogenetic trees with $L(T') \subseteq L(T)$ where $T'$ is
binary. We say that $T'$ is
{\em displayed} by $T$ if $T'$ is the phylogenetic tree obtained from the
smallest subtree of $T$ that contains $L(T')$ by suppressing all
vertices of degree~2. In that case $T'$ is called the {\em restriction
  of $T$ to $L(T')$} and is denoted by $T|_{L(T')}$.
A set $\cP$ of binary phylogenetic trees is {\em
  compatible} if there is a phylogenetic tree $T$ that displays every tree
in $\cP$ and in that case we say that $T$ {\em displays} $\cP$. A {\em
  cherry} of a phylogenetic tree is a set of two leaves which are
adjacent to the same vertex of degree~3. A {\em quartet} is a binary
phylogenetic tree with exactly four leaves and the quartet with leaf
set $\{a,b,c,d\}$ and cherries $\{a,b\}$ and $\{c,d\}$ is denoted by
$ab|cd$. A set $\cP$ of binary phylogenetic trees is {\em definitive}
if there is exactly one
phylogenetic tree $T$ with taxa set $L(\cP)$ displaying $\cP$ and in
that case we say that $\cP$ {\em defines} $T$. Here, two phylogenetic
trees $T_1$ and $T_2$ are defined to be the same (or isomorphic) if
$L(T_1)=L(T_2)$ and there is a graph isomorphism from $T_1$ to $T_2$
that maps every leaf to itself. For example, both phylogenetic trees depicted
in Figure \ref{snow} display the quartets $ad|cf$, $ae|bf$, and $bd|ce$ thus
the set $\{ad|cf,ae|bf,bd|ce\}$ is not definitive.

\begin{figure}[b]
\center
\input{snowflakes2.pstex_t}
\caption{Two phylogenetic trees.}
\label{snow}
\end{figure}

The main result of this paper is a sufficient condition for a set of
binary phylogenetic trees to be compatible. We need some more
definitions to state it.
The set of interior edges of a phylogenetic tree $T$ is denoted by
$\Er(T)$. For a set $\cP$ of phylogenetic trees, we define
the {\em excess of $\cP$}, denoted $\exc(\cP)$ by
$$\exc(\cP)=|L(\cP)|-3-\sum_{T \in \cP}|\Er(T)|.$$
Finally, we say that $\cP$ is {\em excess-free} if $\exc(\cP)=0$, we define
$\Exc(\cP)=\{\cP' \subseteq \cP:\exc(\cP')=0\}$, and we call $\cP$ {\em slim} if $\exc(\cP') \ge 0$ for
every non-empty subset $\cP' \subseteq \cP$. In the next section, we
will prove:
\begin{theorem}
Every slim set of binary phylogenetic trees is compatible.
\label{slim}
\end{theorem}
It depends only on the involved leaf sets of the trees and not on
which phylogenetic tree is chosen for a fixed leaf set whether a
collection of binary phylogenetic trees is slim. Nevertheless, Theorem
\ref{slim} is sharp in the sense that, for every binary
phylogenetic tree $T$, there are slim sets of quartets that define
$T$ \cite{bds99}.

After proving Theorem \ref{slim} in Section~\ref{proof}, we will apply
it in Section~\ref{appl} to give a
new proof of the known characterization of excess-free definitive
quartet sets. An outline of the original proof is given in
\cite{bds99} while the full details can be found in \cite{b99}.
That characterization has been referred to as ``one of the most
mysterious and apparently difficult results in phylogenetics''
\cite{ds04}.

\section{Proof of Theorem \ref{slim}}
\label{proof}

We assume that the statement is wrong and that $\cP$ is a minimal
non-compatible slim set of binary phylogenetic trees where $L(\cP)$ is
minimal under
all non-compatible slim sets of binary phylogenetic trees with cardinality
$|\cP|$. Clearly, we have $|L(T)| \ge 4$ for every tree $T \in \cP$ and
there is no subset $\cP_1$ of $\cP$ with $\exc(\cP_1)=0$ and
$1<|\cP_1|<|\cP|$ since otherwise $\cP_1$ can be replaced by a single
binary phylogenetic tree with leaf set $L(\cP_1)$ that displays
$\cP_1$, contradicting the minimality of $|\cP|$.

We claim that, for every  cherry $\{x,y\}$ of $T$ for some tree $T$ in
$\cP$, there is another tree $T'$ in $\cP$ that contains $x$ and $y$ as
leaves but not as a cherry. Assuming that the claim is wrong, let
$\cP'$ be the set of phylogenetic trees obtained from $\cP$ by
replacing $x$ and
$y$ by a new leaf $z$, i.e. if a tree $T \in \cP$ contains either $x$
or $y$ then this leaf is replaced by $z$ and if $T$ contains a cherry
$\{x,y\}$ then the cherry is replaced by $z$. Clearly, we have
$|L(\cP')|<|L(\cP)|$ and $\cP'$ is not
compatible since the tree obtained from a phylogenetic tree displaying
$\cP'$ by replacing $z$ by a cherry $\{x,y\}$ would display $\cP$. Hence,
by induction hypothesis, $\cP'$ is not slim. Let $\cP_2'$ be a subset of
$\cP'$ with negative excess and let $\cP_2$ be the subset of $\cP$
obtained from $\cP_2'$ by reversing the identification of $x$ and $y$,
i.e. replacing $z$ by a cherry $\{x,y\}$ or a
leaf $x$ or $y$ for
every tree in $\cP_2'$ that contains $z$. We have
\begin{eqnarray*}\exc(\cP_2) & = & |L(\cP_2)|-3-\sum_{T \in
    \cP_2}|\Er(T)|  \\
& \le & |L(\cP_2')|+1-3-\sum_{T \in \cP_2'}|\Er(T)| \\
& = & \exc(\cP_2')+1 \le 0.
\end{eqnarray*}
This implies $\cP_2=\cP$ or $|\cP_2|=1$ but for both cases we get
$\exc(\cP_2') \ge \exc(\cP_2) \ge 0$, a contradiction. This proves the claim.

We construct a digraph $G_{\cP}=(V_{\cP},A_{\cP})$ with vertex set
$V_{\cP}=\cP$ and an arc labeling $\lambda$ that associates a
set of two elements of $L(\cP)$ with every arc $a \in A_{\cP}$ as follows:
For every tree $T \in \cP$, we choose two different cherries
$\{x_1(T),y_1(T)\}$ and $\{x_2(T),y_2(T)\}$ of $T$ and, for $i \in \{1,2\}$,
we choose $T_i(T) \in \cP$ such that $x_i(T),y_i(T) \in L(T_i)$ but
$\{x_i(T),y_i(T)\}$ is not a cherry of $T_i(T)$. Then we define
$A_{\cP}=\{(T,T_i(T)):T \in \cP, i \in \{1,2\}\}$ and
$\lambda((T,T_i(T)))=\{x_i(T),y_i(T)\}$ for all $T \in \cP$ and $i \in
\{1,2\}$. For the ease of notation, we will write $\lambda(T_1,T_2)$
rather than $\lambda((T_1,T_2))$ for an arc $(T_1,T_2) \in A_{\cP}$.

\begin{figure}[h]
\begin{center}
\input{octahedron.pstex_t}
\caption{The (in this case well-defined) arc-labeled digraph $G_{\cP}$ for $\cP=\{q_1,...,q_6\}$ with $q_1=ab|cd$, $q_2=ac|ef$, $q_3=ae|bg$, $q_4=bd|gh$, $q_5=cf|dh$, and $q_6=eg|fh$.}
\label{octa}
\end{center}
\end{figure}

By construction, the outdegree $d^+(T)=2$ for every tree $T \in
\cP$ thus we have $|A(G')|\le 2|V(G')|$ for every subdigraph $G'$ of
$G_{\cP}$ and equality holds for $G'=G_{\cP}$. Let $G$ be a minimal
subdigraph of $G_{\cP}$ with $|A(G)|=2|V(G)|$, let $\cP_3$ be the
vertex set of $G$
and let $X=L(\cP_3)$. We define an {\em
  $x$-coloured cycle} of $G$ to be a cycle $C$ of $G$ such that $x \in
\lambda(a)$ for every arc $a$ of $C$. We call $C$ a {\em coloured
  cycle} if there is $x \in X$ such that $C$ is an $x$-coloured cycle.

Since two different cherries of a binary tree are disjoint,
$\lambda(T_1,T_2) \cap \lambda(T_1,T_3) \neq \emptyset$ implies
$T_2=T_3$. Hence, every coloured cycle $C$ of $G$ is a directed cycle
since otherwise there is a vertex of outdegree 2 in $C$ but the
two outgoing arcs must have disjoint label sets. This implies that every
arc with label set $\{x,y\}$ is contained in at most one $x$-coloured
and in at most one $y$-coloured cycle.

Recall that the {\em cycle space} of a graph $H=(V,E)$ is the vector space over the 2-element field
${\mathbf Z}_2$ generated by the cycles of $H$ (considered as binary vectors indexed by $E$), together with the symmetric difference as addition. This makes it possible to decide whether a collection of cycles of $H$ is linearly dependent. The dimension of the cycle space is called the {\em cyclomatic number}
$c(H)$, and if $H$ is connected we have $c(H)=|E|-|V|+1$. For a digraph, we define the cycle space and the cyclomatic number to be the ones of the underlying undirected graph.

We will now show that the number of coloured cycles in $G$ is at most
$c(G)+1$. This
clearly holds if all coloured cycles of $G$ are linearly independent.
Let $S$ be a minimal linearly dependent set of coloured cycles of $G$
and let $G_S$ be the subdigraph of $G$ induced by $V(G_S)= \bigcup_{C
  \in S} V(C)$. By the minimality of $S$, $G_S$ is connected and every
arc of $G_S$ is contained in at least two
cycles of $S$. Let $(T_1,T_2)$ and $(T_2,T_3)$ be arcs of an
$x$-coloured cycle $C \in S$, let $\lambda(T_1,T_2)=\{x,y\}$ and
$\lambda(T_2,T_3)=\{x,z\}$. We have $y \neq z$ and there are arcs
$(T_4,T_2)$ and $(T_2,T_5)$ in $G_S$ with $y \in \lambda(T_2,T_5)$ and
$z \in \lambda(T_4,T_2)$ since there is a $y$-coloured cycle
containing $(T_1,T_2)$ and a $z$-coloured cycle containing $T_2,T_3$
in $S$. Hence, the degree of $T_2$ in $G_S$ as well as the degree of
every other vertex of $G_S$ is at least 4. This implies $|A(G_S)| \ge
2|V(G_S)|$ but we have $|A(G')| < 2|V(G')|$ for every proper
subdigraph of $G$. So we must have $G_S=G$ and $S$ is the set of all
coloured cycles of $G$. This means that the number of coloured cycles
in $G$ is at most $c(G)+1$. Since $G$ is connected we have
$c(G)=|A(G)|-|V(G)|+1=2|\cP_3|-|\cP_3|+1=|\cP_3|+1$ and the number of
coloured cycles in $G$ is at most $|\cP_3|+2$.

We conclude the proof by showing that $\cP_3$ has negative excess, in contradiction to our assumption that $Q$ is slim. For
$x \in X$, let $G_x=(V_x,A_x)$ be the subdigraph of $G$ such that $V_x$ is the set of all trees in
$\cP_3$ that contain $x$ and $A_x$ is the set of all arcs of $G$ whose label sets contain $x$. Then
all cycles in $G_x$ are vertex-disjoint, so we have $|V_x| \ge 1 + |A_x| - c_x$ where $c_x$ is the number of cycles in $G_x$.
This implies $$\sum_{x \in X}|V_x| \ge |X|+2|A(G)|-|\cP_3|-2=|X|+3|\cP_3|-2.$$
Finally, we get
\begin{eqnarray*}
\exc(\cP_3) & = & |X|-3- \sum_{T \in \cP_3}|\Er(T)| \\
& = & |X|-3-\sum_{T \in \cP_3}(|L(T)|-3) \\
& = & |X|-3+3|\cP_3|-\sum_{x \in X}|V_x| \\
& \le & |X|-3+3|\cP_3|-|X|-3|\cP_3|+2 \\
& = & -1.
\end{eqnarray*} \epf

\section{Definitive Quartet Sets of Minimum Size}
\label{appl}
Let $T$ be a phylogenetic tree with
$\{a,b,c,d\} \subseteq
L(T)$ and let $e \in \Er$. Then the quartet $ab|cd$ {\em
  distinguishes} $e$ if $T$ displays $ab|cd$ and $e$ is the only edge that the paths from
$a$ to $c$ and from $b$ to $d$ in $T$ have in common.
We summarize some elementary results
about definitive quartet sets. Proofs can be found in \cite{ss03}.
\begin{lemma}
\label{easy}
Let $Q$ be a quartet set that defines a phylogenetic tree $T$ with
$|L(T)|=n$. Then $T$ is binary and for every interior edge
$e$ of $T$, there must be a quartet in $Q$ that distinguishes $e$. Hence, we
have $|Q| \ge n-3$ and, in case of equality, every quartet in $Q$ distinguishes an
interior edge of $T$.
\end{lemma}

Combining Theorem \ref{slim} with Lemma \ref{easy}, we get the following corollary:

\begin{corollary}
\label{definitive}
Let $Q$ be a quartet set that defines a phylogenetic tree $T$ with $|L(T)|=n$. If $|Q|=n-3$, then $Q$ is slim and every excess-free subset of $Q$ is definitive.
\end{corollary}
\pf
Assume that $|Q|=n-3$ and $Q$ is not slim. Let $Q'$ be a subset of $Q$ with
negative excess. Since $T|_{L(Q')}$ contains $|L(Q')|-3$
interior edges but $Q'$ contains more than $|L(Q')|-3$ quartets there
must be an interior edge in $T$ that is not distinguished by a quartet
in $Q$, a contradiction to Lemma \ref{easy}. Now assume that an excess-free subset $Q'$ of $Q$ is not definitive. Let $T'$ with $L(T')=L(Q')$ be a different tree from $T|_{L(Q')}$ that displays $Q'$. Then $Q-Q'+T'$ is slim and compatible in view of Theorem \ref{slim}. However, a tree that displays $Q-Q'+T'$ displays $Q$ as well but it is different from $T$. Hence, $Q$ can not be definitive.
\epf

For a set of two binary phylogenetic trees, it is easy to decide if
they are compatible resp. definitive. The proof of the next lemma is
straight forward and omitted.

\begin{lemma}
\label{2trees}
Let $\cP=\{T_1,T_2\}$ be a set of two binary phylogenetic trees with
$L(T_1)\cap L(T_2) \neq \emptyset$. Then $\cP$ is compatible if and
only if there is a binary tree $T_{1,2}$ with leaf set $L(T_1) \cap
L(T_2)$ that is displayed by $T_1$ and $T_2$. $\cP$ is
definitive if and only if, in addition, the sets of edges in
$T_{1,2}$ which are subdivided in $T_1$ and $T_2$, respectively, are
disjoint.
\end{lemma}

\begin{figure}[h]
\begin{center}
\input{subdivide.pstex_t}
\caption{Two trees $T_1$ and $T_2$ and the restriction $T_{1,2}$ of both trees to the intersection of their leaf sets. The dashed edges have to be subdivided to obtain $T_1$ from $T_{1,2}$ and the dotted edge has to be subdivided to obtain $T_2$.}
\label{component}
\end{center}
\end{figure}

For a set $Q$ and a set $\cC$ of subsets of $Q$, the
pair $(Q,\cC)$ is called a {\em patchwork} if, for every two sets
$C_1,C_2 \in \cC$ with $C_1 \cap C_2 \neq \emptyset$, we have $C_1\cap
C_2 \in \cC$ and $C_1 \cup C_2 \in \cC$. Patchworks were introduced
by B\"ocker and Dress \cite{bd01}. An easy
proof of the following lemma can be found in \cite{ss03}, p.~136.

\begin{lemma}
Let $T$ be a binary phylogenetic tree and let $Q$ be an excess-free
quartet set such that every interior edge of $T$ is distinguished
by an element of $Q$. Then $(Q,\Exc(Q))$ is a patchwork.
\label{patchwork}
\end{lemma}

A set $\cC$ of non-empty subsets of a set $Q$ is called a
{\em hierarchy} of $Q$ if, for every two sets $C_1,C_2 \in \cC$ with
$C_1 \cap C_2 \neq \emptyset$, we have $C_1 \subseteq C_2$ or $C_2
\subseteq C_1$. The elements of a hierarchy are called {\em
  clusters}. A hierarchy $\cC$ of $Q$ is {\em maximal} if $Q \in
\cC$ and, for every set $C \in \cC$ with $|C|>1$, there are $C_1,C_2
\in \cC$ such that $C=C_1 \cup C_2$ and $C_1 \cap C_2= \emptyset$. We
call $C_1$ and $C_2$ the
{\em children} of $C$. This is only one of several different
definitions of a maximal hierarchy and their equivalence is shown in
\cite{bd00}. A patchwork $(Q,\cC)$ is called
{\em ample} if there is a maximal hierarchy $\cC'$ of $Q$ with $\cC'
\subseteq \cC$. The next lemma is a special case of the results in
\cite{bd01} where ample patchworks are studied in detail.

\begin{lemma}
Let $Q$ be a finite set and let $(Q,\cC)$ be an ample patchwork with
$C \in \cC$. Then there is a maximal hierarchy $\cC_C$ of $Q$ with $C
\in \cC_C \subseteq \cC$.
\label{ample}
\end{lemma}
\pf
Assume the statement is wrong and $C \in \cC$ is maximal such that there is no maximal hierarchy $\cC_C$ of $Q$ with $C \in \cC_C \subseteq \cC$. Clearly, we have $C \neq Q$. Let $\cC' \subseteq \cC$ be a maximal hierarchy of
$Q$. Then $\cC_1=\{C \cap C':C' \in \cC' \mbox{ and } C \cap C' \neq
\emptyset\}$ is a maximal hierarchy of $C$ with $\cC_1 \subseteq
\cC$.  Let $A \in \cC'$ be minimal such that $A \cap C \neq \emptyset$ and $A \cup C \neq C$ and let $B$ be the child of $A$ with $B \cap C = \emptyset$. Since $\cC$ is a patchwork we have that $A \cup C \in \cC$ and, by definition, $A \cup C$ is the disjoint union of $B$ and $C$. In view of the maximality of $C$ there is a maximal hierarchy $\cC'' \subseteq \cC$ of $Q$ with $A \cup C \in \cC''$. By replacing all proper subsets of $A \cup C$ in $\cC''$ by the union of $\cC_1$ and the maximal hierarchy of $B$ contained in $\cC'$, we obtain a maximal hierarchy $\cC_C$ of $Q$ with $C \in \cC_C \subseteq \cC$, in contradiction to our assumption.
\epf

Combining Lemma \ref{patchwork} and Lemma \ref{ample} yields the
following result.

\begin{corollary}
\label{amplecor}
Let $Q$ be a set of quartets with $C \in \Exc(Q)$. If $\Exc(Q)$ contains
a maximal hierarchy of $Q$, then $\Exc(Q)$ contains a maximal hierarchy
$\cC_C$ of $Q$ with $C \in \cC_C$.
\end{corollary}

We are now able to establish the hardest implication of the
characterization of excess-free definitive quartet sets.

\begin{theorem}
\label{hard}
If an excess-free set $Q$ of quartets defines a binary phylogenetic
tree $T$, then $\Exc(Q)$ contains a maximal hierarchy of $Q$.
\end{theorem}
\pf
To simplify the notation, we call a maximal hierarchy of a subset $Q_s
\subseteq Q$ that is contained in $\Exc(Q)$ a {\em $Q_s$-hierarchy}.

Assume that $Q$ is a minimal counterexample where $\{w_1,x_1\}$ is a cherry
of $T$ and $w_1x_1|w_2y \in Q$. Note that $Q$ is slim in view of Corollary \ref{definitive}.
Then there is a subset $Q'$ of
$Q-w_1x_1|w_2y$ such that $Q'$ contains $w_2$ and $y$ and $\exc(Q')=0$
since otherwise, by Theorem \ref{slim}, the quartet set obtained from
$Q$ by identifying $w_2$ and $y$ would be compatible and thus there
would be a phylogenetic tree displaying $Q$ that contains a cherry
$\{w_2,y\}$. However, $\{w_2,y\}$ is not a cherry of $T$ since $w_1x_1|w_2y$ distinguishes
an edge of $T$.

For every subset $Q_s$ of $Q-w_1x_1|w_2y$, we let
$Q_s^*$ denote the quartet set obtained from
$Q_s$ by replacing $w_1$ and $x_1$ by a new leaf
$z_1$ and we define $Q^*=(Q-w_1x_1|w_2y)^*$. Conversely, for $Q_{s'}^*\subseteq Q^*$,
we use $Q_{s'}$ to denote the quartet set obtained from $Q_{s'}^*$ by reversing the replacement. Note that $Q_{s'}$ is well defined since $Q$ is excess-free and defines $T$. Hence, every quartet in $Q$ distinguishes an interior edge of $T$ and every interior edge of $T$ is distinguished by exactly one quartet.
Clearly, $Q^*$ defines the tree $T^*$ obtained from $T$ by replacing the cherry $\{w_1,x_1\}$ by $z_1$. Further, since we have $|Q^*|\le |L(T^*)|-3$ and Lemma \ref{easy} implies $|Q^*| \ge |L(T^*)|-3$,
$Q^*$ is excess-free thus, by induction hypothesis,
$(Q^*,\Exc(Q^*))$ is an ample patchwork.

Since $\exc(Q')=0$ and $Q$ is slim we have $\exc(Q'^*)=0$ thus, by
Corollary \ref{amplecor}, there is a $Q^*$-hierarchy that contains $Q'^*$. Hence, one child
$Q_1^*$ of $Q^*$ contains $w_2$ and $y$. Let $Q_2^*$ be the other
child of $Q^*$. We note that $|L(Q_1^*) \cap L(Q_2^*)|=3$.

We will now consider the case $z_1 \in L(Q_1^*) \cap L(Q_2^*)$. Let $L(Q_1^*) \cap L(Q_2^*)=\{z_1,z_2,z_3\}$. Then $Q_1+w_1x_1|w_2y$ is excess-free and in view of Corollary \ref{definitive} definitive. By induction hypothesis, there is a $(Q_1+w_1x_1|w_2y)$-hierarchy $\cC_1$. Since $Q$ is definitive
$Q_2+w_1x_1|z_2z_3$ is definitive because every tree that displays $Q_2+w_1x_1|z_2z_3$ and the tree defined by $Q_1+w_1x_1|w_2y$ are compatible in view of Lemma \ref{2trees}. Therefore,  there is a $(Q_2+w_1x_1|z_2z_3)$-hierarchy $\cC_2$. Let $\cC_2'$ be the set system that is obtained from $\cC_2$ by replacing every cluster $C$ that contains $w_1x_1|z_2z_3$ by $(C-w_1x_1|z_2z_3) \cup (Q_1+w_1x_1|w_2y)$. Then $\cC_1 \cup \cC_2'$ is a $Q$-hierarchy, contradicting our assumption. Hence, we have $z_1 \notin L(Q_1^*) \cap L(Q_2^*)$.

If $z_1 \in L(Q_1^*)$  and $z_1 \notin L(Q_2^*)$ then $\exc(Q_1+w_1x_1|w_2y)=\exc(Q_2)=0$ thus there is a $Q$-hierarchy where $Q_1+w_1x_1|w_2y$
and $Q_2=Q_2^*$ are the children of $Q$. Hence, we have $z_1 \in L(Q_2^*)$  and $z_1 \notin L(Q_1^*)$. We can assume that $w_2 \notin
L(Q_2^*)$ since in case $w_2,y \in L(Q_2^*)$ interchanging $Q_1^*$ and
$Q_2^*$ would yield $\{w_2,y,z_1\} \subset L(Q_1^*)$, a case that we have already considered. If $y \notin
L(Q_2^*)$ then let $L(Q_1) \cap L(Q_2)=\{v_1,v_2,v_3\}$. Lemma \ref{2trees} implies that different edges of the phylogenetic tree with leaf set $\{v_1,v_2,v_3\}$ are subdivided in $T|_{L(Q_1)}$ and $T|_{L(Q_2)}$ but then $w_1x_1|w_2y$ does not distinguish an edge of $T$, a contradiction to Lemma \ref{easy}.

The only remaining case is $w_2,y \in L(Q_1^*)$, $z_1 \notin
L(Q_1^*)$, $y,z_1 \in L(Q_2^*)$, and $w_2 \notin
L(Q_2^*)$. Let $L(Q_1^*) \cap L(Q_2^*) =
\{y,x_2,w_3\}$. In view of Lemma \ref{2trees} the edge sets in the phylogenetic tree with leaf set
$\{y,x_2,w_3\}$ that have to be subdivided to obtain $T|_{L(Q_1)}$ respectively $T|_{L(Q_2)}$ are disjoint. On the other hand, $\{w_1,x_1\}$ is a cherry of $T|_{L(Q_2)}$ while $w_2$ is in $L(Q_1)$. Since
$w_1x_1|w_2y$ distinguishes an edge of $T$ it follows that
$w_2y|x_2w_3$ is not displayed by $T$. Hence, we can assume without loss of generality that $T$ displays $w_2x_2|w_3y$.
Further, we have $Q_1=Q_1^*$ thus there is a $Q_1$-hierarchy.
Let $T_2^*$ be the tree defined by $Q_2^*$. Then the edge of the phylogenetic tree with leaf set
$\{x_2,w_3,y\}$ that is incident with $w_2$ does not have to be subdivided to obtain $T_2^*$.
Therefore, $Q_2^*+w_2x_2|yw_3$ is definitive. Further, the quartet set
$Q_2^+:=Q_2+w_2x_2|yw_3+w_1x_1|w_2y$ is definitive since every tree that displays $Q_2^+$
is compatible with the tree defined by $Q_1$ in view of Lemma \ref{2trees}, and $Q_2^+$ is excess-free.
If  $|Q_1|>1$, then $|Q_2^+|<Q$ thus, by induction hypothesis, there is a
$(Q_2+w_1x_1|w_2y+w_2x_2|w_3y)$-hierarchy and we can construct a $Q$-hierarchy in the same way as for the case $z_1 \in L(Q_1^*) \cap L(Q_2^*)$. Hence,
$Q_1=\{w_2x_2|w_3y\}$ thus $\{w_2,x_2\}$ is a cherry of $T$ and
$w_1x_1|w_2y$ and $w_2x_2|w_3y$ are the only two quartets in $Q$ which
contain $w_2$.

We have shown that, for every cherry $\{w,x\}$ of $T$ with $wx|w'y'
\in Q$, there is $z' \in \{w',y'\}$ such that the following statements hold:
\begin{enumerate}
\item [(P1)]
$z'$ is contained in a cherry $\{z',x'\}$ of $T$.
\item[(P2)]
There are exactly two quartets in $Q$ which contain $z'$.
\item [(P3)]
There is $w'' \in L(T)$ such that $w'x'|w''y' \in Q$ (if $z'=w'$) or $x'y'|w'w'' \in Q$ (if $z'=y'$).

\end{enumerate}
We will use Properties (P1)--(P3) of $Q$ and $T$ to show that, for every natural number $i$, the following statements hold:
\begin{enumerate}
\item [(P4)]
There is a leaf set $L_i=\{w_j:1 \le j \le i+1\}\cup \{x_j:1 \le j \le i\} \cup \{y\} \subset L(T)$ of cardinality $2i+2$ such that $T|_{L_i}$ is the phylogenetic tree $T_i$ with vertex set $L_i \cup \{u_j,v_j:1 \le j \le i\}$ and edge set $\{ yu_1\}\cup\{u_jv_j,v_jw_j,v_jx_j,u_ju_{j+1}:1\le j\le i\}$ where we define $u_{i+1}=w_{i+1}$.
\item [(P5)]
$\{w_i,x_i\}$ is a cherry of $T$.
\item[(P6)]
$w_ix_i|w_{i+1}y \in Q$.

\end{enumerate}
This will complete the proof of the theorem since it contradicts the finiteness of $T$.

We have already shown that all claimed statements hold for $i \le 2$. Assume $i \ge 3$ and that all claimed statements are true for smaller $i$. Since, by induction hypothesis, $\{w_{i-1},x_{i-1}\}$ is a cherry of $T$ in view of (P5)  and $w_{i-1}x_{i-1}|w_iy \in Q$ in view of (P6), (P1) implies that there is a leaf $x_i$ of $T$ and $z \in \{w_i,y\}$ such that $\{z,x_i\}$ is a cherry of $T$. Since $T|_{L_{i-1}}=T_{i-1}$ we have $x_i \notin L_{i-1}$. By (P2), there are exactly two quartets in $Q$ which contain $z$. Since $y$ is contained in the quartets $w_1x_1|w_2y$ and $w_2x_2|w_3y$ and there is a quartet containing $x_i$ and $y$ if $\{x_i,y\}$ is a cherry of $T$ we can not have $z=y$.
Hence, $z=w_i$ and (P3) implies that there is $w_{i+1} \in L(T)$ with $w_ix_i|w_{i+1}y \in Q$.  Since $w_ix_i|w_{i+1}y$ distinguishes an edge of $T$ we have $T|_{L_i}=T_i$.
\epf

The characterization of excess-free defining quartet sets which was originally published in \cite{bds99} is an easy
consequence of Theorem~\ref{hard}.

\begin{corollary}
\label{char}
Let $T$ be a binary phylogenetic $X$-tree and let $Q$ be an
excess-free quartet set displayed by $T$ with $L(Q)=L(T)$. Then $Q$
defines $T$ if and only if (i)~every interior edge of $T$ is
distinguished by a quartet in $Q$ and (ii)~$\Exc(Q)$ contains a
maximal hierarchy.
\end{corollary}
\pf
If $Q$ defines $T$ then (i) follows from Lemma \ref{easy} and (ii)
from Theorem \ref{hard}. Conversely, we use induction on $|L(T)|$ to
show that $Q$ defines $T$ if (i) and (ii) hold. This is clearly true
if $|L(Q)|=4$ thus we can assume that $|L(Q)| \ge 5$ and there is a
maximal hierarchy contained in $\Exc(Q)$ where $Q_1$ and $Q_2$
are the children of $Q$. By induction hypothesis, $Q_1$ and $Q_2$
define binary trees $T_1$ and $T_2$, respectively. For $i \in
\{1,2\}$, every quartet in $Q_i$ distinguishes an interior edge of
$T$. Hence, the interior edges of $T_i$ are not subdivided in the
smallest subtree of $T$ containing
$L(T_i)$. Therefore, the interior edges of $T$ distinguished by a
quartet in $Q_i$ induce a connected
subgraph $T_i'$ of $T$ which implies that $T_1'$ and $T_2'$ have
exactly one vertex $v$ in common. Let $L(T_1) \cap
L(T_2)=\{x,y,z\}$. By symmetry, we can assume that $\{x,y\}$ is a
cherry of $T_1$ and $z$ is an isolated vertex in the graph obtained
from $T_2$ by removing the path from $x$ to $y$. Hence, only the edge of the phylogenetic tree with leaf set $\{x,y,z\}$ that is incident with $z$ has to be subdivided to obtain $T_1$ while one or both of the other edges have to be subdivided to obtain $T_2$. Therefore, Lemma \ref{2trees} implies that $T_1$ and $T_2$ define $T$, thus $Q$ defines $T$.
\epf

We conclude the paper by pointing out one of the algorithmic
consequences of Corollary \ref{char} that are studied in
\cite{bbds00}.

\begin{corollary}
It can be decided in polynomial time if an excess-free quartet set $Q$
is definitive and then the phylogenetic tree displaying $Q$ can be
reconstructed in polynomial time.
\end{corollary}

\section*{Acknowledgment}
I thank the  Allan Wilson Centre for Molecular Ecology and Evolution and the Department of Mathematics and Statistics, University of Canterbury in Christchurch, New Zealand where I worked when I found the presented results and I thank Mike Steel for fruitful discussions. I would like to thank Meng Chen and Katharina Huber for their comments on earlier versions of this paper.


TITLE: Does the human body have a resonant frequency? If so, how strong is it?
QUESTION [21 upvotes]: Inspired by this question on Music beta SE, I'm wondering if the human body has a strong resonant frequency. I guess the fact that it's largely a bag of jelly would add a lot of damping to the system, but is that enough to dampen it entirely?
What models for resonance might be used to model the human body? (E.g. weight-on-a-spring, with legs as springs?) What about individual, semi-independent body parts, like legs, or lung cavity (acoustic resonance?).

REPLY [0 votes]: This here is an experimental paper about the mechanical vibrations total resonance (i.e. the discrete frequency where it is found  a human body as a whole resonates mostly):
Discussion of human resonant frequency
also found here.
"...found the human whole-body fundamental resonant frequency to be around 5 Hz. However, in recent years, an indirect method has been prosed which appears to increase the resonant frequency to approximately 10 Hz. To explain this discrepancy, experimental work was carried out in NTU. The study shows that the discrepancy lies in the vibration magnitude used in the tests. A definition of human natural frequency in terms of vibration magnitude is proposed."
The analysis of the experimental results of this paper lead to an important conclusion made by the authors that this resonant frequency is amplitude depended in some extend thus it can vary depending the amplitude of the mechanical vibrations.
"...that the higher the vibration magnitude, the lower the detected
human resonant frequency. Therefore, the definition of the human resonant frequency
should refer to the vibration magnitude. This paper suggests that, for practical purpose where the vibration magnitude is higher than 0.1 ms-2 (such as in the study of earthquake and traffic), the human resonant frequency could be assumed in the range of 3 to 7 Hz."
Also another conclusion the authors of this paper making is that most of the vibrations can be dumped by the human depending also by muscle-tension:
"...There is slight difference between various postures. If we refer
to the muscle tension, it can be suspected that tensed postures can damp the vibration more effectively than the relaxed ones"


TITLE: Inverse Laplace Transform of $\frac{s}{(s-a)^{3/2}}$
QUESTION [3 upvotes]: Find the inverse laplace of: $\frac{s}{(s-a)^{3/2}}$
I tried working through this using partial fractions and convolution but I can't seem to get a requitible answer. How would I go about solving this? (by the way, we have yet to learn the integral definition of inverse laplace transforms, so we are expected not to use that.)

REPLY [2 votes]: Somehow, I missed the part about not using the definition of the ILT.  However, since I invested a lot of effort into the solution and I think it demonstrates some interesting techniques I have not seen used here on M.SE, I will keep the solution posted.
Let's assume that $a \in \mathbb{R}$.  The definition of the ILT is as follows:
$$f(t) = \frac1{i 2 \pi} \int_{c-i \infty}^{c+i \infty} ds \frac{s}{(s-a)^{3/2}} e^{s t} $$
where $c \gt a$.  We evaluate using Cauchy's theorem by considering the following contour integral:
$$\oint_C dz \frac{z}{(z-a)^{3/2}} e^{z t} $$
where $C$ is a deformed Bromwich contour closed to the left of outer radius $R$ with a small circular contour of radius $\epsilon$ about the pole/branch point on the real axis.  As the integral about the outer circular arcs vanish as $R \to \infty$, the contour integral is equal to
$$\int_{c-i \infty}^{c+i \infty} ds \frac{s}{(s-a)^{3/2}} e^{s t} + e^{i \pi} \int_{\infty}^{-a+\epsilon} dx \frac{e^{i \pi} x}{(e^{i \pi} x-a)^{3/2}} e^{-x t} \\ + i \epsilon \int_{\pi}^{-\pi} d\phi \, e^{i \phi} \frac{a+\epsilon e^{i \phi}}{\epsilon^{3/2} e^{i 3 \phi/2}} e^{(a+\epsilon e^{i \phi}) t} + e^{-i \pi} \int_{-a+\epsilon}^{\infty} dx \frac{e^{-i \pi} x}{(e^{-i \pi} x-a)^{3/2}} e^{-x t}$$
Now it appears that the expression above diverges as $\epsilon \to 0$, but that is not the case because the divergences cancel.  Note that the third integral behaves as
$$\begin{align} i \epsilon \int_{\pi}^{-\pi} d\phi \, e^{i \phi} \frac{a+\epsilon e^{i \phi}}{\epsilon^{3/2} e^{i 3 \phi/2}} e^{(a+\epsilon e^{i \phi}) t} &= i a e^{a t} \epsilon^{-1/2} \int_{\pi}^{-\pi} d\phi\, e^{-i \phi/2} + O \left (\epsilon^{1/2} \right ) \\ &=-i 4 a e^{a t} \epsilon^{-1/2}+ O \left (\epsilon^{1/2} \right ) \end{align}$$
This is of course divergent as $\epsilon \to 0$.  However, the second and fourth integrals also have divergences.  For example, the second integral may be written as:
$$\begin{align} e^{i \pi} \int_{\infty}^{-a+\epsilon} dx \frac{e^{i \pi} x}{(e^{i \pi} x-a)^{3/2}} e^{-x t} &= e^{a t} \int_{\infty}^{\epsilon} dy \frac{y-a}{e^{i 3 \pi/2} y^{3/2}} e^{-y t} \\ &= -i e^{a t} \int_{\epsilon}^{\infty} dy \, y^{-1/2} e^{-y t} + i a e^{a t} \int_{\epsilon}^{\infty} dy \, y^{-3/2} e^{-y t} \\ &= -i e^{a t} \sqrt{\frac{\pi}{t}} + O \left (\epsilon^{1/2} \right ) + i a e^{a t} \epsilon^{-1/2} \int_{1}^{\infty} du \, u^{-3/2} e^{-\epsilon t u} \end{align} $$
Now, it turns out that the latter integral is related to an incomplete gamma function and has the following behavior as $\epsilon \to 0$:
$$\int_{1}^{\infty} du \, u^{-3/2} e^{-\epsilon t u} = 2-2 \sqrt{\pi t} \epsilon^{1/2} + O(\epsilon) $$
Thus,
$$e^{i \pi} \int_{\infty}^{-a+\epsilon} dx \frac{e^{i \pi} x}{(e^{i \pi} x-a)^{3/2}} e^{-x t} = i 2 a e^{a t} \epsilon^{-1/2} -i e^{a t} \sqrt{\frac{\pi}{t}}  - i 2 a \sqrt{\pi t} e^{a t} + O \left (\epsilon^{1/2} \right )$$
Similarly, the fourth integral may be written as
$$e^{-i \pi} \int_{-a+\epsilon}^{\infty} dx \frac{e^{-i \pi} x}{(e^{-i \pi} x-a)^{3/2}} e^{-x t} = i 2 a e^{a t} \epsilon^{-1/2} -i e^{a t} \sqrt{\frac{\pi}{t}}  - i 2 a \sqrt{\pi t} e^{a t} + O \left (\epsilon^{1/2} \right )$$
Summing the results for the second, third, and fourth integrals, we see that the terms in $\epsilon^{-1/2}$ cancel, and we are left with
$$\int_{c-i \infty}^{c+i \infty} ds \frac{s}{(s-a)^{3/2}} e^{s t} -i 2 e^{a t} \sqrt{\frac{\pi}{t}}  - i 4 a \sqrt{\pi t} e^{a t}$$
By Cauchy's theorem, the contour integral - and therefore the above expression - is equal to zero.  The sought-after ILT is then found to be
$$\frac1{i 2 \pi} \int_{c-i \infty}^{c+i \infty} ds \frac{s}{(s-a)^{3/2}} e^{s t} = \frac{1+2 a t}{\sqrt{\pi t}} e^{a t} $$
This of course assumed $t \gt 0$.  For $t \lt 0$, the ILT is zero.


TITLE: Is it possible to surpass the diffraction limit for telescopes?
QUESTION [5 upvotes]: Telescopes have angular diffraction limit depending on the observed wavelength and aperture diameter.
I've read that it's possible to go beyond the limit for microscopes. But is it possible to do the same for telescopes too?

REPLY [0 votes]: In microscopy you can get super-resolved images, either as mentioned before going in the near field (atomic force microscope, NSOM..), or all-optically in the far field. All the super resolution techniques in the far field involve fluorescence. In PALM-STORM you tag your sample with fluorophores which are photo-switchable and you let them blink on-off so to have their point spread functions (PSF) not overlapping at the same time, you find the center of each PSF with nm accuracy and you reconstruct the entire sample image by many different images where only few separated PSFs are present.
In STED, you engineer the shape of the PSF of the excitation laser source, using stimulated emission to reduce the excitation size down to few 10s of nm. In SIM, you also use a smart illumination scheme.
So in telescopes, this kind of super resolution seems impossible without the ability to go to the near field or to engineer the emission or excitation.


TITLE: Best approximation of a function out of a closed subset
QUESTION [1 upvotes]: I'm studying approximation theory and I saw this exercise on Rivlin book an introduction to the approximation of functions:
Prove that if $V$ is a normed linear space, $W$ a finite-dimensional subspace of $V$, and $U$ a closed subset of $W$, then, given $v\in V$, there exists $u^*\in U$ such that $\Vert v-u^*\Vert\le\Vert v-u\Vert $ for all $u\in U$.
my approach is as follows:
$dist(v,U)=inf\Vert v-u\Vert_{u\in U}$
by definition of infimum there exists a sequence $[u_i]$ in $U$ such that $lim_{i\to \infty}\Vert v-u_i \Vert=dist(v,U)$ since $U$ is closed it contains all it's limit points and $u^*=dist(v,U)$ belongs to $U$.
so I didn't use the assumption that W is a finite-dimensional subspace.
Am I missing something here? if yes any hints on the correct proof would be so appreciated.

REPLY [2 votes]: Your mistake is that from $\lim_{i\to\infty}\|v-u_i\|=dist(v,U)$ you have concluded that $u_i$ has a limit point. The limit above is in $\mathbb R$, but this does not imply that the original sequence $u_i$ has any limit points.
However, if $W$ is finite-dimensional, then the set $\{u_i:i\in\mathbb N\}\subseteq W$ is bounded and therefore has a limit point. (See e.g. https://math.stackexchange.com/a/144491/491874 for discussion about why it is.) That is the missing ingredient.


text:
\begin{document}

\maketitle
\begin{abstract}
We propose to tackle the problem of understanding the effect of regularization in Sinkhorn algotihms. In the case of Gaussian distributions we provide a closed form for the regularized optimal transport which enables to provide a better understanding of the effect of the regularization from a statistical framework.
\end{abstract}

\section{Introduction.}

Statistical methods based on optimal transportation have received a considerable amount of attention in recent times. While the topic has a long history,
computational limitations (and also lack of a well developed distributional theory) hampered its applicability for years. Some recent advences (see Cuturi, Peyre, Schmitzer, Rigollet,...) have completely changed the scene and now statistical methods based on optimal transportation are everywhere (see, e.g.\cite{peyre2019computational},for Kernel based methods \cite{Kolouri_2016_CVPR,bachoc2017gaussian}, in Fair Machine Learning \cite{gordaliza2019obtaining}).

Monge-Kantorovich distances are defined using a cost function $c$ as
$$W_c(P,Q)= \min_{\pi \in \Pi(P,Q)} \int c(x,y) d\pi(x,y),$$
where $\Pi(P,Q)$ denotes the set of distributions  with marginals $P$ and $Q$. \\ Computing such distances requires to solve  in the discrete case a linear program. Actually solving the original discrete optimal transport problem, for two discrete distributions
$P=\sum_{i=1}^n p_i \delta_{x_i}$ and $Q=\sum_{i=1}^m q_i \delta_{y_i}$ and a cost matrix $c$ $c_{ij}=c(x_i,y_j)$ for all $(i,j)\in [1,n]\times [1,m]$,  amounts to solve the minimization with respect to $\pi$ the transportation plan \begin{equation} \label{otemp}\min_{ \pi \in \Pi(P,Q)} <c,\pi>  \end{equation}
 $\Pi(P,Q)=\{ \pi \in \mathbb{R}^{n\times n }_{+}, \: \pi \mathds{1}_n = P , \:  \pi^T \mathds{1}_m = Q \}$
where $ \pi \mathds{1}_n=(\sum_{j=1}^n \pi_{ij})_i$ and  $ \pi^T \mathds{1}_m=(\sum_{j=1}^m \pi_{ij})_j$. This minimization  is yet a linear problem (see \cite{kantorovich1942translocation}) but it turns to be  computationally difficult. Different algorithms have been proposed such as the Hungarian algorithm \cite{kuhn1955hungarian}, the simplex algorithm \cite{luenberger1984linear} or others versions using interior points algorithms \cite{orlin1988faster}. The complexity of these methods is at most of order $O(n^3 \log(n))$ for the OT problem between two discrete distributions with equal size $n$. \vskip .1in
To overcome this issue, regularization methods have been proposed to approximate the optimal transport problem by adding a penalty. The seminal paper by \cite{cuturi2013sinkhorn} provides the description of the Sinkhorn algorithm to regularize  optimal transport by using the  entropy of the transportation plan
$ H(\pi)= \sum_{i,j} \pi_{ij} \log(\pi_{ij}),$ and changing the initial optimization program \eqref{otemp} into a strictly convex one
\begin{equation} \label{otempreg}\min_{ \pi \in \Pi(P,Q)} \{  <c,\pi>  + \varepsilon H(\pi) \}. \end{equation}
The minimization of this criterion is achieved using Sinkhorn algorithm. We refer to \cite{peyre2019computational} and references therein for more details.
The introdution of the Sinkhorn divergence enables to obtain an $\varepsilon$-approximation of the optimal transport distance which can be computed, as pointed out in \cite{altschuler2017near},  with a  complexity of algorithm  of order $O(\frac{n^2}{\varepsilon^3})$, hence in a much faster way than the original optimal transport problem. Several toolboxes have been developed to compute regularized OT such among others as \cite{flamary2017pot} for python, \cite{klatt2017package} for R. \\
Other algorithms can be used to minimize \eqref{otempreg}. In~\cite{genevay2016stochastic} stochastic gradient
descent is applied to solve the entropy-regularized OT problem while in~\cite{dvurechensky2018computational} an accelerated gradient descent is proposed improving the complexity to  $O(\min (\frac{n^2}{\varepsilon^2}, \frac{n^{9/4}}{\varepsilon}))$.  \vskip .1in
The influence of the penalty is balanced introducing a parameter $\varepsilon >0 $ which controls the balance between the approximation of the optimal transport distance and its computational feasibility. Note also that others regularizing penalty have been proposed, for instance the entropy with respect to the product of marginals . \vskip .1in
 Beyond computational convenience, regularization has a statistical impact  and few results exist in the literature.  An enjoyable property of regularized optimal transport is that the convergence of its empirical version is faster than the standard optimal transport. Actually, if $P_n$ and $Q_n$ are empirical versions of distributions $P$ and $Q$ in $\mathbb{R}^d$, then Monge-Kantorovich distances suffer from the curse of dimensionality and converge under some assumptions at a rate at most $n^{-1/d}$, this rate may be improved under some assumptions as pointed out in \cite{weed2019sharp} for instance. As shown first in \cite{genevay2019sample} for  distributions defined on a bounded domain,  and sharpened for sub-Gaussian distributions in \cite{mena2019statistical}, the rate of convergence of regularized OT divergences is of order $\frac{1}{\varepsilon^{2+[5d/4]}} / {\sqrt{n}} $. \vskip .1in
In the recent years, optimal transport theory has been extensively used in unsupervised learning in order to characterize the mean of observations, giving rise to the notion of Wasserstein barycenters. This point of view is closely related to the notion of Fr\'echet means which has been used in statistics in preliminar works such as \cite{dupuy2011non} . The problem of existence and uniqueness of the Wasserstein barycenter of distributions $P_1,\dots,P_k$, where at least one of these distributions has a density, has been tackled in \cite{agueh2011barycenters}. The asymptotic property of Wasserstein barycenters have been studied in \cite{boissard2015distribution} or \cite{le2017existence}.
     However their computation is a difficult issue apart from the scatter-location family case. In this case a fixed point solution method can be derived to compute their barycenter as explained in \cite{alvarez2016fixed}. Hence, some authors have replaced Monge-Kantorovich distance by the Sinkhorn divergence and thus have considered the notion of Sinkhorn barycenter as  in \cite{cuturi2014fast} or \cite{bigot2019penalization}. In this setting, the distributions are discretized and the usual Sinkhorn's algorithm for discrete distributions is applied. Results proving the consistency of empirical Sinkhorn barycenters towards population Sinkhorn barycenters can be derived and the rate of convergence can be upper bounded by a bound depending on the number of observations, the discretization scheme and the trade-off parameter $\varepsilon$. Here again little is said to derive the statistical properties of the Sinkhorn barycenter and its property with respect to the original Wasserstein barycenter. \vskip .1in
 Hence, for both computational and statistical properties, the influence of $\varepsilon$ is crucial  and the results dealing with the approximation properties of regularized OT with regards to standard OT are scarce.  Very recently some papers all independently have proved in~\cite{janati2020entropic} similar expressions for the closed form of regularized optimal transport between Gaussian distributions, including in their case the case of unbalanced transport. In \cite{mallasto2020entropyregularized},  similar formulations have been derived using proofs based on the solution of the Schr\"odinger system that can be written to compute the entropic transport plan. All three points of view are complementary and provide new insights on entropic optimal transport.
 \vskip .1in
 Our contribution is the following

\begin{itemize}

 \item We investigate in this paper this impact
 \item We find that optimal regularized coupling of Gaussian measures is Gaussian and compute regularized transportation cost between Gaussians (Theorem \ref{GaussianEntropicTC})
 \item The Gaussian case is not just an interesting benchmark. In fact, just as in the classical (unregularized) optimal transportation problem,
 for probabilities with given means and covariance matrices the entropic transportation cost is minimized for Gaussian distributions. This is a generalization of Gelbrich lower bound the entropic setup (Theorem \ref{EntropicGelbrich}).
 \item Also as in the classical case, the entropic barycenter of Gaussian probabilities is Gaussian (Theorem \ref{entropic_Gaussian_barycenter}).
 \item Entropic variation around barycenter lower bounded by explicit expression from Gaussian case
 \item We see that entropic regularization basically amounts to smoothing via convolution with a Gaussian kernel, which results in
 added variance. The regularization parameter controls the increase in variance

\end{itemize}

\section{Regularized optimal transport.}

We consider the entropic regularization of the transportation cost, namely, for
probabilities $P$, $Q$ on $\mathbb{R}^d$,
$$\mathcal{W}^2_{2,\varepsilon}(P,Q)=\min_{\pi\in\Pi(P,Q)} I_\varepsilon[\pi]$$
with
\begin{equation}\label{W2e}
I_\varepsilon[\pi]=\int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\pi(x,y)
+\varepsilon H(\pi).
\end{equation}
Here $H$ stands for the negative of the differential or  Boltzmann-Shannon entropy, that is, if
$\pi$ has density $r$ with respect to Lebesque measure on $\mathbb{R}^d\times \mathbb{R}^d$, then
$$H(\pi)=\int_{\mathbb{R}^d\times \mathbb{R}^d} r(x,y)\log r(x,y)dxdy,$$
while $H(\pi)=+\infty$ if $\pi$ does not have a density.

\medskip
The entropy term $H$ modifies the linear term in classical optimal transportation (the quadratic transportation cost)
to produce a strictly convex functional. This is not the only possible choice. Alternatively, we could
fix two reference probability measures on $\mathbb{R}^d$, say $\mu$ and $\nu$, and
consider
$$\mathcal{W}^2_{2,\varepsilon,\mu,\nu}(P,Q)=\min_{\pi\in\Pi(P,Q)} I_{\varepsilon,\mu,\nu}[\pi]$$
where
\begin{equation}\label{W2emunu}
I_{\varepsilon,\mu,\nu}[\pi]=\int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\pi(x,y)
+\varepsilon K(\pi|\mu\otimes \nu)
\end{equation}
and $K$ denotes the Kullback-Leibler divergence, namely, for probability measures, $\rho$, $\eta$, $K(\rho\|\eta)=\int \log \frac{d\rho}{d\eta} d\rho$
if $\rho\ll \eta$ and $K(\rho\|\eta)=+\infty$ otherwise. In the case when $\mu=\nu$
is the centered normal distribution on $\mathbb{R}^d$ with covariance matrix, $\lambda I_d$, for some $\lambda>0$, we will simply write
$I_{\varepsilon,\lambda}[\pi]$ and $\mathcal{W}^2_{2,\varepsilon,\lambda}(P,Q)$.

In our definitions of the regularized transportation cost we have written $\min$ instead of $\inf$. The existence of the minimizer follows easily.
In the case of $\mathcal{W}^2_{2,\varepsilon,\mu,\nu}(P,Q)$, for instance, let us assume that $\pi_n\in\Pi(P,Q)$ is a minimizing sequence, that is,
$I_{\varepsilon,\mu,\nu}[\pi_n]\to\inf_{\pi\in\Pi(P,Q)} I_{\varepsilon,\mu,\nu}[\pi]=m<\infty$. Since $\pi_n$ have fixed marginals, $\{\pi_n\}$
is a tight sequence and we can extract a weakly convergent subsequence, that we keep denoting $\pi_n$, say $\pi_n\to\pi_0$. Obviously $\pi_0\in \Pi(P,Q)$.
By Fatou's Lemma $\int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\pi(x,y)\leq \liminf_n \int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\pi_n(x,y)$
and by lower semicontinuity of relative entropy (see, e.g., Lemma 1.4.3 in \cite{DupuisEllis}) $K(\pi_0|\mu\otimes\nu)\leq \liminf_n K(\pi_n|\mu\otimes\nu)$.
But this shows that $I_{\varepsilon,\mu,\nu}[\pi_0]\leq \liminf_n I_{\varepsilon,\mu,\nu}[\pi_n]=m$, hence, $\pi_0$ is a minimizer. The case of $\mathcal{W}^2_{2,\varepsilon}(P,Q)$ follows similarly. Futhermore, if the transportation cost is finite then the minimizer is unique, since the relative entropy is strictly convex in its domain.

The choice of the reference measures is arbitrary. However, its influence on the regularized
optimal transport is limited. In fact, if we replace $\mu$, $\nu$ with equivalent measures $\mu'$, $\nu'$ (in the sense of $\mu$ and $\mu'$ being
mutually absolutely continuous with respect to each other and similarly for $\nu$ and $\nu'$) then $\pi\ll \mu\otimes \nu$ if and only if $\pi\ll \mu'\otimes \nu'$ and
then $\frac{d\pi}{d(\mu'\otimes \nu')}=\frac{d\pi}{d(\mu\otimes \nu)}\big/ \Big(\frac {d\mu'}{d\mu} \frac {d\nu'}{d\nu} \Big)$.
Hence, for any $\pi\in \Pi(P,Q)$ with $\pi\ll \mu\otimes \nu$, writing $r=\frac{d\pi}{d(\mu\otimes \nu)}$ we have
\begin{equation}\label{red1}
K(\pi\| \mu\otimes \nu)-K(\pi\| \mu'\otimes \nu')=\int_{\mathbb{R}^d} \log\big(\textstyle \frac {d\mu'}{d\mu}(x)\big)dP(x)+\int_{\mathbb{R}^d} \log\big(\textstyle \frac {d\nu'}{d\nu}(y)\big)dQ(y)
\end{equation}
and we see that the difference does not depend on $\pi$. In particular the minimizer, if it exists, does not depend on the choice of $\mu$, $\nu$.
Furthermore, if $\mu$ and $\nu$ have a positive density on $\mathbb{R}^d$ then $I_\varepsilon[\pi]$ and $I_{\varepsilon,\mu,\nu}[\pi]$
differ only in a constant and, again, the minimizer does not depend on the choice of $\mu$, $\nu$. The minimal value, however, does depend
on the choice of the regularization term and this has an impact, for instance, in the barycenter problem, as we will see later.

\bigskip
We prove in this section that the entropic regularization of the transportation problem between nondegenerate Gaussian laws admits a
(unique) minimizer which is also Gaussian (on the product space). We provide a explicit expression for the mean and covariance
of this minimizer. Our proof is self-contained in the sense that we prove the existence of a minimizer in this setup. This existence
could be obtained from more general results (see, e.g., Theorem 3.2 in \cite{Chizatetal} or Remark 4.19 in \cite{peyre2019computational}) based
on duality. We obtain the minimizer, instead, from the analysis of a particular type of matrix equation: the so-called algebraic Riccatti
equation. This equation has been extensively studied (see \cite{LancasterRodman1995}) and efficient numerical methods for the computation
of solutions are available (see, e.g., \cite{BiniIanazzoMeini2012}). However, the particular Riccatti equation which is of interest for
the entropic transportation problem (see (\ref{Riccatti})) has a particularly simple structure and
its unique positive definite solution admits an explicit expression. This is shown in our next result.

\begin{Proposition} \label{RiccattiSolutions} If $\Sigma_1$, $\Sigma_2$ are real, symmetric, positive definite $d\times d$ matrices and $\varepsilon > 0$ then the
unique symmetric, positive definite solution of the matrix equation
\begin{equation}\label{Riccatti}
X\Sigma_1X +\textstyle \frac \varepsilon  2 X= \Sigma_2
\end{equation}
is
\begin{equation}\label{RiccattiSol}
X_\varepsilon=\Sigma_1^{-1/2} \big(\Sigma_1^{1/2}\Sigma_2 \Sigma_1^{1/2}+\textstyle (\frac \varepsilon 4)^2 I_d \big)^{1/2} \Sigma_1^{-1/2}-\textstyle \frac \varepsilon 4 \Sigma_1^{-1}.
\end{equation}
Furthermore, if
$$\Sigma_\varepsilon=\left[
\begin{matrix}
\Sigma_1 & \Sigma_1 X_\varepsilon \\
X_\varepsilon \Sigma_1 &\Sigma_2
\end{matrix}
\right]
$$
then $\Sigma_\varepsilon$ is a real, symmetric, positive definite $2d\times 2d$ matrix and
$$\Sigma_\varepsilon^{-1}=\left[
\begin{matrix}
\Sigma_1^{-1}+\frac 2 \varepsilon X_\varepsilon & -\frac{2}{\varepsilon} I_d \\
-\frac{2}{\varepsilon} I_d &\frac 2 \varepsilon X_\varepsilon^{-1}
\end{matrix}
\right].
$$
\end{Proposition}

\bigskip
\noindent
\textbf{Proof.} The fact that $X_\varepsilon$ solves (\ref{Riccatti}) can be checked by simple inspection. $X_\varepsilon$ is obviously symmetric. Hence, it suffices to show that it is positive definite or, equivalently, that $\big(\Sigma_1^{1/2}\Sigma_2 \Sigma_1^{1/2}+\textstyle (\frac \varepsilon 4)^2 I_d \big)^{1/2}-\textstyle \frac \varepsilon 4 I_d$ is positive definite.
This, in turn, will follow if we prove that every eigenvalue,
say $\lambda$, of $\big(\Sigma_1^{1/2}\Sigma_2 \Sigma_1^{1/2}+\textstyle (\frac \varepsilon 4)^2 I_d \big)^{1/2}$ satisfies $\lambda >\frac\varepsilon 4$.
But this is a consequence of the fact that the eigenvalues of
$\big(\Sigma_1^{1/2}\Sigma_2 \Sigma_1^{1/2}+\textstyle (\frac \varepsilon 4)^2 I_d \big)^{1/2}$ are $\sqrt{s+(\frac \varepsilon 4)^2}$ with $s$ ranging in the set of eigenvalues
of $\Sigma_1^{1/2}\Sigma_2 \Sigma_1^{1/2}$, which is positive definite. Consequently, $X_\varepsilon$ is a positive definite solution of (\ref{Riccatti}).
To prove uniqueness we set $Z=\frac \varepsilon 4I_d+\Sigma_1 X$ and note that if $X$ is a solution to (\ref{Riccatti}) then
\begin{equation}\label{uniqueness}
XZ=\Sigma_2-\textstyle\frac \varepsilon 4 X.
\end{equation}
But then $X=\Sigma_1^{-1}(Z-\frac \varepsilon 4 I_d)$ and substitution in (\ref{uniqueness}) yields
$$\Sigma_2+\textstyle\big(\frac\varepsilon 4 \big)^2\Sigma_1^{-1} =\Sigma_1^{-1} Z^2$$
or, equivalently,
$$Z^2=\Sigma_1\Sigma_2 +\textstyle\big(\frac\varepsilon 4 \big)^2 I_d.$$
Observe now that $A:=\Sigma_1^{-1/2}Z\Sigma_1^{1/2}$ is a symmetric, positive definite matrix. From the last identity
we see that
$$A^2=\Sigma_1^{-1/2}Z^2\Sigma_1^{1/2}=\Sigma_1^{1/2}\Sigma_2\Sigma_1^{1/2} +\textstyle\big(\frac\varepsilon 4 \big)^2 I_d.$$
Therefore, $A=(\Sigma_1^{1/2}\Sigma_2\Sigma_1^{1/2} +\textstyle (\frac\varepsilon 4 )^2 I_d)^{1/2}$. We conclude that, necessarily, $X=X_\varepsilon$.

We show next that $\Sigma_\varepsilon$ is positive definite. In fact, (see, e.g., Theorem 1.3.3 in \cite{Bhatia}) it suffices to show that
$\Sigma_1-\Sigma_1 X_\varepsilon \Sigma_2^{-1}X_\varepsilon \Sigma_1$ is positive definite. Since $X_\varepsilon$ solves (\ref{Riccatti}),
we have that $X_\varepsilon^{-1}\Sigma_2 X_\varepsilon^{-1}=\Sigma_1+\frac \varepsilon 2  X_\varepsilon^{-1}$ and the last condition becomes
that $\Sigma_1-\Sigma_1  (\Sigma_1+\frac  \varepsilon 2 X_\varepsilon^{-1})^{-1}\Sigma_1$ has to be positive definite. But this holds
if and only if
$$U=\left[
\begin{matrix}
\Sigma_1 & \Sigma_1 \\
 \Sigma_1 &\Sigma_1+ \frac \varepsilon 2 X_\varepsilon^{-1}
\end{matrix}
\right]
$$
is positive definite. Since $[x^T y^T]U[x^T y^T]^T=(x+y)^T\Sigma_1(x+y)+ \frac \varepsilon 2 y^T X_\varepsilon^{-1}y$, we conclude
that $\Sigma_\varepsilon$ is indeed positive definite.

To complete the proof we note that from the well known
identity for the inverse of block partitioned matrices
$$\Sigma_\varepsilon^{-1}=\left[
\begin{matrix}
(\Sigma_1-\Sigma_1 X_\varepsilon \Sigma_2^{-1} X_\varepsilon\Sigma_1 )^{-1} & -X_\varepsilon(\Sigma_2-X_\varepsilon \Sigma_1 X_\varepsilon )^{-1} \\
-(\Sigma_2-X_\varepsilon \Sigma_1 X_\varepsilon )^{-1}X_\varepsilon &(\Sigma_2-X_\varepsilon \Sigma_1 X_\varepsilon )^{-1}
\end{matrix}
\right],
$$
Since $X_\varepsilon$ solves (\ref{Riccatti}) we have that $(\Sigma_2-X_\varepsilon \Sigma_1 X_\varepsilon )^{-1}=\frac 2 \varepsilon X_\varepsilon^{-1}$.
We similarly check that $(\Sigma_1-\Sigma_1 X_\varepsilon \Sigma_2^{-1} X_\varepsilon\Sigma_1 )(\Sigma_1^{-1}+\frac 2 \varepsilon X_\varepsilon)
={I_d+\frac 2 \varepsilon \Sigma_1 X_\varepsilon-\Sigma_1 X_\varepsilon \Sigma_2^{-1} X_\varepsilon-\frac 2 \varepsilon\Sigma_1 X_\varepsilon \Sigma_2^{-1} X_\varepsilon\Sigma_1X_\varepsilon}=I_d$.
This completes the proof.\hfill $\Box$

\bigskip
\begin{Remark}\label{AltForm}
The inverse of the solution of equation (\ref{Riccatti}) can be expressed in terms of $Y_\varepsilon$, the unique symmetric positive definite solution of the alternative
Riccati equation
\begin{equation}\label{AltRiccatti}
Y\Sigma_2 Y+\textstyle\frac \varepsilon 2 Y=\Sigma_1.
\end{equation}
In fact, if we write $Z_\varepsilon=\Sigma_2^{-1}X_\varepsilon \Sigma_1$ then
$$Z_\varepsilon=\Sigma_2^{-1}(\Sigma_2-\textstyle \frac \varepsilon 2 X_\varepsilon)X_\varepsilon^{-1}=(I_d-\textstyle \frac \varepsilon 2 \Sigma_2^{-1} X_\varepsilon)X_\varepsilon^{-1}=X_\varepsilon^{-1}-\frac \varepsilon 2 \Sigma_2^{-1}.$$
This shows that $Z_\varepsilon$ is symmetric. Also, since $\Sigma_2\geq \frac \varepsilon 2 X_\varepsilon$, we see that $X_\varepsilon^{-1}\geq\frac \varepsilon 2 \Sigma_2^{-1}$, that is, $Z_\varepsilon$ is positive definite. Since $Z_\varepsilon$ solves (\ref{AltRiccatti}) we conclude
$Z_\varepsilon=\Sigma_2^{-1}X_\varepsilon \Sigma_1=Y_\varepsilon$ or, equivalently, $X_\varepsilon \Sigma_1=\Sigma_2 Y_\varepsilon$.
From this we obtain $\Sigma_2^{-1}X_\varepsilon \Sigma_1X_\varepsilon=Y_\varepsilon X_\varepsilon$, which implies
\begin{eqnarray*}
I_d&=&\Sigma_2^{-1}(\Sigma_2-X_\varepsilon\Sigma_1 X_\varepsilon)+Y_\varepsilon X_\varepsilon=\textstyle\frac \varepsilon 2\Sigma_2^{-1}X_\varepsilon +Y_\varepsilon X_\varepsilon\\
&=&\big(\Sigma_2^{-1}+\textstyle\frac 2 \varepsilon Y_\varepsilon \big)\frac \varepsilon 2 X_\varepsilon.
\end{eqnarray*}
Thus, we conclude
\begin{equation}\label{AltFormEq}
\textstyle \frac 2 \varepsilon X_\varepsilon^{-1}=\Sigma_2^{-1}+\textstyle\frac 2 \varepsilon Y_\varepsilon.
\end{equation}

\end{Remark}

\bigskip
Before stating the announced result, we observe that in the analyisis of entropic regularization of transportation problems can
focus on the case of centered probabilities $P$ and $Q$. In fact, for $\pi\in\Pi(P,Q)$ and $(X,Y)\sim \pi$ we write $\tilde{\pi}=\mathcal{L}(X-\mu_P,Y-\mu_Q)$,
$\tilde{P}=\mathcal{L}(X-\mu_P)$ and $\tilde{Q}=\mathcal{L}(Y-\mu_Q)$. The map $\pi\to \tilde{\pi}$ is a bijection between $\Pi(P,Q)$ and $\Pi(\tilde{P},\tilde{Q})$ and
$\int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\pi(x,y)=\int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\tilde{\pi}(x,y)+\|\mu_P-\mu_Q\|^2$.
Similarly, we see that $H(\pi)=H(\tilde{\pi})$ and
$K(\pi|\mu\otimes \nu)=K(\tilde{\pi}|\tilde{\mu}\otimes \tilde{\nu})$, where $d\tilde{\mu}(x)=d\mu(x-\mu_P)$, $d\tilde{\nu}(y)=d\nu(y-\mu_Q)$. If $\mu$, $\nu$ and
$\tilde{\mu}$, $\tilde{\nu}$ are equivalent,  we see, using (\ref{red1}), that
$$I_{\varepsilon,\mu,\nu}[\pi]=I_{\varepsilon,\mu,\nu}[\tilde{\pi}]+\|\mu_P-\mu_Q\|^2-\varepsilon\Big(\textstyle
\int_{\mathbb{R}^d} \log\big(\textstyle \frac {d\tilde{\mu}}{d\mu}(x)\big)d\tilde{P}(x)+\int_{\mathbb{R}^d} \log\big(\textstyle \frac {d\tilde{\nu}}{d\nu}(y)\big)d\tilde{Q}(y)
\Big).$$
With the choice of reference measures $\mu=\nu=N(0,\lambda I_d)$ we have $\tilde{\mu}=N(\mu_P,\lambda I_d)$,
$\tilde{\nu}=N(\mu_Q,\lambda I_d)$. Hence, $\log\big(\textstyle \frac {d\tilde{\mu}}{d\mu}(x)\big)=\frac{1}{2\lambda}(\|x\|^2-\|x-\mu_P\|^2)
=\frac{1}{2\lambda}(2\mu_P\cdot x-\|\mu_P\|^2)$ and we conclude that
\begin{eqnarray}\label{W2ecent}
I_\varepsilon[\pi]&=&I_\varepsilon[\tilde{\pi}]+\|\mu_P-\mu_Q\|^2\\
\nonumber
I_{\varepsilon,\lambda}[\pi]&=&I_{\varepsilon,\lambda}[\tilde{\pi}]+\|\mu_P-\mu_Q\|^2+\textstyle \frac {\varepsilon}{2\lambda} \Big(\|\mu_P\|^2+\|\mu_Q\|^2\Big).
\end{eqnarray}

\bigskip
\begin{Theorem}\label{GaussianEntropicTC}
If $P$ and $Q$ are Gaussian probabilities on $\mathbb{R}^d$ with means $\mu_1$ and $\mu_2$ and positive definite covariance
matrices  $\Sigma_1$ and $\Sigma_2$, respectively, then, if $\pi_0$ denotes the  Gaussian probability on $\mathbb{R}^d\times \mathbb{R}^d$
with mean $\mu=\big[
\begin{smallmatrix}
\mu_1 \\ \mu_2
\end{smallmatrix}
\big]$ and covariance matrix $\Sigma_\varepsilon$ as in Proposition \ref{RiccattiSolutions}
\begin{eqnarray}
\nonumber
\mathcal{W}^2_{2,\varepsilon}(P,Q)&=& I_\varepsilon[\pi_0]=\|\mu_1-\mu_2\|^2\\
\label{entropiccost}
&&+\mbox{\em Tr}(\Sigma_1)+\mbox{\em Tr}(\Sigma_2)-2
\mbox{\em Tr}\big(\Sigma_1 X_\varepsilon \big){\textstyle  -\frac \varepsilon 2 \log\big((2\pi e)^{2d} (\frac{\varepsilon}2)^d|\Sigma_1 X_\varepsilon| \big) }.
\end{eqnarray}

\end{Theorem}

\noindent
\textbf{Proof.} {We write $r_P$ and $r_Q$ for the densities of $P$ and $Q$, respectively. From (\ref{W2ecent}) and the comments above we see that we only have to consider the case $\mu_1=\mu_2=0$.
Also, since $H(\pi)$ can only be finite if $\pi$ has a density, we can rewrite (\ref{W2e}) as
$$\mathcal{W}^2_{2,\varepsilon}(P,Q)=\inf_{r\in \mathcal{R}(P,Q)}\Big[\int_{\mathbb{R}^d\times \mathbb{R}^d} [\|x-y\|^2 +\varepsilon \log r(x,y)] r(x,y)dx dy \Big]
$$
with $\mathcal{R}(P,Q)$ denoting the set of densities on $\mathbb{R}^d\times \mathbb{R}^d$ satisfying the marginal conditions
$\int_{\mathbb{R}^d} r(x,y)dy=r_P(x)$ for almost every $x$ and $\int_{\mathbb{R}^d} r(x,y)dx$ $=r_Q(y)$ for almost every $y$. Consider now $f\in L_1(P)$,
$g\in L_1(Q)$. Then for any $r\in \mathcal{R}(P,Q)$,
\begin{eqnarray*}
\lefteqn{\int [\|x-y\|^2 +\varepsilon \log r(x,y)] r(x,y)dxdy-\int f(x) dP(x)-\int g(y)dQ(y)}\hspace*{5cm}\\
&=&\varepsilon \int  r(x,y) \log\Big(\textstyle \frac{r(x,y)}{e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon}} \Big) dxdy\\
&\geq &
\varepsilon \int  e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon} \Big(\textstyle \frac{r(x,y)}{e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon}} -1\Big) dxdy\\
&=& \varepsilon -\varepsilon  \int  e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon}  dxdy,
\end{eqnarray*}
with equality if and only if $r(x,y)=e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon}$ for almost every $(x,y)$ (observe that this follows from the elementary fact
that $s\log s\geq s-1$, $s>0$, with equality if and only if $s=1$). This shows that
$$\mathcal{W}^2_{2,\varepsilon}(P,Q)\geq \varepsilon +\sup_{f\in L_1(P),g\in L_1(Q)} \big[\textstyle \int f(x) dP(x)+\int g(y)dQ(y)-
\varepsilon  \int  e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon}  dxdy\big].$$
It shows also that if $r\in \mathcal{R}(P,Q)$ can be written as $r(x,y)=e^{\frac{f(x)+g(y)-\|x-y\|^2}\varepsilon}$ then $r$ is a minimizer for
the entropy-regularized transportation problem (indeed, by the strict convexity of $H$, the unique minimizer).

Now, if $\pi_0$ denotes the centered Gaussian distribution on $\mathbb{R}^d\times \mathbb{R}^d$ with
covariance matrix $\Sigma_\varepsilon$ as in Proposition \ref{RiccattiSolutions}, then, obviously, $\pi_0\in \Pi(P,Q)$. From the expression
for $\Sigma_\varepsilon^{-1}$ and denoting $A_\varepsilon=\Sigma_1^{-1}+\frac 2 \varepsilon X_\varepsilon$ and $B_\varepsilon=\frac 2 \varepsilon X_\varepsilon^{-1}$
we see that the density of $\pi_0$ equals
\begin{eqnarray*}
r_0(x,y)&=&\textstyle \frac{1}{(2\pi)^d|\Sigma_\varepsilon|^{\frac 1 2}}\exp\Big[
-\frac 1 2 \big(x^TA_\varepsilon x+ y^T B_\varepsilon y-\textstyle \frac 4 \varepsilon x^T y\big)
\Big]\\
&=&
\textstyle \frac{1}{(2\pi)^d|\Sigma_\varepsilon|^{\frac 1 2}}\exp\Big[
-\frac 1 \varepsilon  \big(\|x-y\|^2+  x^T\big(\frac \varepsilon 2 A_\varepsilon -I_d  \big)x+ y^T\big(\frac \varepsilon 2 B_\varepsilon-I_d\big) y\big)
\Big].
\end{eqnarray*}
Consequently, $r_0(x,y)=e^{\frac{f_0(x)+g_0(y)-\|x-y\|^2}\varepsilon}$ with
\begin{eqnarray}\nonumber
f_0(x)&=& x^T\big(\textstyle I_d-\frac \varepsilon 2(\Sigma_1^{-1}+\frac 2 \varepsilon X_\varepsilon)\big)x-\frac \varepsilon 2 \log\big( (2\pi)^{2d} |\Sigma_\varepsilon|\big),\\
\label{g0}
g_0(y)&=& y^T\big(\textstyle I_d-X^{-1}_\varepsilon\big )y.
\end{eqnarray}
This proves that $\pi_0$ minimizes the regularized transportation cost between $P$ and $Q$.

Finally, to prove (\ref{entropiccost}) we note first that
\begin{eqnarray}
\label{part1}
\int_{\mathbb{R}^d\times \mathbb{R}^d} \|x-y\|^2 d\pi_0(x,y)&=&
\mbox{Tr}(\Sigma_1)+\mbox{Tr}(\Sigma_2)-2
\mbox{Tr}(\Sigma_1 X_\varepsilon).
\end{eqnarray}
A simple computation shows that $H(\pi)=-\frac 1 2 \log\big((2\pi e)^{2d} |\Sigma_\varepsilon| \big)$. On the other hand
$$\det(\Sigma_\varepsilon)=\det(\Sigma_1) \det(\Sigma_2-X_\varepsilon \Sigma_1 \Sigma_1^{-1} \Sigma_1 X_\varepsilon)=
\textstyle\big(\frac{\varepsilon} 2\big)^d\det(\Sigma_1X_\varepsilon)$$
(here we have used that $\Sigma_2-X_\varepsilon \Sigma_1  X_\varepsilon=\frac \varepsilon 2 X_\varepsilon$).
Combining these last computations
with (\ref{part1}) we obtain (\ref{entropiccost}). \hfill $\Box$}

\bigskip
The proof of Theorem \ref{GaussianEntropicTC} can be easily adapted to other entropic regularizations. In particular, we can check that
$\pi_0$ is also the minimizer of $I_{\varepsilon,\lambda}[\pi]$ and also that
\begin{eqnarray}
\nonumber
\mathcal{W}^2_{2,\varepsilon,\lambda}(P,Q)&=& I_{\varepsilon,\lambda}[\pi_0]\\
\nonumber
&=&\|\mu_1-\mu_2\|^2+\textstyle \frac {\varepsilon}{2\lambda} \big(\|\mu_1\|^2+\|\mu_2\|^2\big)\\
&&\label{entropiccostlambda}
+\mbox{Tr}(\Sigma_1)+\mbox{Tr}(\Sigma_2)-2
\mbox{Tr}\big(\Sigma_1 X_\varepsilon \big)\\
&&\nonumber
{\textstyle -\frac \varepsilon 2} \big[\log \big( |\Sigma_1 X_\varepsilon |\big) -{\textstyle \frac 1 \lambda \big(\mbox{Tr}(\Sigma_1)+\mbox{Tr}(\Sigma_2) \big)-d \big(2\log \lambda -\log {\textstyle \frac \varepsilon 2} -1\big)} \big].
\end{eqnarray}

\bigskip
Theorem \ref{GaussianEntropicTC} shows that the entropic transportation cost between normal laws is, as in the case of classical transportation cost,
a sum of two contributions. One accounts for the deviation in mean between the two laws. This part remains unchanged by the regularization with negative
differential entropy (but not with relative entropies). The other contribution,
which accounts for deviations between the covariance matrices, behaves differently, but this behavior is also easier to understand in the case
of $\mathcal{W}_{2,\varepsilon}$.
In the one-dimensional case we see that
$$\mathcal{W}^2_{2,\varepsilon}(N(0,\sigma_1^2),N(0,\sigma_2^2))=\sigma_1^2+\sigma_2^2-2\sqrt{\sigma_1^2\sigma_2^2+(\textstyle\frac{\varepsilon}4)^2}-\textstyle \frac \varepsilon 2 \log
\big( \sqrt{\sigma_1^2\sigma_2^2+(\frac{\varepsilon}4)^2}-\frac \varepsilon 4\big)-\frac \varepsilon 2 \log ( 2 \pi^2 e \varepsilon ).$$
In particular, $\mathcal{W}^2_{2,\varepsilon}(N(0,1),N(0,1))=h(\frac \varepsilon 4)$ with
$$h(x)=2(1-\sqrt{1+x^2})-2x \log\big(\sqrt{1+x^2}-x\big)-2x\log \big((2\pi)^2 e x\big).$$
It is easy to see that $h(0)=0$, $h$ is decreasing in $\mathbb{R}_+$ and $\lim_{x\to\infty}h(x)=-\infty$.

\bigskip
While Theorem \ref{GaussianEntropicTC} is limited to Gaussian probabilities, its scope goes beyond that case. In classical optimal transportation
the Gaussian case provides a lower bound for the quadratic transportation cost through Gelbrich's bound (see in \cite{cuesta1996lower} which improves the bound in~\cite{gelbrich1990formula} ). We show next that this carries
over to entropic regularizations of transportation cost.

\begin{Theorem}\label{EntropicGelbrich}
If $P$ and $Q$ are probabilites on $\mathbb{R}^d$ with means $\mu_1,\mu_2$ and positive definite covariance matrices $\Sigma_1,\Sigma_2$, respectively,
then
\begin{eqnarray}
\nonumber
\mathcal{W}^2_{2,\varepsilon}(P,Q)&\geq& \|\mu_1-\mu_2\|^2\\
\label{gelbound}
&&+\mbox{\em Tr}(\Sigma_1)+\mbox{\em Tr}(\Sigma_2)-2
\mbox{\em Tr}\big(\Sigma_1 X_\varepsilon \big){\textstyle  -\frac \varepsilon 2 \log\big((2\pi e)^{2d} (\frac{\varepsilon}2)^d|\Sigma_1 X_\varepsilon| \big) },
\end{eqnarray}
where $X_\varepsilon$ is as in (\ref{RiccattiSol}). Equality in (\ref{gelbound}) holds if and only if $P$ and $Q$ are Gaussian.
\end{Theorem}

\noindent
\textbf{Proof.} As in the proof of Theorem \ref{GaussianEntropicTC}, it suffices to consider the case of centered $P$ and $Q$. If $P$ (or $Q$)
does not have a density then $\Pi(P,Q)$ does not contain any probability with a density and, consequently, $I_\varepsilon[\pi]=+\infty$
for every $\pi\in \Pi(P,Q)$ and the result is trivial. We assume, therefore, that $P$ and $Q$ are absolutely continuous w.r.t. Lebesgue measure.
We consider $\pi\in \Pi(P,Q)$ with density $r$ and denote by $r_0$ the density of $\pi_0$, as defined in Theorem \ref{GaussianEntropicTC}. Then (recall (\ref{g0}))
\begin{eqnarray*}
I_\varepsilon[\pi]&=&\varepsilon \int_{\mathbb{R}^d\times\mathbb{R}^d} \log\Big({\textstyle \frac{r(x,y)}{e^{-\frac{\|x-y\|^2}{\varepsilon}}}}\Big) r(x,y) dx dy\\
&=&\varepsilon \int_{\mathbb{R}^d\times\mathbb{R}^d} \log\Big({\textstyle \frac{r(x,y)}{r_0(x,y)}}\Big) r(x,y) dx dy
+ \int_{\mathbb{R}^d\times\mathbb{R}^d} x^T (I_d-X_\varepsilon-{\textstyle\frac \varepsilon 2 \Sigma_1^{-1}})x r(x,y)dxdy\\
&&+ \int_{\mathbb{R}^d\times\mathbb{R}^d} y^T (I_d-X_\varepsilon^{-1})y r(x,y)dxdy-{\textstyle \frac \varepsilon 2 }\log \Big((2\pi)^{2d} ({\textstyle \frac \varepsilon 2})^d  |\Sigma_1 X_\varepsilon|\Big)\\
&=&\mbox{Tr}((I_d-X_\varepsilon-{\textstyle\frac \varepsilon 2 \Sigma_1^{-1}})\Sigma_1)+\mbox{Tr}((I_d-X_\varepsilon^{-1})\Sigma_2)-{\textstyle \frac \varepsilon 2 }\log \Big((2\pi)^{2d}({\textstyle \frac \varepsilon 2})^d|\Sigma_1 X_\varepsilon|\Big) +\varepsilon K(\pi|\pi_0),\\
&=&\mbox{Tr}(\Sigma_1)+\mbox{Tr}(\Sigma_2)-2\mbox{Tr}(\Sigma_1X_\varepsilon)-{\textstyle \frac \varepsilon 2 }\log \Big((2\pi e)^{2d}({\textstyle \frac \varepsilon 2})^d|\Sigma_1 X_\varepsilon|\Big) +\varepsilon K(\pi|\pi_0).
\end{eqnarray*}
Now (\ref{gelbound}) follows from the fact that $K(\pi|\pi_0)\geq 0$. If $P$ and $Q$ are Gaussian (and only in that case) then $\pi_0\in \Pi(P,Q)$. This completes the proof. \hfill $\Box$

\bigskip
To conclude this section we present a simple result on best approximation with respect to entropic transportation cost. In the case $\varepsilon=0$
(classical optimal transportation) $\mathcal{W}_2$ is a metric and for any $P$ with finite second moment we have
$$\mathcal{W}_2^2(P,Q)\geq  \mathcal{W}_2^2(P,P)=0, \quad Q\in \mathcal{F}_2(\mathbb{R}^d).$$
The fact that $\mathcal{W}_{2,\varepsilon}$ is no longer a metric for $\varepsilon>0$ changes the nature of the problem and we may wonder
which $Q\in \mathcal{F}_2(\mathbb{R}^d)$ is closest to $P$ in the sense of minimizing $\mathcal{W}_2^2(P,Q)$.
We show next that in the case of Gaussian $P$ the problem admits a simple solution.

\medskip
\begin{Theorem}\label{best_entropic_approximation}
Assume that $P$ is a probability on $\mathbb{R}^d$ with a density $r_P$ such that $\log r_P(x)\in L_1(P)$. Then
$$P*N_d(0,{\textstyle \frac{\varepsilon} 2} I_d)=\mbox{\em argmin}_Q W_{2,\varepsilon}^2(P,Q),$$
with the minimization extended to the set of all probabilities on $\mathbb{R}^d$. Furthermore, $P*N_d(0,{\textstyle \frac{\varepsilon} 2} I_d)$
is the unique minimizer.
\end{Theorem}

\medskip
\noindent
\textbf{Proof.} We consider a probability on $\mathbb{R}^d\times \mathbb{R}^d$ with first marginal $P$ and
$f\in L_1(P)$. Arguing as in the proof of Theorem \ref{GaussianEntropicTC} (take $g=0$) we see that
$$I_\varepsilon[\pi]\geq  \varepsilon + \int f(x) dP(x) - \varepsilon \int  e^{\frac{f(x)-\|x-y\|^2}\varepsilon}  dxdy,$$
with equality if and only if $\pi$ has a density, $r$, that can be written as $r(x,y)=e^{\frac{f(x)-\|x-y\|^2}\varepsilon}$.
Now, if $r_0(x,y)=r_P(x) (\pi\varepsilon)^{-d/2} \exp(-\frac{\|y-x\|^2}{\varepsilon})$, then $r_0$ is a density on
$\mathbb{R}^d\times\mathbb{R}^d$ with first marginal $P$, second marginal $P*N_d(0,\frac{\varepsilon} 2 I_d)$, and we can write
$r_0(x,y)=e^{\frac{f_0(x)-\|x-y\|^2}\varepsilon}$ with $f_0(x)=\varepsilon \log r_P(x)-\frac {d\varepsilon} 2 \log \pi\varepsilon$.
The assumption on $r_P$ ensures that $f_0\in L_1(P)$. We conclude that
$$\min_Q W_{2,\varepsilon}^2(P,Q)= W_{2,\varepsilon}^2(P,P*N_d(0,{\textstyle \frac{\varepsilon} 2} I_d)).$$
Uniqueness follows by strict convexity of the entropic transportation cost.
\hfill $\Box$

\bigskip
We end this section with a simple observation that will be useful in our analysis of reguarized barycenters.
While $\mathcal{W}_2^2(P,Q)$ can take negative values, Theorem \ref{best_entropic_approximation} shows that the map $Q\mapsto \mathcal{W}_2^2(P,Q)$
is lower bounded by
$$ W_{2,\varepsilon}^2(P,P*N_d(0,{\textstyle \frac{\varepsilon} 2} I_d))=\varepsilon \int_{\mathbb{R}^d}r_P(x) \log r_P(x)dx-{\textstyle \frac{d\varepsilon}{2}\log \pi\varepsilon}.$$

In the Gaussian case $P=N_d(\mu,\Sigma)$ we see that
$$ W_{2,\varepsilon}^2(N_d(\mu,\Sigma),Q)\geq W_{2,\varepsilon}^2(N_d(\mu,\Sigma),N_d(\mu,\Sigma+{\textstyle \frac \varepsilon 2} I_d))=
{\textstyle-\frac \varepsilon 2 \log |\Sigma| -\frac{d\varepsilon}2 \log (2\pi^2e\varepsilon)}.$$
This shows (recall Theorem \ref{GaussianEntropicTC}) that, in particular, if we fix a positive definite $\Sigma_1$ then the map
$$\Sigma_2\mapsto  \mbox{Tr}(\Sigma_2)-2\mbox{Tr}(\Sigma_1X_\varepsilon) -\textstyle \frac{\varepsilon}{2}\log|\Sigma_1X_\varepsilon|,$$
with $X_\varepsilon$ as in (\ref{RiccattiSol}),
attains its minimal value within the set of positive definite matrices at $\Sigma_2=\Sigma_1+\frac \varepsilon 2 I_d$.
Setting $A=\Sigma_1^{1/2}X_\varepsilon \Sigma_1^{1/2}$ is equivalent to setting $\Sigma_2=\Sigma_1^{-1/2}(A^2+\frac \varepsilon 2 A)\Sigma_1^{-1/2}$.
This allows to conclude that the strictly convex map (strict convexity follows easily from concavity of the log determinant)
$$A \mapsto  \mbox{Tr}(\Sigma_1^{-1}A^2)+ {\textstyle \frac \varepsilon 2}\mbox{Tr}(\Sigma_1^{-1}A)-2\mbox{Tr}(A) -\textstyle \frac{\varepsilon}{2}\log|A|$$
attains its minimal value within the set of positive definite matrices at $A=\Sigma_1$.

\section{Regularized barycenters.}

In this section we consider the entropic regularization of barycenters with respect to transportation cost metrics. To be precise, we will assume
that $P_1,\ldots,P_k$ are probabilities on $\mathbb{R}^d$ and $\lambda_1,\ldots,\lambda_k$ a collection of weights satysfying
$\lambda_i>0$, $\sum_{i=1}^k \lambda_i=1$ and consider the functional
$$V_\varepsilon(Q)=\sum_{i=1}^k\lambda_i \mathcal{W}_{2,\varepsilon}^2(P_i,Q).$$
A minimizer of $V_\epsilon$ will be called an $\varepsilon$-regularized barycenter of $P_1,\ldots,P_k$ (with weights $\lambda_1,\ldots,\lambda_k$).

The $L_2$ transportation cost metric, $\mathcal{W}_2$, satisfies the remarkable stability property that barycenters of Gaussian probabilities with
respect to $\mathcal{W}_2$ are Gaussian (this holds in fact for general location-scatter families, see  \cite{alvarez2016fixed}). We show in Theorem
\ref{entropic_Gaussian_barycenter} that this
carries over to entropic regularized barycenters, although in this case the stability fails beyond the Gaussian case.
Our result characterizes the barycenter in terms of the solution of a particular matrix equation, extending the result for the classical (unregularized) case. Existence and uniqueness of a solution for that matrix equation is guaranteed by our next result.

\medskip
\begin{Proposition}
If $\Sigma_i\in\mathcal{M}_{d\times d}(\mathbb{R})$ are symmetric and positive definite then there exists a unique positive definite $\Sigma
\in\mathcal{M}_{d\times d}(\mathbb{R})$ such that
\begin{equation}\label{matrix_eq}
\sum_{i=1}^k \lambda_i \Big(\Sigma^{-1/2}\big( \Sigma^{1/2}\Sigma_i \Sigma^{1/2}+\textstyle (\frac{\varepsilon}{4})^2 I_d \big)^{1/2}\Sigma^{-1/2}+\textstyle \frac{\varepsilon}{4} \Sigma^{-1}\Big)=I_d.
\end{equation}
\end{Proposition}

\medskip
\noindent \textbf{Proof.}
The existence of a solution is equivalent to the existence of a fixed point for the map $G(\Sigma)=\sum_{i=1}^k\lambda_i G_i(\Sigma)$ with
$G_i(\Sigma)=\big( \Sigma^{1/2}\Sigma_i \Sigma^{1/2}+\textstyle (\frac{\varepsilon}{4})^2 I_d \big)^{1/2}+\textstyle \frac{\varepsilon}{4} I_d$.
$G$ is a continuous map on the set of positive semidefinite matrices and existence of a fixed point can be proved
using Brower's fixed point theorem, as follows. We write $A \preceq B$ to denote that $B-A$ is positive definite. Assume then that
$\alpha I_d\preceq \Sigma_i\preceq \beta I_d$, $i=1,\ldots,k$ and set $K=\{\Sigma :\, \alpha I_d\preceq \Sigma \preceq \beta+\frac \varepsilon 2 I_d\}$.
The set $K$ is compact and convex. Now, for every $\Sigma\in K$ we have $\Sigma^{1/2}\Sigma_i \Sigma^{1/2}+\textstyle (\frac{\varepsilon}{4})^2 I_d \preceq
\beta \Sigma + (\frac{\varepsilon}{4})^2 I_d\leq \big(\beta (\beta+\frac{\varepsilon} 2)+ (\frac{\varepsilon}{4})^2\big) I_d=
\big(\beta+\frac{\varepsilon}{4}\big)^2 I_d$. Using that $A\preceq B$ implies $A^{1/2}\preceq B^{1/2}$ (see, e.g., Theorem V.2.10 in \cite{Bhatia}) we conclude
that
$$G_i(\Sigma)\preceq \textstyle{\big(\beta+\frac{\varepsilon}{2}\big)}I_d.$$
Similarly, we see that $\alpha I_d \preceq G_i(\Sigma)$ for $\Sigma\in K$. We conclude that $G$ maps $K$ into $K$ and from Brower's theorem we conclude
the existence of a fixed point. Uniqueness follows from Theorem \ref{entropic_Gaussian_barycenter} below \hfill $\Box$

\medskip
\begin{Theorem}\label{entropic_Gaussian_barycenter}
If $P_i=N(\mu_i,\Sigma_i)$ with $\mu_i\in \mathbb{R}^d$ and $\Sigma_i\in\mathcal{M}_{d\times d}(\mathbb{R})$ symmetric and positive definite then
the $\varepsilon$-regularized barycenter of $P_1,\ldots,P_k$ with weights $\lambda_1,\ldots,\lambda_k$ is $\bar{P}=N(\mu_0,\Sigma_0)$,
where $\mu_0=\sum_{i=1}^k \lambda_i \mu_i$ and $\Sigma_0$ is the unique positive definite solution of the matrix equation (\ref{matrix_eq}).
\end{Theorem}

config: arxiv


TITLE: Integral with analytical solution with normal distribution
QUESTION [2 upvotes]: I received very good answers a couple of days ago in a simpler related problem, see Integral with Normal Distributions, but I am struggling with this new question:
Let's define a function $F(\theta)=\int\limits_{-\infty}^{+\infty} \Phi  \left(\theta -a- b x\right) \phi\left(cx- \theta \right) \mathrm d x$
$\theta$ is a relevant parameter and $a$, $b$ and $c$ are all given scalars. $\Phi$ and $\phi$ respectively denote the CDF and PDF of the standard normal distribution
I have two questions:

Is there a way to express analytically this integral as a function of $\theta$, $a$, $b$ and $c$? (The case with $a=0$, $b=c=1$ is the one solved in the previous question)
I want to find conditions on $a$, $b$ and $c$ that make $F'(\theta)<1$.

REPLY [5 votes]: For any $a,b,\theta \in \mathbb{R}$ and $c > 0$, it holds
$$
F(\theta ) := \int_{ - \infty }^\infty  {\Phi (\theta  - a - bx)\phi (cx - \theta )\,{\rm d}x} = \frac{1}{c}\Phi \bigg(\frac{{(c - b)\theta  - ac}}{{\sqrt {c^2  + b^2 } }}\bigg).
$$
(I confirmed the result numerically.)
Proof. First note that
$$
\frac{1}{c}\Phi \bigg(\frac{{(c - b)\theta  - ac}}{{\sqrt {c^2  + b^2 } }}\bigg) = \frac{1}{c}{\rm P}\bigg[Z \le \frac{{(c - b)\theta  - ac}}{{\sqrt {c^2  + b^2 } }}\bigg] = \frac{1}{c}{\rm P}\big[cX + bY \le (c - b)\theta  - ac\big],
$$
where $X$, $Y$, and $Z$ are independent ${\rm N}(0,1)$ random variables (note that $\sqrt {c^2  + b^2 } Z$ and $cX+bY$ are identically distributed). By the law of total probability, conditioning on $Y$, we thus get
$$
\frac{1}{c}\Phi \bigg(\frac{{(c - b)\theta  - ac}}{{\sqrt {c^2  + b^2 } }}\bigg) = \frac{1}{c}\int_{ - \infty }^\infty  {{\rm P}\big[cX + by \le (c - b)\theta  - ac\big]\phi (y)\,{\rm d}y}.
$$
A change of variable $y=cx-\theta$ then gives
$$
\frac{1}{c}\Phi \bigg(\frac{{(c - b)\theta  - ac}}{{\sqrt {c^2  + b^2 } }}\bigg) = \frac{1}{c}\int_{ - \infty }^\infty  {{\rm P}\big[cX + b(cx - \theta ) \le (c - b)\theta  - ac\big]\phi (cx - \theta )c\,{\rm d}x} .
$$
A little algebra shows that the expression on the right is equal to
$$
\int_{ - \infty }^\infty  {{\rm P}\big[X \le  \theta  - a -bx \big]\phi (cx - \theta )\,{\rm d}x},
$$
and hence
$$
\frac{1}{c}\Phi \bigg(\frac{{(c - b)\theta  - ac}}{{\sqrt {c^2  + b^2 } }}\bigg) = \int_{ - \infty }^\infty  {\Phi (\theta  - a - bx)\phi (cx - \theta )\,{\rm d}x}.
$$


text:
\newcommand{\appendixTitle}{
\vbox{
    \centering

    \vskip 0.05in
	{\LARGE \bf Supplementary material}
	\vskip 0.2in
	\hrule height 1pt
}}

\newcommand{\makeappendixtable}[1]{
~\\[.75em]\hskip 2em \begin{tabular}{@{}p{0.44\textwidth}p{0.2\textwidth}p{0.14\textwidth}@{}}
\toprule
#1\\
\bottomrule
\end{tabular}\\[.0em]
}
\newcommand{\makeappendixheader}{
\textbf{Step-size} & \textbf{Rate} & \textbf{Reference} \\
\midrule
}
\appendixTitle

\section*{Organization of the Appendix}
\begin{itemize}
    \item[\ref{sec:setup}] \nameref{sec:setup}

    \item[\ref{app:line-search}] \nameref{app:line-search}

    \item[\ref{app:adagrad-proofs}] \nameref{app:adagrad-proofs}
    \makeappendixtable{
        \makeappendixheader
        Constant
        & $\bigO(\nicefrac{1}{T} + \nicefrac{\sigma}{\m!\sqrt{T}})$
        & \cref{thm:adagrad-constant}
        \\
        Conservative Lipschitz LS
        & $\bigO(\nicefrac{1}{T} + \nicefrac{\sigma}{\m!\sqrt{T}})$
        & \cref{thm:adagrad-linesearch-conservative}
        \\
        Non-conservative LS (with interpolation)
        &$\bigO(\nicefrac{1}{T})$
        & \cref{cor:adagrad-armijo-interpolation}
    }
    \item[\ref{app:amsgrad-proofs}] \nameref{app:amsgrad-proofs}
    \makeappendixtable{
        Constant
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-constant}
        \\
        Armijo LS
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-linesearch}
    }
    \item[\ref{app:amsgrad-momentum-proofs}] \nameref{app:amsgrad-momentum-proofs}
    \makeappendixtable{
        Constant
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-constant-mom}
        \\
        Conservative Armijo LS
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-sls-mom}
        \\
        Conservative Armijo SPS
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-sps-mom}
    }
    ~\\[.5em]
    \nameref{app:amsgrad-hb-proofs}
        \makeappendixtable{
        Constant
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-constant-HB}
        \\
        Conservative Armijo LS
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-sls-HB}
        \\
        Conservative Armijo SPS
        & $\bigO(\nicefrac{1}{T} + \sigma^2)$
        & \cref{thm:amsgrad-sps-HB}
    }

    \item[\ref{app:exp-details}] \nameref{app:exp-details}

    \item[\ref{app:additional-exps}] \nameref{app:additional-exps}

\end{itemize}


TITLE: Write number of elements in P(X) for which gof(A) =1
QUESTION [0 upvotes]: Let $X=\{a, b, c, d, e\}$ and $P(X)$ be the power set of $X$.
Define the functions $f:P(X) \to \mathbb{N}$ by $f(A)= 1 + |A|$, where $|A|$ is the number of elements in set $A$, and $g:\mathbb{N} \to \{0,1\}$ by $g(n)= 1$ if $n$ is prime, $g(n) = 0$ otherwise.
Write the number of elements in $P(X)$ for which $(g \circ f)(A) =1$.
Number of elements in power set gonna remain same whatsoever, ie $2^5$ but that doesn't seem correct. In relevance to the question, I figured out we need to find number of elements in $P(X)$ for which $1 + |A|$ is a prime number. A hint will be appreciated.

REPLY [0 votes]: For $A \subseteq X$, you have that $|A| \in \{ 0, 1, 2, 3, 4, 5 \}$, whence $f(A) \in \{ 1, 2, 3, 4, 5, 6\}$.
Now find the prime numbers among these, subtract $1$, and what are the subsets of $X$ having the resulting cardinalities?
The resulting cardinalities are, of course, $1$, $2$ and $4$.


TITLE: Finding $\Theta$ of Recurrence $ T(n) = 2T(\frac{n}{3})+2T(\frac{2n}{3})+n$ or finding Closed Form for $2^{p+1}+2=3^p$
QUESTION [8 upvotes]: The goal is to get an exact asymptotic for $T(n).$  I tried two approaches, but both failed:
1). Recursion tree. We see that $$\sum_{i = 0}^{\log_{3}(n)}n2^i=\Theta(n^{1+\log_3(2)})<<T(n) << \sum_{i = 0}^{\log_{3/2}(n)} n2^i = \Theta(n^{1+\log_{3/2}(2)})$$ but cannot, as I can see, get $\Theta(T(n))$ exactly.
2). Akra-Bazzi Theorem. We get through straightforward calculus that $T(n) = \Theta(n^p)$ where $2+2^{p+1} = 3^p$. As far as I can see this equation yields no closed form for $p\,$ (But it gives a numerical approximation consistent with 1, so that is good).
The goal is to get a closed form better than $2^{p+1}+2 = 3^p.$ I believe such a closed form does exist, for reasons associated with the expected difficulty of the problem, and that it can be found through an alternate derivation, transformations or some other trick.
Summary:
Twin goals of the question, any answer resolving either will be accepted:
(1). Can this problem be solved without the use of the Akra-Bazzi Theorem?
(2). Find a better closed form for $p$.
Essentially, I have a hunch that getting (1) leads right to (2).
Any help is appreciated.
This is  problem 2(m) from Jeffrey Erickson's notes.

REPLY [0 votes]: The goal to get a closed form better than $\,2+2^{p+1}=3^p\,$ is impossible  because $\,T(n)=An^p-n\,$ is the general solution (and the Akra-Bazzi Theorem is not necessary to get this).
E.g. the recursion of the Fibonacci numbers is a good example how to get such formulas. The given link above (Jeffrey Erickson's notes) is good too to understand how to solve such recursions.
For a closed form for $\,p\,$ define a function $\,f(x):=\sqrt[x]{4\cosh x}\,$ for $\,x>0\,$ and $\,f^{-1}(x)\,$ it's inverse function so that one gets:  $$p=\frac{2}{\ln 2}f^{-1}(\sqrt[\ln2]{4.5})$$

Did $\,$gave me the good advice to add a proof for the (descending) monotony of $\,f(x)\,$ .
It's enough to proof this for $\,\ln f(x)\,$ because of $\displaystyle \frac{d}{dx}f(x)=f(x)\frac{d}{dx}\ln f(x)\,$ and $\,f(x)>0\,$ .
We have to proof $\,\displaystyle\frac{d}{dx}\ln f(x)<0\,$ for all $\,x>0\,$ .
$\displaystyle\frac{d}{dx}\ln f(x)=-\frac{\ln (4\cosh x)}{x^2}+\frac{\tanh x}{x}<0\enspace$ is true because of
$x\tanh x<x<\ln(2 e^x)<\ln(4\cosh x)\enspace$ or in details
$e^x-e^{-x}<e^x+e^{-x}\,$ , $\enspace x<x+\ln 2\,$ , $\enspace e^x<2\cosh x\,$ .


TITLE: Find all natural numbers $n$ such that $n^{17}-n$ is divisible by 10
QUESTION [2 upvotes]: I've encountered this math problem and I don't know how to solve it. What math region,field(however you call it. English is not my first language) is used here ?

Find all natural numbers for which ($n^{17} - n $  ) is divisible by
  10.

Any tips or advice you can give me and if you could share some websites where I can learn more about this.

REPLY [2 votes]: A systematic approach: just check the cases of $2$ and of $5$ respectively.
It is clear that $n^{17}-n$ is even. Also we see
$$n^{17}-n=(n^4)^{4}\times n-n\equiv 0\pmod5$$
since if $n$ is not divisible by $5,$ then $n^4-1$ is divisible by $5.$
Hope this helps.

REPLY [2 votes]: You can check all the remnants by $mod \ 10$ simply taking 17th power (there are 10 of them - $1,2, \ldots , 9$) or you can check whether the polynomial mentioned above takes its value divided by 10.

REPLY [0 votes]: I don't have time to develop this, but it seems that all positive numbers satisfy your problem.
In Mathematica:
Reduce[Mod[n^17 - n, 10] == 0, n, Integers]

We have output:
C[1] \[Element] Integers &&
(n == 10 C[1] || n == 1 + 10 C[1] || n == 2 + 10 C[1] ||
n == 3 + 10 C[1] || n == 4 + 10 C[1] || n == 5 + 10 C[1] ||
n == 6 + 10 C[1] || n == 7 + 10 C[1] || n == 8 + 10 C[1] ||
n == 9 + 10 C[1])


TITLE: Problem on limit superior of a function
QUESTION [2 upvotes]: If $\overline\lim_{x\to y} f(x)=A$ and $\langle x_n\rangle$ is a
  sequence with $x_n \neq y$ such that $y=\lim x_n$, then
  $\overline\lim_{n\to  \infty} f(x_n)\le A$.

Now, I am able to visualize this problem graphically. One instance where
$\overline\lim_{n\to  \infty} f(x_n)= A$ is when $f$ is continuous over a certain neighborhood of $y$, since the graph is "smooth" around that point, all $f(x)$'s of different sequences converge to the same $f(y)$. But if $f$ is not continuous, the limit may reach different values depending on the "direction" $x$ converges to $y$. (Hopefully this made sense.)
What I don't know how to do is write out the proof mathematically and simply. Now, my textbook defined the limit superior as follows:

$$\overline\lim_{x\to y}f(x)=\inf_{\delta>0}\sup_{0<|x-y|<\delta} f(x)$$
  $$\overline\lim_{n\to \infty}x_n= \inf_{n}\sup_{k \ge n} x_k$$

While I understand what these mean, I'm having trouble to express them in mathematical terms, and even if I can, I'm not sure how to proceed. Can someone explain to me how to express these things correctly and solve the problem in a good way? Thanks.

REPLY [1 votes]: If $B>A$ then for $\delta>0$ small enough we have: $$\sup_{0<|x-y|<\delta} f(x)<B$$
Some $n_0$ will exist with: $$k\geq n_0\implies|x_k-y|<\delta\implies f(x_k)<B$$
That results in: $$\overline\lim_{n\to \infty}f(x_n)\leq\sup_{k\geq n_0}f(x_k)\leq B$$
This is true for every $B>A$ hence we also have:$$\overline\lim_{n\to \infty}f(x_n)\leq A$$


TITLE: Center of $SU(N)$ group in general Young-tableaux representation
QUESTION [2 upvotes]: Let us consider $ SU(2)$ irrep. with a $1\times k$ Young tableaux. Then the center group of such linear representation depends on the value of $k$ in the following sense. If $k\in$odd, then the center is nontrivial, namely $Z_2$, while the center is trivial when $k\in$even.
I wonder whether it can be generalized to $SU(N)$ irrep. with a general Young tableaux consisting of $b$ blocks. What I can guess or expect is the result should be that the center is $Z_{N/(b,N)}$ where $(b,N)$ is the greatest common divsor of $b$ and $N$. Is this statement correct? If so, how to prove it?

REPLY [0 votes]: The matrix representing the center generator of $SU(N)$ can be calculated within some (larger) irreducible representation since the matrix is proportional to the identity matrix. More specifically, any Young-tableaux representation with $b$ blocks is contained in the $b$-fold tensor product of fundamental representations, namely
\begin{eqnarray}
\text{irrep}(b)\in\otimes_1^bN.
\end{eqnarray}
Thus we can calculated the prefactor by the right-hand side:
\begin{eqnarray}
Z(b)&=&\left[\exp(i2\pi/N)\right]^b\nonumber\\
&=&\exp(i2\pi b/N),
\end{eqnarray}
which generates $Z_{N/(b,N)}$.


TITLE: Example of composition of continuous function with sequence of functions which converges in measure need not converge in measure
QUESTION [2 upvotes]: Example $\phi $ is continuous function $f_n \to f$ in measure. with $\phi \circ f_n\not\to  \phi \circ  f$ in measure

I am trying to find above example but unable to construct.
Also I tried following theorem
$\phi $ is uniformly continuous function $f_n \to f$ in measure. with $\phi \circ f_n\to  \phi \circ  f$ in measure
My attempt:
Let $\phi $ is uniformly continuous
$\forall \epsilon >0$ $\exists \delta >0$ such that $|x-y|<\delta\implies |\phi (x)-\phi (y)|<\epsilon $
$E=\{x||f_n(x)-f(x)|>\delta \}$
$\mu(E)\to 0$
On $E^c$ $|f_n(x)-f(x)|\leq \delta $$\implies |\phi \circ f_n(x)-\phi \circ f(x)||<\epsilon $
SO it is converges in measure .
Is there is any mistake ?
Please Help me to construct example

REPLY [1 votes]: The answer by @Kavi Rama Murthy is valid on finite measure spaces.
On a general measure space, you can find a counterexample. Take for example the real line with the Lebesgue measure, and $f_n (x) = x + 1/n$, $f(x) = x$, and $\phi (x) = x^2$.
Then $\phi(f_n(x))-\phi(f(x)) = 2x/n +n^{-2}$, which has absolute value at least one on the set $[n,\infty)$. Directly from the definition, this shows that you don't have $\phi \circ f_n \to \phi \circ f$ in measure.


TITLE: Can a number have infinitely many digits before the decimal point?
QUESTION [60 upvotes]: I asked my teacher if a number can have infinitely many digits before the decimal point. He said that this isn't possible, even though there are numbers with infinitely many digits after the decimal point. I asked why and he said that if you keep adding digits to the left of a number it will eventually approach infinity which is not a number and you could no longer distinguish two numbers from one another.
Now this is the part of his reasoning I don't understand: why can we distinguish two numbers with infinitely many digits after the point but not before it? Or is there a simpler explanation for this?

REPLY [0 votes]: Just because a number has an infinite number of digits doesn't mean it isn't well defined...
With a great deal of effort you may even be able to redefine a number with an infinite number of digits into being a finite number...
consider 1+2+3+4+5+6+...=-1/12 which is the solution to riemannZeta(-1)
proof
1-1+1-1+1-......=A
1-A=1-(1-1+1-1+1-1+1-....)=1-1+1-1+1-1+1-....=A
1-A=A
A=1/2

1-2+3-4+5-6+7-....=B
B+B= 1-2+3-4+5-6+7-....
      +1-2+3-4+5-6+7-....
   = 1-1+1-1+1-1+1-......
B+B=A
B=1/4

1+2+3+4+5+6+7+8=C
C-B=1+2+3+4+5+6+7+8
   -1+2-3+4-5+6-7+8-...
   =  4  +8 +12 +16 +...
   =4*(1 +2 +3  +4  +...)
   =4*C
C-B=4*C
C=-B/3
 =-1/4/3
 =-1/12

boya
and as Mathmo123 pointed out numbers with repeating digits may all be considered equal to zero.
since ...111111.11111.... *10 = ...11111111.11111....
and since the only solution to x*10=x is zero then all numbers with repeating digits left and right of the decimal place can be considered equal to zero.
there is precedent for this as the riemannZeta function is zero for all negative even integers... i.e. 0=1^2+2^2+3^2+...=1^4+2^4+3^4+...=1^6+2^6+3^6+...
and as  supercat has mentioned in several comments, the power-series formula yields -1 for the geometric series 1+2^2+2^3+2^4+2^5+2^6+2^7+... even though it is out side the traditionally defined domain of that formula.
consider what 1+2^1+2^2+2^3+2^4+... is in binary... it happens to be equal to ...11111111111.0 in binary and if ...1111111.1111111.... (all repeating digits) is equal to zero and 0.11111111111 which is equal to one... then
 ...1111111111.111111111...(binary)  0
-...0000000000.111111111...(binary) -1
=...1111111111.000000000...(binary)=-1

which satisfies the power series formula!
Everything works out perfectly!
So in summary: a number with an infinite number of digits to the left of the decimal place can be well defined.
However this does not mean that ALL such numbers are well defined... (although they may all be well defined, I can't prove that all infinite numbers are well defined... it's beyond my current level of skill and time available to prove)


TITLE: Images of linearly equivalent divisors are linear equivalent?
QUESTION [4 upvotes]: Let $f:X\longrightarrow Y$ be a finite morphism of degree $d$ projective surfaces over $\mathbb{C}$. Suppose that $X$ is smooth. Let $L'$ be a line bundle on $Y$, and let $L=f^*L'$.
1)  Consider a smooth curve $C\in |L|$. If the image $f(C)$ is a smooth curve on $Y$ which is a Cartier divisor, then does $f(C)\in |L'|$.
2) More generally if two curves $C_1$ and $C_2$ are linearly equivalent in $X$. Consider their images $C_1'$ and $C_2'$, and suppose that they Cartier divisors in $Y$. If $f|_{C}:C_i\longrightarrow C_i'$ are finite morphisms of degree $d$. Then are the images linearly equivalent too? I suppose that they are, because that linear equivalence is preserved by direct images.
So if $C_1 \sim C_2$, then $f_*(C_1)\sim f_*(C_2)$. That is $d.C_1'\sim d.C_2'$. Hence $C_1'\sim C_2'$. Is this right?

REPLY [0 votes]: I see the flaw in my argument in part 2). If have $d.C_1'\sim d.C_2'$. This means that $\mathcal{O}(C_1')^d=\mathcal{O}(C_2')^d$. But this does not mean that $\mathcal{O}(C_1')=\mathcal{O}(C_2')$. For example we for a degree $d $ morphism, we have non trivial line bundle $L$ on $Y$ such that $L^d=\mathcal {O}_Y$


TITLE: Evaluate $\lim_{x \to \infty} \sqrt{x} \sin(\frac{1}{x})$
QUESTION [3 upvotes]: I am trying to evaluate $\lim_{x \to \infty} \sqrt{x} \sin(\frac{1}{x})$. I have been taught that L'Hopital's Rule is only valid for fractions $\frac{f(x)}{g(x)}$ which have the form where $f(x) = g(x) = 0$ or where $g(x) = \pm \infty$ and $f(x)$ is anything.
Right away I notice that this limit evaluates to $\infty \cdot 0$. I need to put this in either the $\frac{0}{0}$ or the $\frac{\text{anything}}{\pm \infty}$ form to use L'Hopital's rule.
So I write $\sqrt{x} \sin(\frac{1}{x}) = \frac{\sin(\frac{1}{x})}{\frac{1}{\sqrt{x}}}$ to get it in the $\frac{\text{anything}}{\pm \infty}$ form. Executing L'Hopital's Rule I find $\lim_{x \to \infty} \sqrt{x} \sin(\frac{1}{x}) = \lim_{x \to \infty} \frac{2\cos(\frac{1}{x})}{\sqrt{x}} = \frac{0}{\infty}$ but this is yet another undetermined form is it not? It seems fairly obvious to me that the limit here is zero but also that we have an undetermined form. Do I have to keep doing rounds of L'Hopital's Rule?

REPLY [4 votes]: $L = \displaystyle \lim_{x \to \infty} \dfrac{1}{\sqrt{x}}\cdot \displaystyle \lim_{x \to \infty} \dfrac{\sin(\frac{1}{x})}{\frac{1}{x}} = 0\cdot 1 = 0$

REPLY [3 votes]: No, it's not an undetermined form, because if we take absolute values and note that $0 \leq |\cos(\text{anything})| \leq 1$, then for all $x > 0$:
$\dfrac{0}{\sqrt{x}} \leq \left |\dfrac{2\cos(\frac{1}{x})}{\sqrt{x}} \right | \leq \dfrac{2}{\sqrt{x}}$.
Now, when we take $x \to \infty$, both the RHS and LHS converge to $0$, so by the squeeze theorem, the middle term converges to $0$ as well.

REPLY [2 votes]: So doing L'Hospital's Rule, I get this: $$\lim_{x\to\infty} \frac{\cos(x^{-1}) (-x^{-2})}{\frac{-1}{2} x^{-3/2}} = \lim_{x\to\infty} \frac{2\cos \frac{1}{x}}{\sqrt{x}} = \frac{-2}{\infty} = 0$$

REPLY [2 votes]: use the fact that for $x$ large $$\sin \left(\frac1x\right) = \frac1x + \mathcal O\left(\frac1{x^2}\right)$$  therefore $$ \sqrt x \sin \left(\frac1x\right) =  \frac1{\sqrt x} + \mathcal O\left(\frac1{x^{1.5}}\right) \to 0 \text{ as } x \to \infty.$$