∎

11institutetext: M. Hayashi 22institutetext: School of Data Science, The
Chinese University of Hong Kong, Shenzhen, Longgang District, Shenzhen,
518172, China, International Quantum Academy (SIQA), Futian District, Shenzhen
518048, China, and Graduate School of Mathematics, Nagoya University, Chikusa-
ku, Nagoya 464-8602, Japan.
22email: e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
# Reverse em-problem based on Bregman divergence and its application to
classical and quantum information theory

Masahito Hayashi

(Received: date / Accepted: date)

###### Abstract

The recent paper (IEEE Trans. IT 69, 1680) introduced an analytical method for
calculating the channel capacity without the need for iteration. This method
has certain limitations that restrict its applicability. Furthermore, the
paper does not provide an explanation as to why the channel capacity can be
solved analytically in this particular case. In order to broaden the scope of
this method and address its limitations, we turn our attention to the reverse
em-problem, proposed by Toyota (Information Geometry, 3, 1355 (2020)). This
reverse em-problem involves iteratively applying the inverse map of the em
iteration to calculate the channel capacity, which represents the maximum
mutual information. However, several open problems remained unresolved in
Toyota’s work. To overcome these challenges, we formulate the reverse em-
problem based on Bregman divergence and provide solutions to these open
problems. Building upon these results, we transform the reverse em-problem
into em-problems and derive a non-iterative formula for the reverse em-
problem. This formula can be viewed as a generalization of the aforementioned
analytical calculation method. Importantly, this derivation sheds light on the
information geometrical structure underlying this special case. By effectively
addressing the limitations of the previous analytical method and providing a
deeper understanding of the underlying information geometrical structure, our
work significantly expands the applicability of the proposed method for
calculating the channel capacity without iteration.

###### Keywords:

maximization Bregman divergence information geometry channel capacity

##  1 Introduction

The em-algorithm is widely recognized as a valuable tool in various domains,
including machine learning and neural networks Amari ; Fujimoto ;
Allassonniere . This algorithm is typically formulated within the framework of
information geometry, which encompasses important concepts such as exponential
families and mixture families Amari-Nagaoka ; Amari-Bregman . This algorithm
aims to solve the em-problem, i.e., the minimization of the divergence between
an exponential family and a mixture family. In other words, the goal is to
identify an element in the mixture family that minimizes the divergence from
the given exponential family. The algorithm achieves this by iteratively
performing projections onto the exponential family and the mixture family.

Recently, Toyota Shoji  addressed the opposite problem related to the
calculation of classical channel capacity, as depicted in Fig 1. Specifically,
he aimed to find an element in the mixture family that maximizes the minimum
divergence from the given exponential family. He observed that if the inverse
operation of the combined projection exists, repeating it leads to the
maximization mentioned above in the case of classical channel capacity Shannon
. Consequently, he proposed an alternative method for calculating the channel
capacity, which has been extensively studied in existing literature Arimoto ;
Blahut ; Matz ; Yu ; SSML ; NWS . This problem is referred to as the reverse
em-problem. However, Toyota did not establish the existence or uniqueness of
the inverse map, nor did he provide a method for computing the inverse of the
map. Furthermore, his analysis was limited to the specific scenario of
classical channel capacity. These issues remain open challenges in the field.

Figure 1: Brief idea of our maximization problem: ${\cal E}$ is an exponential
family. ${\cal M}$ is a mixture family. The solid line expresses the direction
of the em-algorithm. The dashed line expresses the direction of the reverse
em-algorithm. The pair of $\theta_{*}\in{\cal E}$ and $\theta^{*}\in{\cal M}$
realized the maximum.

Furthermore, a recent paper exact  introduced an analytical method for
calculating the channel capacity without the need for iteration. However, this
method has certain restrictions that limit its applicability. Additionally,
the paper does not provide an explanation for why the channel capacity can be
solved analytically in this specific case. Consequently, to expand the
applicable range of the method proposed in the paper exact , this paper aims
to generalize this method and explore the information geometrical background
for the algorithm by the paper exact .

Surprisingly, these two problems can be resolved by addressing the open
problems in the reverse em-problem. By leveraging the framework of Bregman
divergence, we can effectively tackle these open problems. In this study, we
formulate the maximization problem within the framework of Bregman divergence,
following a similar approach as in the papers em-only ; Fujimoto , which is
given in Section 4.1. Moreover, as Theorem 4.3, we establish the uniqueness
and existence of the inverse map under certain conditions in this general
setting. Notably, the case of classical channel capacity satisfies these
conditions, allowing us to successfully address the problem initially proposed
by Toyota Shoji . In this approach, we introduce a specific parameterization
condition for the reverse em-problem and present the iteration process for
each step. Additionally, we evaluate the convergence speed within this general
framework.

In the subsequent step, using the aforementioned results, we convert the
reverse em-problem into an em-problem. In Section 4.7, we derive equivalent
conditions that determine when an element of the mixture family becomes a
fixed point for the iteration function. These equivalent conditions transform
the reverse em-problem into a problem of finding the intersection between an
exponential family and a mixture family, which can be effectively solved
through an em-problem. Notably, in Section 4.8, we demonstrate that under
certain conditions, the reverse em-problem can be further simplified into a
non-iterative form, minimizing a particular convex function. This reduction
results in a problem with fewer free parameters compared to the original
reverse em-problem. Importantly, when the reverse em-problem satisfies
specific conditions, it can be solved analytically without resorting to a
minimization problem. In summary, our approach not only generalizes the
analytical calculation method proposed in the paper exact  but also provides
insights into the information geometrical structure underlying the algorithm.
By addressing the open problems in the reverse em-problem, we make significant
advancements in the field, enabling more efficient and comprehensive solutions
for calculating the channel capacity without iteration.

In the case of the classical channel capacity Shannon ; Arimoto ; Blahut ;
Matz ; Yu ; SSML ; NWS , the above conditions are satisfied. Consequently, the
calculation of the channel capacity can be transformed into a minimization
problem of a specific convex function. This transformation yields a new
calculation algorithm for the classical channel capacity. Notably, this
algorithm can be viewed as a generalization of the analytical algorithm
proposed in the paper exact  because it coincides with the analytical
algorithm when the classical channel satisfies the same condition as described
in exact . Moreover, this reduction to the result presented in exact  provides
insight into the information geometrical background explaining why the channel
capacity can be solved analytically in this special case. Furthermore, even
when the condition from exact  does not hold, our calculation algorithm still
exhibits advantages. Specifically, under certain conditions, the obtained
algorithm has a reduced number of free parameters compared to the original
problem of the classical channel capacity. It is worth noting that a similar
method was previously derived by Muroga Muroga . However, our approach offers
slight improvements over Muroga’s method, as elucidated in Remark 3.
Additionally, we extend the application of our results to two other scenarios:
the capacity of classical wire-tap channels Wyner ; CK79  and the capacity of
classical-quantum channels Holevo ; SW . These maximization problems have been
explored in numerous papers Yasui ; Nagaoka ; Dupuis ; Sutter ; Li ; RISB .

The remaining part of this paper is organized as follows. Section 2 formulates
general basic properties for Bregman divergence. Section 3 explains how the
set of probability distributions and the set of quantum states satisfy the
condition for Bregman divergence. We omit the proofs of statements in Sections
2 and 3, and their proofs are given in the paper em-only . Section 4
formulates the reverse em-problem, and studies its various properties. Section
5 applies these results to the capacity of a classical channel. Section 6
applies these results to the secrecy capacity of a degraded wiretap channel.
Section 7 applies these results to the capacity of a classical-quantum
channel.

##  2 Bregman divergence system

In this section, we formulate the Bregman divergence system as a preparation
for our maximization problem. We omit the proofs of statements in this section
and their proofs are given in the paper em-only . The contents of this section
will be used in the main body and the appendices.

###  2.1 Legendre transform

In this paper, a sequence $a=(a^{i})_{i=1}^{k}$ with an upper index expresses
a vertical vector and a sequence $b=(b_{i})_{i=1}^{k}$ with a lower index
expresses a horizontal vector as

$\displaystyle a=\left(\begin{array}[]{c}a^{1}\\\ a^{2}\\\ \vdots\\\
a^{k}\end{array}\right),\quad b=(b_{1},b_{2},\ldots,b_{k}).$ (5)

We choose an open convex $\Theta$ set in $\mathbb{R}^{d}$ and a
$C^{\infty}$-class strictly convex function $F:\Theta\rightarrow\mathbb{R}$.
Using the convex function $F$, we introduce another parametrization
$\eta=(\eta_{1},\ldots,\eta_{d})\in\mathbb{R}^{d}$ as

$\displaystyle\eta_{j}:=\partial_{j}F(\theta),$ (6)

where $\partial_{j}$ expresses the partial derivative for the $j$-th variable
$\partial_{j}$. We also use the notation for the vector
$\nabla^{(e)}[F](\theta):=(\partial_{j}F(\theta))_{j=1}^{d}$. Hence, the
relation (6) is rewritten as

$\displaystyle\eta=\nabla^{(e)}[F](\theta).$ (7)

Therefore, $\nabla^{(e)}$ can be considered as a horizontal vector.

Since $F$ is a $C^{\infty}$-class strictly convex function, this conversion is
one-to-one. The parametrization $\eta_{j}$ is called the mixture parameter
while the original parameter ${\theta}=({\theta}^{1},\ldots,{\theta}^{d})$ is
called the natural parameter. In the following, $\Xi$ expresses the open set
of vectors $\eta(\theta)=(\eta_{1},\ldots,\eta_{d})$ given in (6). For
$\eta\in\Xi$, we define the Legendre transform $F^{*}={\cal L}[F]$ of $F$

$\displaystyle
F^{*}(\eta)=\sup_{\theta\in\Theta}\langle\eta,\theta\rangle-F(\theta).$ (8)

We denote the partial derivative for the $j$-th variable under the mixture
parameter by $\partial^{j}$. The partial derivative of $F^{*}$ is given as
(Fujimoto, , Section 3)(hayashi, , Section 2.2)

$\displaystyle\partial^{j}F^{*}(\eta(\theta))=\theta^{j}.$ (9)

In the same way as the above, we use the notation
$\nabla^{(m)}[F^{*}](\eta):=(\partial^{j}F^{*}(\eta))_{j=1}^{d}$. The relation
(9) is rewritten as

$\displaystyle\theta=\nabla^{(m)}[F^{*}](\eta(\theta)).$ (10)

In the following discussion, we address subfamilies related to $m$ vectors
$v_{1},\ldots,v_{m}\in\mathbb{R}^{d}$. For preparation for such cases, we
prepare the following two equations, which will be used for calculations based
on mixture parameters. The $d\times m$ matrix $V$ is defined as $(v_{1}\ldots
v_{m})$. The multiplication function of V from the left (right) hand side is
denoted by $L[V]$ ($R[V]$). The relation

$\displaystyle\partial_{j}(F\circ L[V])(\theta)=\frac{\partial
F}{\partial\theta^{j}}(V\theta)=\sum_{i}v_{j}^{i}\partial_{i}F(V\theta)=(R[V]\circ(\nabla^{(e)}[F])\circ
L[V](\theta))_{j},$ (11)

implies that

$\displaystyle\nabla^{(e)}[F\circ L[V]]$
$\displaystyle=R[V]\circ(\nabla^{(e)}[F])\circ L[V].$ (12)

Similarly, the relation

$\displaystyle\nabla^{(m)}[F^{*}\circ R[V]]=L[V]\circ\nabla^{(m)}[F^{*}]\circ
R[V]$ (13)

holds. Also, we have

$\displaystyle(F^{*}\circ
R[V])^{*}(\theta^{\prime})=\sup_{\eta}\Big{(}\langle\eta,\theta^{\prime}\rangle-\sup_{\theta\in\Theta}\Big{(}\langle\eta
V,\theta\rangle-F(\theta)\Big{)}\Big{)}$ $\displaystyle=$
$\displaystyle\sup_{\eta}\inf_{\theta\in\Theta}\big{(}\langle\eta,\theta^{\prime}-V\theta\rangle+F(\theta)\big{)}=\inf_{\theta:\theta^{\prime}=V\theta}F(\theta).$
(14)

###  2.2 Exponential subfamily

Next, we introduce an exponential subfamily, and discuss its properties. We
say that a subset $\mathcal{E}\subset\Theta$ is an exponential subfamily
generated by $l$ linearly independent vectors
$v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ at $\theta_{0}\in\Theta$ when the subset
$\mathcal{E}$ is given as

$\displaystyle\mathcal{E}$ $\displaystyle=\left\\{\phi_{{\cal
E}}^{(e)}(\bar{\theta})\in\Theta\left|\bar{\theta}\in\Theta_{{\cal
E}}\right.\right\\}.$ (15)

In the above definition, $\phi_{{\cal E}}^{(e)}(\bar{\theta})$ is defined for
$\bar{\theta}=(\bar{\theta}^{1},\ldots,\bar{\theta}^{l})\in\mathbb{R}^{l}$ as

$\displaystyle\phi_{{\cal E}}^{(e)}(\bar{\theta})$
$\displaystyle:=\theta_{0}+\sum_{j=1}^{l}\bar{\theta}^{j}v_{j}$ (16)

and the set $\Theta_{{\cal E}}$ is defined as

$\displaystyle\Theta_{{\cal E}}:=\\{\bar{\theta}\in\mathbb{R}^{l}|\phi_{{\cal
E}}^{(e)}(\bar{\theta})\in\Theta\\}.$ (17)

The set $\Theta_{{\cal E}}$ is an open set because $\Theta$ is an open set. In
the following, we restrict the domain of $\phi_{{\cal E}}^{(e)}$ to
$\Theta_{{\cal E}}$. We define the inverse map $\psi_{{\cal
E}}^{(e)}:=(\phi_{{\cal E}}^{(e)})^{-1}:{\cal E}\to\Theta_{{\cal E}}$.

For an exponential subfamily ${\cal E}$, we define the function $F_{{\cal E}}$
as

$\displaystyle F_{{\cal E}}(\bar{\theta}):=F(\phi_{{\cal
E}}^{(e)}(\bar{\theta})).$ (18)

In fact, even in an exponential subfamily ${\cal E}$, we can employ the
mixture parameter ${\psi}_{{\cal E},j}^{(m)}(\phi_{{\cal
E}}^{(e)}(\bar{\theta})):=\partial_{j}F_{{\cal E}}(\bar{\theta})$ because the
map $\bar{\theta}\mapsto F_{{\cal E}}(\bar{\theta})$ is also a
$C^{\infty}$-class strictly convex function. For the latter discussion, we
prepare the set $\Xi_{{\cal E}}:=\\{(\partial_{j}F_{{\cal
E}}(\bar{\theta}))_{j=1}^{l}\\}_{\bar{\theta}\in\Theta_{{\cal E}}}$, and the
inverse map $\phi_{{\cal E}}^{(m)}:=(\psi_{{\cal E}}^{(m)})^{-1}:\Xi_{{\cal
E}}\to{\cal E}$.

###  2.3 Mixture subfamily

Next, we introduce a mixture subfamily, and discuss its properties. For $d$
linearly independent vectors $u_{1},\ldots,u_{d}\in\mathbb{R}^{d}$, and a
vector $a=(a_{1},\ldots,a_{d-k})^{T}\in\mathbb{R}^{d-k}$, we say that a subset
$\mathcal{M}\subset\Theta$ is a mixture subfamily generated by the constraint

$\displaystyle\sum_{i=1}^{d}u^{i}_{k+j}\partial_{i}F(\theta)=a_{j}$ (19)

for $j=1,\ldots,d-k$ when the subset $\mathcal{M}$ is written as

$\displaystyle\mathcal{M}=\left\\{\theta\in\Theta\left|\hbox{ Condition
\eqref{const1} holds.}\right.\right\\}.$ (20)

The $d\times d$ matrix $U$ is defined as $(u_{1}\ldots u_{d})$. To make a
parametrization in the above mixture subfamily ${\cal M}$, we set the new
natural parameter $\bar{\theta}=(\bar{\theta}^{1},\ldots,\bar{\theta}^{d})$ as
$\theta=U\bar{\theta}$, and introduce the new mixture parameter

$\displaystyle\bar{\eta}_{i}=\partial_{j}(F\circ U)(\bar{\theta}).$ (21)

Since the relation $\bar{\eta}_{k+i}=a_{i}$ holds for $i=1,\ldots,d-k$ in
${\cal M}$, the initial $k$ elements $\bar{\eta}_{1},\ldots,\bar{\eta}_{k}$
give a parametrization for ${\cal M}$. To make the parametrization, we define
the map $\psi_{\cal M}^{(m)}$ as $\psi_{\cal
M}^{(m)}(U\bar{\theta}):=(\partial_{j}(F\circ U)(\bar{\theta}))_{j=1}^{k}$.
The set $\Xi_{{\cal M}}:=\\{\psi_{\cal M}^{(m)}(\theta)|{\theta}\in{\cal
M}\\}$ works as the range of the new mixture parameters, and we also employ
the inverse map $\phi_{{\cal M}}^{(m)}:=(\psi_{{\cal
M}}^{(m)})^{-1}:\Xi_{{\cal M}}\to{\cal M}$. Since $\Theta$ is an open set, the
set $\Xi_{{\cal M}}$ is an open subset of $\mathbb{R}^{k}$. When an element
$\bar{\eta}\in\Xi_{{\cal M}}$ satisfies $\bar{\eta}_{j}=\partial_{j}(F\circ
U)(\bar{\theta})$ for $j=1,\ldots,k$, we have

$\displaystyle\partial^{i}(F\circ U)^{*}(\bar{\eta},a)=\bar{\theta}^{i}$ (22)

for $i=1,\ldots,d$. The strict convexity of the map $\bar{\eta}\mapsto(F\circ
U)^{*}(\bar{\eta},a)$ guarantees that the map
$\bar{\eta}\mapsto(\partial^{i}(F\circ U)^{*}(\bar{\eta},a))_{i=1}^{k}$ is
one-to-one. Hence, the initial $k$ elements
$\bar{\theta}^{1},\ldots,\bar{\theta}^{k}$ form a parametrization for ${\cal
M}$. In other words, the relation

$\displaystyle((U^{-1}\theta)^{i})_{i=1}^{k}=(\partial^{i}(F\circ
U)^{*}(\psi_{\cal M}^{(m)}({\theta}),a))_{i=1}^{k}$ (23)

holds. We define the set $\Theta_{\cal
M}:=\\{((U^{-1}\theta)^{i})_{i=1}^{k}|{\theta}\in{\cal M}\\}$, which is
rewritten as

$\displaystyle\Theta_{\cal
M}=\left\\{(\theta^{1},\ldots,\theta^{k})\in\mathbb{R}^{k}\left|\begin{array}[]{l}\exists(\theta^{k+1},\ldots,\theta^{d})\in\mathbb{R}^{d-k}\hbox{
such that}\\\
\sum_{i=1}^{d}u^{i}_{k+j}\partial_{i}F(U(\theta^{1},\ldots,\theta^{d}))=a_{j}\\\
\hbox{ for }j=1,\ldots,d-k.\end{array}\right.\right\\}.$ (27)

When the mixture subfamily ${\cal M}$ forms an exponential subfamily generated
by $u_{1},\ldots,u_{k}$, it is possible to retake $\theta_{0}$ such that
$(U^{-1}\theta_{0})^{i}=0$ for $i=1,\ldots,k$. Therefore, the subsets
$\Theta_{{\cal M}}$ and $\Xi_{{\cal M}}$ are the same subsets defined in
Subsection 2.2.

###  2.4 Bregman Divergence and $m$\- and $e$\- projections

Next, we introduce the concept of Bregman Divergence, which is a
generalization of the conventional divergence.

######  Definition 1 (Bregman Divergence)

We choose an open set $\Theta$ in $\mathbb{R}^{d}$ and a $C^{\infty}$-class
strictly convex function $F:\Theta\rightarrow\mathbb{R}$. We define the
Bregman divergence $D^{F}$ as

$D^{F}(\theta_{1}\|\theta_{2}):=\langle\nabla^{(e)}[F](\theta_{1}),\theta_{1}-\theta_{2}\rangle-F(\theta_{1})+F(\theta_{2})~{}(\theta_{1},\theta_{2}\in\Theta).$
(28)

Our Bregman divergence system is defined as the triplet $(\Theta,F,D^{F})$.
Given a one-variable convex function $\mu(t)$, we have

$\displaystyle\mu^{\prime}(\bar{t})(\bar{t}-\tilde{t})-\mu(\bar{t})+\mu(\tilde{t})=\int^{\bar{t}}_{\tilde{t}}\mu^{\prime\prime}({t})({t}-\tilde{t})dt.$
(29)

Now, we use the Hesse matrix
$J_{i,j}(\theta):=\frac{\partial^{2}F}{\partial\theta^{i}\partial\theta^{j}}(\theta)$.
We substitute $F(\theta_{2}+t(\theta_{1}-\theta_{2})$ into $\mu(t)$ in (29)
with $\bar{t}=1$ and $\tilde{t}=0$. this quantity can be written as

$D^{F}(\theta_{1}\|\theta_{2})=\int_{0}^{1}\sum_{i,j}(\theta_{1}^{i}-\theta_{2}^{i})(\theta_{1}^{j}-\theta_{2}^{j})J_{i,j}(\theta_{2}+t(\theta_{1}-\theta_{2}))tdt.$
(30)

In addition, since the relations (6) and (8) imply

$\displaystyle
F^{*}(\eta)=\sum_{i=1}^{d}\theta^{i}\eta(\theta_{i})-F(\theta)=\langle\eta(\theta),\theta\rangle-F(\theta),$
(31)

the relations

$\displaystyle
D^{F^{*}}(\nabla^{(e)}[F](\theta_{2})\|\nabla^{(e)}[F](\theta_{1}))=D^{F^{*}}(\eta(\theta_{2})\|\eta(\theta_{1}))$
$\displaystyle=$
$\displaystyle\langle\eta(\theta_{2})-\eta(\theta_{1}),\theta_{2}\rangle-F^{*}(\eta(\theta_{2}))+F^{*}(\eta(\theta_{1}))$
$\displaystyle=$
$\displaystyle\langle\eta(\theta_{1}),\theta_{1}-\theta_{2}\rangle-F(\theta_{1})+F(\theta_{2})=D^{F}(\theta_{1}\|\theta_{2})$
(32)

hold.

In fact, when we restrict both inputs into elements of an exponential
subfamily ${\cal E}$, the characterization

$\displaystyle D^{F}(\phi_{{\cal E}}^{(e)}(\bar{\theta}_{1})\|\phi_{{\cal
E}}^{(e)}(\bar{\theta}_{2}))=D^{F_{{\cal
E}}}(\bar{\theta}_{1}\|\bar{\theta}_{2})$ (33)

holds for $\bar{\theta}_{1},\bar{\theta}_{2}\in\Theta_{{\cal E}}$. Therefore,
the restriction of the Bregman divergence system $(\Theta,F,D^{F})$ to ${\cal
E}$ can be considered as the Bregman divergence system $(\Theta_{{\cal
E}},F_{{\cal E}},D^{F_{\cal E}})$. A simple calculation shows the following
proposition.

######  Proposition 1 (Pythagorean TheoremAmari-Nagaoka )

Given a vector $(a_{j})_{j=1}^{l}$, we consider an exponential subfamily
$\mathcal{E}\subset\Theta$ generated by $l$ vectors
$v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ at $\theta_{0}\in\Theta$, and a mixture
subfamily $\mathcal{M}\subset\Theta$ generated by the constraint
$\sum_{i=1}^{d}v^{i}_{j}\eta_{i}(\theta)=a_{j}$ for $j=1,\ldots,l$. Assume
that an intersection $\theta^{*}$ of $\mathcal{E}$ and $\mathcal{M}$ exists.
Any pair of $\theta\in\mathcal{E}$ and $\theta^{\prime}\in\mathcal{M}$
satisfies

$\displaystyle
D^{F}(\theta\|\theta^{\prime})=D^{F}(\theta\|\theta^{*})+D^{F}(\theta^{*}\|\theta^{\prime}).$
(34)

###### Lemma 1

We consider an exponential family $\mathcal{E}$ generated by $l$ vectors
$v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$. The following conditions are equivalent
for an exponential subfamily $\mathcal{E}$, $\theta^{*}\in\mathcal{E}$, and
$\theta_{0}\in\Theta$.

(E0)

The element $\theta^{*}\in\mathcal{E}$ achieves a local minimum for the
minimization
$\min_{\hat{\theta}\in\mathcal{E}}D^{F}(\theta_{0}\|\hat{\theta})$.

(E1)

The element $\theta^{*}\in\mathcal{E}$ achieves the minimum value for the
minimization
$\min_{\hat{\theta}\in\mathcal{E}}D^{F}(\theta_{0}\|\hat{\theta})$.

(E2)

Let $\mathcal{M}\subset\Theta$ be the mixture subfamily generated by the
constraint
$\sum_{i=1}^{d}v^{i}_{j}\eta_{i}(\theta)=\sum_{i=1}^{d}v^{i}_{j}\eta_{i}(\theta_{0})$
for $j=1,\ldots,l$. The element $\theta^{*}\in\mathcal{E}$ belongs to the
intersection $\mathcal{M}\cap\mathcal{E}$.

Further, when an element $\theta^{*}\in\mathcal{E}$ with the above condition
exists, it is unique.

In the following, we denote the above mixture family $\mathcal{M}$ by
$\mathcal{M}_{\theta_{0}\to\mathcal{E}}$. Then, $\theta^{*}\in\mathcal{E}$ is
called the $m$-projection of $\theta$ onto an exponential subfamily
$\mathcal{E}$, and is denoted by
$\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta)$ because the points
$\theta$ and $\theta^{*}$ are connected via the mixture family
$\mathcal{M}_{\theta_{0}\to\mathcal{E}}$. The minimum value
$\min_{\hat{\theta}\in\mathcal{E}}D^{F}(\theta\|\hat{\theta})$ is called the
projected Bregman divergence between $\theta$ and $\mathcal{E}$.

Exchanging the roles of the exponential family and the mixture family leads
the following lemma.

###### Lemma 2

We choose $l$ vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$. Let $\mathcal{M}$
be a mixture family generated by the constraint
$\sum_{i=1}^{d}v^{i}_{j}\eta_{i}(\theta)=\sum_{i=1}^{d}v^{i}_{j}\eta_{i}(\theta_{0})$
for $j=1,\ldots,l$. The following conditions are equivalent for the mixture
family $\mathcal{M}$, $\theta^{\dagger}\in\mathcal{M}$, and
$\theta_{0}\in\Theta$.

(M0)

The element $\theta^{\dagger}\in\mathcal{M}$ achieves a local minimum for the
minimization
$\min_{\hat{\theta}\in\mathcal{M}}D^{F}(\hat{\theta}\|\theta_{0})$.

(M1)

The element $\theta^{\dagger}\in\mathcal{M}$ achieves the minimum value for
the minimization
$\min_{\hat{\theta}\in\mathcal{M}}D^{F}(\hat{\theta}\|\theta_{0})$.

(M2)

Let $\mathcal{E}\subset\Theta$ be the mixture subfamily generated by $l$
vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ at $\theta_{0}\in\Theta$. The
element $\theta^{\dagger}\in\mathcal{M}$ belongs to the intersection
$\mathcal{M}\cap\mathcal{E}$.

Further, when there exists an element $\theta^{\dagger}\in\mathcal{M}$ to
satisfy the above condition, such an element is unique.

In the following, the symbol $\mathcal{E}_{\theta_{0}\to\mathcal{M}}$
expresses the above exponential family $\mathcal{E}$. Then, an element
$\theta^{\dagger}\in\mathcal{M}$ is called the $e$-projection of $\theta$ onto
a mixture subfamily $\mathcal{M}$, and is denoted by
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}(\theta)$ because the points
$\theta$ and $\theta^{\dagger}$ are connected via the exponential family
$\mathcal{E}_{\theta_{0}\to\mathcal{M}}$. When $\mathcal{M}$ is an exponential
subfamily and a mixture subfamily, we can define both projections
$\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{M}}$ and
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}$, and these projections are
different maps. Hence, the subscripts $(e)$ and $(m)$ are needed.

###### Lemma 3

Consider an exponential subfamily $\mathcal{E}\subset\Theta$ generated by $l$
vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ at $\theta_{0}\in\Theta$. For
$\theta_{*}\in\Theta$, the element
$\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta_{*})=\theta^{*}\in{\cal
E}$ is uniquely characterized as
$\sum_{j=1}^{d}v_{i}^{j}\partial_{j}F(\theta^{*})=\sum_{j=1}^{d}v_{i}^{j}\partial_{j}F(\theta_{*})$,
i.e.,
$R[V]\circ\nabla^{(e)}[F](\theta^{*})=R[V]\circ\nabla^{(e)}[F](\theta_{*})$.
That is, the mixture parameter of the element
$\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta_{*})=\theta^{*}\in{\cal
E}$ is given by the above condition.

###### Lemma 4

Let $d$ vectors $u_{1},\ldots,u_{d}\in\mathbb{R}^{d}$ be linearly independent.
We consider a mixture subfamily $\mathcal{M}\subset\Theta$ generated by the
constraint

$\displaystyle\sum_{i=1}^{d}u^{i}_{j}\partial_{i}F(\theta)=a_{j}$ (35)

for $j=k+1,\ldots,d$. For an element $\theta_{\dagger}\in\Theta$, the
existence of the maximum $\max_{\theta\in{\cal
M}}D^{F}(\theta\|\theta_{\dagger})$ yields the following characterizations for
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}(\theta_{\dagger})$.

(C1)

The point
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}(\theta_{\dagger})=\theta^{\dagger}\in{\cal
M}$ is uniquely characterized as

$\displaystyle(U^{-1}{\theta}^{\dagger})^{i}=(U^{-1}{\theta}_{\dagger})^{i}$
(36)

for $i=1,\ldots,k$, where $U$ is defined in the same way as Subsection 2.3.

(C2)

We choose the exponential subfamily ${\cal E}$ generated by $d-k$ vectors
$u_{k+1},\ldots,u_{d}\in\mathbb{R}^{d}$ at $\theta_{\dagger}$. The
intersection between ${\cal M}$ and ${\cal E}$ is composed of the unique
element $\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}(\theta_{\dagger})$.

(C3)

The point
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}(\theta_{\dagger})=\theta^{\dagger}\in{\cal
M}$ is uniquely characterized as
$\theta_{\dagger}+\sum_{j^{\prime}=1}^{d-k}\bar{\tau}^{j^{\prime}}u_{k+j^{\prime}}$,
where $(\bar{\tau}^{1},\ldots,\bar{\tau}^{d-k})$ is the unique element to
satisfy

$\displaystyle\frac{\partial}{\partial\tau^{j}}F\Big{(}\theta_{*}+\sum_{j^{\prime}=1}^{l}\tau^{j^{\prime}}u_{k+j^{\prime}}\Big{)}=a_{j}$
(37)

for $j=1,\ldots,d-k$.

Lemmas 1 and 2 show the importance to find a sufficient condition for (E2) and
(M2). To seek such a condition with a convex function $F$ and $\Theta$, we
consider the following conditions with $l$ linearly independent fixed vectors
$v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$;

(M3)

We denote the exponential family generated by the $l$ linearly independent
vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ at $\theta_{0}\in\Theta$ by
$\mathcal{E}(\theta_{0})$. The set $\Xi_{\mathcal{E}(\theta_{0})}$ does not
depend on $\theta_{0}\in\Theta$. In this case, this set is denoted by
$\Xi(v_{1},\ldots,v_{l})$. Notice that the set $\Xi_{\mathcal{E}(\theta_{0})}$
is defined after (18).

(E3)

We denote the mixture family generated by the constraint
$\sum_{i=1}^{d}v^{i}_{j}\partial_{i}F(\theta)=a_{j}$ for $j=1,\ldots,l$ by
$\mathcal{M}(a_{1},\ldots,a_{l})$. When the set
$\Theta_{\mathcal{M}(a_{1},\ldots,a_{l})}$ is defined in the way as (27), it
does not depend on $(a_{1},\ldots,a_{l})\in\mathbb{R}^{l}$ unless
$\mathcal{M}(a_{1},\ldots,a_{l})$ is empty. In this case, this set is denoted
by $\Theta(v_{1},\ldots,v_{l})$.

Under the above condition, we have the following lemmas.

###### Lemma 5

Suppose that the $l$ linearly independent vectors
$v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ satisfy Condition (M3). Given
$(a_{1},\ldots,a_{l})\in\Xi(v_{1},\ldots,v_{l})$, the mixture family
$\mathcal{M}(a_{1},\ldots,a_{l})$ is defined by using the condition (35).
Then, for $\theta_{0}\in\Theta$, the projected point
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}(a_{1},\ldots,a_{l})}(\theta_{0})$
exists.

###### Lemma 6

Suppose that the $l$ linearly independent vectors
$v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ satisfy Condition (E3). Then, for
$(b^{1},\ldots,b^{d-l})\in\mathbb{R}^{d-l}$ and $\theta_{0}\in\Theta$, the
projected point
$\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}(b^{1},\ldots,b^{d-l})}(\theta_{0})$
exists unless $\mathcal{E}(b^{1},\ldots,b^{d-l})$ is empty where the
exponential family $\mathcal{E}(b^{1},\ldots,b^{d-l})$ is defined as
$\\{(\sum_{i=1}^{d-l}u_{i}^{j}b^{i}+\sum_{i=1}^{l}u_{i}^{j}\theta^{i})_{j=1}^{d}|(\theta^{1},\ldots,\theta^{l})\in\mathbb{R}^{l}\\}\cap\Theta$.

Therefore, to consider the existence of both types of projections universally,
we introduce the following conditions for the Bregman divergence system
$(\Theta,F,D^{F})$.

(M4)

Any $l$ linearly independent vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$
satisfy the condition (M3) for $l=1,\ldots,d-1$.

(E4)

Any $l$ linearly independent vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$
satisfy the condition (E3) for $l=1,\ldots,d-1$.

When (M4) holds, the $e$-projection
$\mathop{\Gamma}\nolimits^{(e),F}_{\mathcal{M}}$ can be defined for any
mixture subfamily $\mathcal{M}$. Also, when (E4) holds, the $m$-projection
$\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}$ can be defined for any
exponential subfamily $\mathcal{E}$. Therefore, these two conditions are
helpful for the analysis of these projections.

Table 1: Summary of dimensions Symbol | Space
---|---
$d$ | Dimension of the whole space
$l$ | Dimension of Exponential family ${\cal E}$
$k$ | Dimension of Mixture family ${\cal M}$

###  2.5 Evaluation of Bregman divergence without Pythagorean theorem

Next, we evaluate Bregman divergence when we cannot use the Pythagorean
theorem. For this aim, we focus on $J(\theta)^{-1}$, i.e., the inverse of the
Hesse matrix $J(\theta$) defined for the parameters of $\Theta$. Then, we
introduce the quantity $\gamma(\hat{\Theta}|{\Theta})$ for a subset
$\hat{\Theta}$ of $\Theta$.

$\displaystyle\gamma(\hat{\Theta}|{\Theta}):=$
$\displaystyle\inf\\{\gamma|\gamma J(\theta_{1})^{-1}\geq
J(\theta_{2})^{-1}\hbox{ for }\theta_{1},\theta_{2}\in\hat{\Theta}\\}.$ (38)

We say that a subset $\hat{\Theta}$ of $\Theta$ is a star subset for an
element $\theta_{1}\in\hat{\Theta}$ when
$\lambda\eta(\theta)+(1-\lambda)\eta(\theta_{1})\in\eta(\hat{\Theta})$ for
$\theta\in\hat{\Theta}$ and $\lambda\in(0,1)$.

Then, we have the following theorem.

###### Theorem 2.1

We assume that the condition (M4) holds. Then, for a star subset with
$\hat{\Theta}$ for $\theta_{1}\in\hat{\Theta}$, $\theta_{2}\in\hat{\Theta}$,
and $\theta_{3}\in\Theta$, we have

$\displaystyle D^{F}(\theta_{1}\|\theta_{2})$ $\displaystyle\leq$
$\displaystyle
D^{F}(\theta_{1}\|\theta_{3})+\gamma(\hat{\Theta}|{\Theta})D^{F}(\theta_{2}\|\theta_{3})+2\gamma(\hat{\Theta}|{\Theta})\sqrt{D^{F}(\theta_{1}\|\theta_{3})D^{F}(\theta_{2}\|\theta_{3})}.$
(39)

##  3 Examples of Bregman divergence

###  3.1 Classical system

We consider the set of probability distributions on the finite set ${\cal
X}=\\{1,\ldots,n\\}$. We focus on $d$ linearly independent functions
$f_{1},\ldots,f_{d}$ defined on ${\cal X}$, where the linear space spanned by
$f_{1},\ldots,f_{d}$ does not contain a constant function and $d\leq n-1$.
Then, the $C^{\infty}$ strictly convex function $\mu$ on $\mathbb{R}^{d}$ is
defined as $\mu(\theta):=\log\big{(}\sum_{x\in{\cal
X}}\exp(\sum_{j=1}^{d}\theta^{j}f_{j}(x))\big{)}$, which yields the Bregman
divergence system $(\mathbb{R}^{d},\mu,D^{\mu})$. When $d=n-1$, any
probability distribution with full support on ${\cal X}$ can be written as
$P_{\theta}$, which is defined as
$P_{\theta}(x):=\exp\Big{(}(\sum_{j=1}^{n-1}\theta^{j}f_{j}(x))-\mu(\theta)\Big{)}$.
It is known that the KL divergence equals the Bregman divergence of the
potential function $\mu$ (Amari-Nagaoka, , Section 3.4), i.e., we have

$\displaystyle
D^{\mu}(\theta\|\theta^{\prime})=D(P_{\theta}\|P_{\theta^{\prime}})$ (40)

for $\theta\in\mathbb{R}^{d}$, where the KL divergence $D(q\|p)$ is defined as

$\displaystyle D(q\|p)=\sum_{\omega}p(\omega)(\log p(\omega)-\log q(\omega)).$
(41)

When the parameter $\theta$ is limited to
$(\bar{\theta},\underbrace{0,\ldots,0}_{d-l})$ with
$\bar{\theta}\in\mathbb{R}^{l}$, the set of distributions $P_{\theta}$ forms
an exponential subfamily. Also, when the linear space spanned by $d-k$
linearly independent functions $g_{1},\ldots,g_{d-k}$ does not contain a
constant function, for $d-k$ constants $a_{1},\ldots,a_{d-k}$, the following
set of distributions forms a mixture subfamily;

$\displaystyle\Big{\\{}P_{\theta}\Big{|}\sum_{x\in{\cal
X}}g_{i}(x)P_{\theta}(x)=a_{i}\hbox{ for }i=1,\ldots,d-k\Big{\\}}.$ (42)

###### Example 1

When ${\mathcal{X}}$ is given as ${\mathcal{X}}_{1}\times{\mathcal{X}}_{2}$
with $n_{i}=|{\mathcal{X}}_{i}|$, the set of distributions with full support
on ${\mathcal{X}}$ forms a Bregman divergence system
$(\mathbb{R}^{d},\mu,D^{\mu})$. When $f_{i}$ is a function on
${\mathcal{X}}_{1}$ or ${\mathcal{X}}_{2}$ with $i=1,\ldots,n_{1}+n_{2}-2$,
and they are linearly independent, the exponential subfamily generated by
$f_{1},\ldots,f_{n_{1}+n_{2}-2}$ forms the set ${\cal
P}_{{\mathcal{X}}_{1}}\times{\cal P}_{{\mathcal{X}}_{2}}$ of independent
distributions on ${\mathcal{X}}_{1}\times{\mathcal{X}}_{2}$.

###### Example 2

When ${\mathcal{X}}$ is given as
${\mathcal{X}}_{1}\times{\mathcal{X}}_{2}\times{\mathcal{X}}_{3}$ with
$n_{i}=|{\mathcal{X}}_{i}|$, the set of distributions with full support on
${\mathcal{X}}$ forms a Bregman divergence system
$(\mathbb{R}^{d},\mu,D^{\mu})$. When $f_{i}$ is a function on
${\mathcal{X}}_{1},{\mathcal{X}}_{2}$ or ${\mathcal{X}}_{2},{\mathcal{X}}_{3}$
with $i=1,\ldots,n_{2}(n_{1}+n_{3}-1)-1$, and they are linearly independent,
the exponential subfamily generated by
$f_{1},\ldots,f_{n_{2}(n_{1}+n_{3}-1)-1}$ forms the set ${\cal
P}_{X_{1}-X_{2}-X_{3}}$ of distributions on
${\mathcal{X}}_{1}\times{\mathcal{X}}_{2}\times X_{3}$ to satisfy the
Markovian condition $X_{1}-X_{2}-X_{3}$.

For the possibility of the projection, we have the following lemma. For its
proof, see em-only .

###### Lemma 7

The Bregman divergence system $(\mathbb{R}^{d},\mu,D^{\mu})$ defined in this
subsection satisfies the conditions (E4) and (M4).

###  3.2 Quantum system

In the quantum system, we focus on the $n$-dimensional Hilbert space ${\cal
H}$ hayashi . We choose $d$ linearly independent Hermitian matrices
$X_{1},\ldots,X_{d}$ on ${\cal H}$, where the linear space spanned by
$X_{1},\ldots,X_{d}$ does not contain the identity matrix. Then, we define the
$C^{\infty}$ strictly convex function $\mu$ on $\mathbb{R}^{d}$ as
$\mu(\theta):=\log(\operatorname{\mathrm{Tr}}\exp(\sum_{j=1}^{d}\theta^{j}X_{j}))$.
A quantum state on ${\cal H}$ is given as a positive semi-definite Hermitian
matrix $\rho$ with the condition $\operatorname{\mathrm{Tr}}\rho=1$, which is
called a density matrix. We denote the set of density matrices by ${\cal
S}({\cal H})$. Any density matrix with full support on ${\cal H}$ can be
written as $\rho_{\theta}$, which is defined as
$\rho_{\theta}:=\exp\Big{(}(\sum_{j=1}^{d}\theta^{j}X_{j})-\mu(\theta)\Big{)}$.
It is known that the relative entropy equals the Bregman divergence of the
potential function $\mu$ (Amari-Nagaoka, , Section 7.2), i.e., we have

$\displaystyle
D^{\mu}(\theta\|\theta^{\prime})=D(\rho_{\theta}\|\rho_{\theta^{\prime}})$
(43)

for $\theta\in\mathbb{R}^{d}$, where the relative entropy
$D(\rho\|\rho^{\prime})$ is defined as

$\displaystyle
D(\rho\|\rho^{\prime})=\operatorname{\mathrm{Tr}}\rho(\log\rho-\log\rho^{\prime}).$
(44)

When the parameter $\theta$ is limited to
$(\bar{\theta},\underbrace{0,\ldots,0}_{d-l})$ with
$\bar{\theta}\in\mathbb{R}^{l}$, the set of distributions $\rho_{\theta}$
forms an exponential family. Also, when the linear space spanned by $d-k$
linearly independent Hermitian matrices $Y_{1},\ldots,Y_{d-k}$ does not
contain a constant function, for $d-k$ constants $a_{1},\ldots,a_{d-k}$, the
following set of distributions forms a mixture family;

$\displaystyle\Big{\\{}\rho_{\theta}\Big{|}\operatorname{\mathrm{Tr}}Y_{i}\rho_{\theta}=a_{i}\hbox{
for }i=1,\ldots,d-k\Big{\\}}.$ (45)

For the possibility of the projection, we have the following lemma. For its
proof, see em-only .

###### Lemma 8

The Bregman divergence system $(\mathbb{R}^{d},\mu,D^{\mu})$ defined in this
section satisfies the conditions (E4) and (M4).

##  4 Reverse em-problem

###  4.1 General formulation

In this section, we address a maximization problem for a pair of a
$k$-dimensional mixture subfamily $\mathcal{M}$ and an $l$-dimensional
exponential subfamily $\mathcal{E}$. Similar to Section IV of em-only , we
assume the following condition;

(B1)

The Bregman divergence system $(\Theta,F,D^{F})$ satisfies the conditions (E4)
and (M4).

The meaning of (B1) is clear. In the general setting of Bregman, $m$\- and
$e$\- projections do not necessarily exist. To guarantee their existence, we
assume condition (B1), which is satisfied when they are given as probability
distributions or density operators.

Hence, the minimum
$\min_{\theta^{\prime}\in\mathcal{E}}D^{F}(\theta\|\theta^{\prime})$ exists.
As discussed in Section IV of em-only , the em-algorithm is a method to
minimize the divergence between two points in the mixture and exponential
subfamilies ${\cal E}$ and ${\cal M}$, which is formulated as the following
minimization under the framework of Bregman divergence system:

$C_{\inf}(\mathcal{M},\mathcal{E}):=\inf_{\theta\in\mathcal{M}}D^{F}(\theta\|\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta))=\inf_{\theta\in\mathcal{M}}\min_{\theta^{\prime}\in\mathcal{E}}D^{F}(\theta\|\theta^{\prime}).$
(46)

For this problem, the em-algorithm, Algorithm 1, is known.

Algorithm 1 em-algorithm

Choose the initial value ${\theta}_{(1)}\in\mathcal{E}$;

repeat

m-step: Calculate ${\theta}^{(t+1)}:=\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}({\theta}_{(t)})$. That is, ${\theta}^{(t+1)}$ is given as $\mathop{\rm
argmin}\limits_{\theta\in\mathcal{M}}D^{F}({\theta}\|{\theta}_{(t)})$, i.e.,
the unique element in ${\cal M}$ to realize the minimum of the smooth convex
function $\theta\mapsto D^{F}(\theta\|{\theta}_{(t)})$.

e-step: Calculate ${\theta}_{(t+1)}:=\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t+1)})$. That is, ${\theta}_{(t+1)}$ is given as $\mathop{\rm
argmin}\limits_{\theta^{\prime}\in\mathcal{E}}D^{F}({\theta}^{(t+1)}\|\theta^{\prime})$,
i.e., the unique element in ${\cal E}$ to realize the minimum of the smooth
convex function $\theta^{\prime}\mapsto
D^{F}({\theta}^{(t+1)}\|\theta^{\prime})$.

until convergence.

Instead of the em-problem (46), we address the following maximization problem
for a pair of a mixture subfamily $\mathcal{M}$ and an exponential subfamily
$\mathcal{E}$;

$C_{\sup}(\mathcal{M},\mathcal{E}):=\sup_{\theta\in\mathcal{M}}D^{F}(\theta\|\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta))=\sup_{\theta\in\mathcal{M}}\min_{\theta^{\prime}\in\mathcal{E}}D^{F}(\theta\|\theta^{\prime}).$
(47)

Also, we need to characterize the following set;

$\Theta^{*}(\mathcal{M},\mathcal{E}):=\\{\theta\in\mathcal{M}|C_{\sup}(\mathcal{M},\mathcal{E})=D^{F}(\theta\|\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta))\\}.$
(48)

When the above set is not empty and is composed of a unique element, we need
to find the maximization point

$\theta^{*}(\mathcal{M},\mathcal{E}):=\mathop{\rm
argmax}\limits_{\theta\in\mathcal{M}}D^{F}(\theta\|\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta)).$
(49)

Some of maximization problems in information theory can be written in the
above form. The above maximization asks to maximize the divergence between two
points in the mixture and exponential subfamilies ${\cal E}$ and ${\cal M}$.
Hence, as pointed out in Toyota Shoji , we can expect that the reverse
operation of the em-algorithm gives the solution of the maximization given in
(47), which is illustrated in Fig. 1. Since the minimum
$\min_{\theta\in\mathcal{M}}D^{F}(\theta\|\theta^{\prime})$ exists due to the
condition (B1), the em-algorithm repetitively applies the function
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal M}}$ for an
element $\theta\in{\cal M}$. Therefore, when the function
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal M}}$ is a
surjective map from ${\cal M}$ to ${\cal M}$, there exists its inverse map
$(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal M}})^{-1}$. Since
the application of $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal M}}$ monotonically
decreases the Bregman divergence, the application of the inverse map increases
the Bregman divergence

$\displaystyle D^{F}(\theta\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta))$ $\displaystyle\leq$ $\displaystyle
D^{F}((\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal
M}})^{-1}(\theta)\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}((\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal
M}})^{-1}(\theta))).$ (50)

In this case, when we apply the updating rule
${\theta}^{(t+1)}:=(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal
M}})^{-1}({\theta}^{(t)})$, it is expected that the outcome ${\theta}^{(t)}$
of the repetitive application of the inverse map converges to
$\theta^{*}(\mathcal{M},\mathcal{E})$. Due to the above reason, we call the
maximization (47) the reverse em-problem.

###  4.2 Precision analysis

For the analysis of the precision, we introduce the following condition for
$\mathcal{M}$ and $\mathcal{E}$.

(B2)

The relation

$\displaystyle D^{F}(\theta^{\prime}\|\theta)\leq
D^{F}(\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{\prime})\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}(\theta))$
(51)

holds for any $\theta,\theta^{\prime}\in{\cal M}$.

For example, Condition (B2) holds in the case of classical and quantum channel
coding, as explained later. That is, when the exponential family ${\cal E}$ is
given as the product of two exponential families ${\cal E}_{1}$ and ${\cal
E}_{2}$, and there is a data processing between the mixture family ${\cal M}$
and the exponential family ${\cal E}_{1}$, Condition (B2) is satisfied.

In the following, we restrict the domain of $e$\- and $m$\- projections into
${\cal M}$ and ${\cal E}$. We use the notations:

$\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal
M}}:=\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal M}}|_{{\cal
E}},\quad\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal
E}}:=\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}|_{{\cal M}}.$ (52)

Then, we have the following theorem, which is proven in Appendix A.

###### Theorem 4.1

Assume that the conditions (B1) and (B2) hold, the initial point
$\theta^{(1)}\in{\cal M}$ satisfies the relation
$\sup_{\theta\in\mathcal{M}}D^{F}(\theta\|\theta^{(1)})<\infty$, and its
inverse map $(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}})^{-1}$ exists.
Then, the quantity
$D^{F}\big{(}\theta^{(t)}\big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)})\big{)}$ converges to the supremum
$C_{\sup}(\mathcal{M},\mathcal{E})$ with the speed

$\displaystyle
C_{\sup}(\mathcal{M},\mathcal{E})-D^{F}\big{(}\theta^{(t)}\big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)})\big{)}=o(\frac{1}{t}).$ (53)

That is, the convergence point achieves the maximum in (47). Further, when
$t\geq\frac{\sup_{\theta\in\mathcal{M}}D^{F}(\theta\|\theta^{(1)})}{\epsilon}$,
the parameter $\theta^{(t)}$ satisfies

$\displaystyle
C_{\sup}(\mathcal{M},\mathcal{E})-D^{F}\big{(}\theta^{(t)}\big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)})\big{)}\leq\epsilon.$ (54)

###### Lemma 9

When the set $\Theta^{*}(\mathcal{M},\mathcal{E})$ is not empty, it is a
mixture subfamily.

As a strengthened version of (B2), we introduce the following condition for
$\mathcal{M}$, $\mathcal{E}$, and $\theta^{\prime}\in\mathcal{M}$;

(B2+)

The maximizer $\theta^{*}=\theta^{*}(\mathcal{M},\mathcal{E})$ exists. There
exists a constant $\alpha(\theta^{\prime})>0$ such that the relation

$\displaystyle(1+\alpha(\theta^{\prime}))D^{F}(\theta^{*}\|\theta)\leq
D^{F}(\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{*})\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}(\theta))$ (55)

holds when an element $\theta\in{\cal M}$ satisfies the condition
$D^{F}(\theta^{*}\|\theta)\leq D^{F}(\theta^{*}\|\theta^{\prime})$.

When the condition (B2+) holds, we have a better evaluation.

###### Theorem 4.2

Assume that the conditions (B1) and (B2+) hold for $\mathcal{M}$,
$\mathcal{E}$, and $\theta^{\prime}\in\mathcal{M}$, and there exists its
inverse map $(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}})^{-1}$. Then,
the quantity
$D^{F}\big{(}\theta^{(t)}\big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)})\big{)}$ converges to the supremum
$C_{\sup}(\mathcal{M},\mathcal{E})$ with the speed

$\displaystyle
C_{\sup}(\mathcal{M},\mathcal{E})-D^{F}\big{(}\theta^{(t)}\big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)})\big{)}\leq(1+\alpha(\theta^{(1)}))^{-t+1}D^{F}(\theta^{*}\|\theta^{(1)}).$
(56)

Further, when $t-1\geq\frac{\log
D^{F}(\theta^{*}\|\theta^{(1)})-\log\epsilon}{\log(1+\alpha(\theta^{(1)}))}$,
the parameter $\theta^{(t)}$ satisfies

$\displaystyle
C_{\sup}(\mathcal{M},\mathcal{E})-D^{F}\big{(}\theta^{(t)}\big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)})\big{)}\leq\epsilon.$ (57)

Theorem 4.2 is proven in Appendix B. Here, we consider the case
$\alpha(\theta^{(1)})$ can be chosen as a non-negligible value when
$\theta^{(1)}$ is close to $\theta^{*}(\mathcal{M},\mathcal{E})$. In this
case, the convergence speed in (56) increases when $t$ is larger.

###  4.3 Algorithm based on minimization under mixture parameter

In the rest of this paper, we use the subscript
$\mathsf{a},\mathsf{b},\mathsf{c},\mathsf{d},\mathsf{e}$ to express elements
of $\mathbb{R}^{k}$, $\mathbb{R}^{l-k}$, $\mathbb{R}^{l}$, $\mathbb{R}^{d-k}$,
$\mathbb{R}^{l-2k}$, respectively, as Table 2.

Table 2: Summary of subscripts

Subscript | $\mathsf{a}$ | $\mathsf{b}$ | $\mathsf{c}$ | $\mathsf{d}$ | $\mathsf{e}$
---|---|---|---|---|---
Vector space | $\mathbb{R}^{k}$ | $\mathbb{R}^{l-k}$ | $\mathbb{R}^{l}$ | $\mathbb{R}^{d-k}$ | $\mathbb{R}^{l-2k}$
Examples | $\Theta_{{\cal M}}$ | $\Theta_{{\cal E},\mathsf{b}},\Theta_{{\cal E},\mathsf{b}}$ | $\Theta_{{\cal E}}$ |  |
$\Theta_{{\cal E},\mathsf{a}},\Theta_{{\cal E},\mathsf{a}}$ |  |

In this paper, there are many types of vector spaces. An element of each
vector space has a subscript to identify the vector space. This table shows
the relation between the vector space and the subscript.

To handle these maps, we employ natural parameters and mixture parameters. We
use the following notions.

$\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to\Xi_{\cal M}}$
$\displaystyle:=(\psi_{{\cal
M}}^{(m)})^{-1}\circ\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal M}}$
(58) $\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to\Theta_{\cal
M}}$ $\displaystyle:=(\psi_{{\cal
M}}^{(e)})^{-1}\circ\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal M}}$
(59) $\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{\Xi_{\cal E}\to{\cal M}}$
$\displaystyle:=\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal
M}}\circ\psi_{{\cal E}}^{(m)}$ (60)
$\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{\Xi_{\cal E}\to\Xi_{\cal M}}$
$\displaystyle:=(\psi_{{\cal
M}}^{(m)})^{-1}\circ\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal
M}}\circ\psi_{{\cal E}}^{(m)}$ (61)
$\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{\Xi_{\cal E}\to\Theta_{\cal
M}}$ $\displaystyle:=(\psi_{{\cal
M}}^{(e)})^{-1}\circ\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to{\cal
M}}\circ\psi_{{\cal E}}^{(m)}.$ (62)

In the same way, we define the maps
$\mathop{\Gamma}\nolimits^{(e),F}_{\Theta_{\cal E}\to{\cal M}}$,
$\mathop{\Gamma}\nolimits^{(e),F}_{\Theta_{\cal E}\to\Xi_{\cal M}}$,
$\mathop{\Gamma}\nolimits^{(e),F}_{\Theta_{\cal E}\to\Theta_{\cal M}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to\Xi_{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to\Theta_{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal M}\to{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal M}\to\Xi_{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal M}\to\Theta_{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{\Theta_{\cal M}\to{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{\Theta_{\cal M}\to\Xi_{\cal E}}$,
$\mathop{\Gamma}\nolimits^{(m),F}_{\Theta_{\cal M}\to\Theta_{\cal E}}$.

To characterize $e$\- and $m$-projections, we introduce the following
condition, which is also useful for the characterization of the inverse map of
the map $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$.

(B3)

Let $u_{1},\ldots,u_{d}$ be a basis of $\mathbb{R}^{d}$. $v_{1},\ldots,v_{l}$
are linearly independent vectors in $\mathbb{R}^{d}$. Let
$\mathcal{E}\subset\Theta$ be an exponential subfamily generated by $l$
vectors $v_{1},\ldots,v_{l}\in\mathbb{R}^{d}$ at $\theta_{0}\in\Theta$, and
$\mathcal{M}\subset\Theta$ be the mixture subfamily generated by the
constraint $\sum_{i=1}^{d}u^{i}_{k+j}\partial_{i}F(\theta)=0$ for
$j=1,\ldots,d-k$ with $k\leq l$. Also, $\mathcal{M}\subset\Theta$ is an
exponential subfamily generated by $u_{1},\ldots,u_{k}\in\mathbb{R}^{d}$. That
is, there exists
$\theta_{\mathsf{d}}^{*}=(\theta^{k+1,*},\ldots,\theta^{d,*})$ such that
$\mathcal{M}=\\{(\theta_{\mathsf{a}},\theta_{\mathsf{d}}^{*})|\theta\in\mathbb{R}^{k}\\}\cap\Theta$.

When the condition (B3) holds, for $\theta\in\mathcal{M}$, we denote its
natural parameter and its mixture parameter by
$\hat{\theta}_{\mathsf{a}}(\theta)\in\Theta_{\mathcal{M}}$ and
$\hat{\eta}_{\mathsf{a}}(\theta)\in\Xi_{\mathcal{M}}$, respectively.
Therefore, we use the notation
$\hat{\theta}_{\mathsf{a}}^{(t)}:=\hat{\theta}_{\mathsf{a}}(\theta^{(t)})\in\Theta_{\mathcal{M}}$
to identify an element in $\mathcal{M}$ instead of $\theta^{(t)}$. Then, we
define the $d\times d$ matrix $U$ and the $d\times l$ matrix $V$ as
$U=(u_{1},\ldots,u_{d})$ and $V=(v_{1},\ldots,v_{l})$, and define the $k\times
l$ matrix $V_{1}$ and the $(d-k)\times l$ matrix $V_{2}$ as
$\left(\begin{array}[]{c}V_{1}\\\ V_{2}\end{array}\right)=VU^{-1}$. Condition
(B3) brings the following useful characterization of $e$\- and
$m$-projections.

###### Lemma 10

Assume Condition (B3). For $\eta_{\mathsf{a}}\in\Xi_{\mathcal{M}}$, we have

$\displaystyle\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{{\cal M}}\to\Xi_{\cal
E}}(\eta_{\mathsf{a}})=\eta_{\mathsf{a}}V_{1}.$ (63)

###### Lemma 11

Assume Condition (B3). The following conditions for elements
$\eta_{\mathsf{a}}\in\Xi_{\mathcal{M}}$ and
$\theta_{\mathsf{a}}\in\Theta_{\mathcal{M}}$ are equivalent.

(i)

$\mathop{\Gamma}\nolimits^{(e),F}_{\Xi_{{\cal E}}\to\Theta_{\cal
M}}(\eta_{\mathsf{a}}V_{1})=\theta_{\mathsf{a}}$.

(ii)

The element $\psi_{\mathcal{E}}^{(m)}(\eta_{\mathsf{a}}V_{1})\in\mathcal{E}$
belongs to the exponential subfamily
$\psi_{\mathcal{E}}^{(e)}(\\{\theta_{\mathsf{c}}\in\Theta_{\mathcal{E}}|\theta_{\mathsf{a}}=V_{1}\theta_{\mathsf{c}}\\})$.

(iii)

The following relation holds.

$\displaystyle\theta_{\mathsf{a}}=V_{1}\nabla^{(m)}[F_{\mathcal{E}}^{*}](\eta_{\mathsf{a}}V_{1})=\nabla^{(m)}[F_{\mathcal{E}}^{*}\circ
R[V_{1}]](\eta_{\mathsf{a}}).$ (64)

Here, the second equation always holds.

(iv)

The following relation holds.

$\displaystyle\eta_{\mathsf{a}}=\nabla^{(e)}[(F_{\mathcal{E}}^{*}\circ
R[V_{1}])^{*}](\theta_{\mathsf{a}}).$ (65)

(v)

The following relation holds.

$\displaystyle\eta_{\mathsf{a}}$ $\displaystyle=\mathop{\rm
argmin}\limits_{\eta_{\mathsf{a}}^{\prime}\in\mathbb{R}^{k}}F_{\mathcal{E}}^{*}(\eta_{\mathsf{a}}^{\prime}V_{1})-\langle\eta_{1}^{\prime},\theta_{\mathsf{a}}\rangle.$
(66)

The proofs of the above lemmas are given in Appendix C.

These lemmas give the following meaning of Condition (B3), which assumes that
the mixture family ${\cal M}$ has the structure of an exponential family. Due
to Lemma 10, a mixture parameter $\eta_{\mathsf{a}}$ in ${\cal E}$ is mapped
to the mixture parameter $\eta_{\mathsf{a}}V_{1}$ in ${\cal M}$ by multiplying
the matrix $V_{1}$, which also characterizes the $m$-projection. Due to (iii)
of Lemma 11, a natural parameter $\theta_{\mathsf{c}}$ in ${\cal E}$ is mapped
to the natural parameter $V_{1}\theta_{\mathsf{c}}$in ${\cal M}$ by
multiplying the matrix $V_{1}$. This map also characterizes the $m$-projection
when $\theta_{\mathsf{c}}$ is
$\nabla^{(m)}[F_{\mathcal{E}}^{*}](\eta_{\mathsf{a}}V_{1})$. These mappings
take a central role in the latter discussion.

In addition, the equivalence between (i) and (iii) in Lemma 11 implies

$\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{\Xi_{\cal E}\to\Theta_{\cal
M}}(\eta_{\mathsf{a}}V_{1})=V_{1}\nabla^{(m)}[F_{\mathcal{E}}^{*}](\eta_{\mathsf{a}}V_{1}).$
(67)

Combining (63) of Lemma 10, we have

$\displaystyle\mathop{\Gamma}\nolimits^{(e),F}_{{\cal E}\to\Theta_{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal M}\to{\cal
E}}(\eta_{\mathsf{a}})=\mathop{\Gamma}\nolimits^{(e),F}_{\Xi_{\cal
E}\to\Theta_{\cal M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal
M}\to\Xi_{\cal
E}}(\eta_{\mathsf{a}})=V_{1}\nabla^{(m)}[F_{\mathcal{E}}^{*}](\eta_{\mathsf{a}}V_{1}).$
(68)

The following theorem characterizes the inverse map of
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$.

###### Theorem 4.3

When the condition (B3) holds, we have the following two statements; (i) The
map $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$ has a unique
inverse map $\nabla^{(m)}[F_{\cal M}^{*}]\circ\nabla^{(e)}[(F_{\cal
E}^{*}\circ R[V_{1}])^{*}]$ under the natural parameter of ${\cal M}$. (ii) In
addition, for $\hat{\theta}_{\mathsf{a}}\in\Theta_{{\cal
M}}\subset\mathbb{R}^{k}$, we have

$\displaystyle\nabla^{(e)}[(F_{\cal E}^{*}\circ
R[V_{1}])^{*}](\hat{\theta}_{\mathsf{a}})=$ $\displaystyle\mathop{\rm
argmin}\limits_{\hat{\eta}_{\mathsf{a}}\in\mathbb{R}^{k}}F_{{\cal
E}}^{*}(\hat{\eta}_{\mathsf{a}}V_{1})-\langle\hat{\eta}_{\mathsf{a}},\hat{\theta}\rangle.$
(69)

Theorem 4.3 is proven in Appendix D.

Therefore, when the conditions (B1) and (B3) hold, our algorithm is given as
Algorithm 2, which is based on the minimization under the mixture parameter
$\hat{\eta}$. Further, when the condition (B2) holds additionally, and we set
$\hat{\theta}^{(0)}$ as an arbitrary element in $\Theta_{\cal M}$ and update
it as the rule $\hat{\theta}^{(t+1)}:=\nabla^{(m)}[F_{\cal
M}^{*}]\circ\nabla^{(e)}[(F_{\cal E}^{*}\circ
R[V_{1}])^{*}](\hat{\theta}^{(t)})$, then we obtain the maximum value
$C_{\sup}(\mathcal{M},\mathcal{E})$ as the limit of $D^{F}\Big{(}\psi_{\cal
M}^{(e)}(\hat{\theta}^{(t)})\Big{\|}\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}\big{(}\psi_{\cal M}^{(e)}(\hat{\theta}^{(t)})\big{)}\Big{)}$.

Algorithm 2 Reverse em-algorithm with mixture parameter under conditions (B1)
and (B3)

Choose the initial value
$\hat{\theta}^{(1)}_{\mathsf{a}}\in\Theta_{\mathcal{M}}\subset\mathbb{R}^{k}$;

repeat

Calculate $\hat{\eta}^{(t+1)}_{\mathsf{a}}:=\mathop{\rm
argmin}\limits_{\hat{\eta}\in\mathbb{R}^{k}}F_{{\cal
E}}^{*}(\hat{\eta}_{\mathsf{a}}V_{1})-\langle\hat{\eta}_{\mathsf{a}},\hat{\theta}_{\mathsf{a}}^{(t)}\rangle$;

Calculate $\hat{\theta}_{\mathsf{a}}^{(t+1)}:=\nabla^{(m)}[F_{\cal
M}^{*}](\hat{\eta}_{\mathsf{a}}^{(t+1)})\in\Theta_{\mathcal{M}}\subset\mathbb{R}^{k}$;

until convergence.

Further, we have the following corollary of Theorems 4.1 and 4.3.

###### Corollary 1

Assume that the conditions (B1), (B2), and (B3) hold. An invariant point of
the map $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$, i.e., an
invariant point of the inverse map $(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}})^{-1}$, is a
maximizer in (46). Hence, no minimizer exists in (46).

###### Proof

Theorem 4.3 guarantees the existence of the inverse map
$(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}})^{-1}$.
Applying Algorithm 2 by setting an invariant point is the initial point, we
find that it is the global maximizer because Theorem 4.1 guarantees that the
algorithm asymptotically achieves the global maximum.

Since a minimizer in (46) is also an invariant point, no minimizer exists in
(46).

###### Remark 1

The proof technique of Theorem 4.1 is inspired by the proof of (Shoji, ,
Theorem 11). In contrast, Theorem 4.2 employs a different technique, which is
close to (RISB, , Eq. (25)).

###  4.4 Algorithm with approximate minimization

However, the minimization
$\min_{\hat{\eta}_{\mathsf{a}}\in\mathbb{R}^{k}}F_{{\cal
E}}^{*}(\hat{\eta}_{\mathsf{a}}V_{1})-\langle\hat{\eta}_{\mathsf{a}},\hat{\theta}_{\mathsf{a}}^{(t)}\rangle$
cannot be solved perfectly in general. That is, it can be solved only
approximately. Hence, we propose an alternative algorithm, Algorithm 3, by
replacing the minimization by $\epsilon$-approximation. To evaluate the error
of Algorithm 3, we have Theorem 4.4.

Algorithm 3 Reverse em-algorithm with $\epsilon$ approximation under mixture
parameter under conditions (B1) and (B3)

Choose the initial value
$\hat{\theta}_{\mathsf{a}}^{(1)}\in\Theta_{\mathcal{M}}\subset\mathbb{R}^{k}$;

repeat

Choose an element $\hat{\eta}_{\mathsf{a}}^{(t+1)}\in\mathbb{R}^{k}$ such that
$\displaystyle F_{{\cal
E}}^{*}(\hat{\eta}_{\mathsf{a}}^{(t+1)}V_{1})-\langle\hat{\eta}_{\mathsf{a}}^{(t+1)},\hat{\theta}_{\mathsf{a}}^{(t)}\rangle\leq\min_{\hat{\eta}_{\mathsf{a}}\in\mathbb{R}^{k}}F_{{\cal
E}}^{*}(\hat{\eta}_{\mathsf{a}}V_{1})-\langle\hat{\eta}_{\mathsf{a}},\hat{\theta}_{\mathsf{a}}^{(t)}\rangle+\epsilon;$
(70)

Calculate $\hat{\theta}_{\mathsf{a}}^{(t+1)}:=\nabla^{(m)}[F_{\cal
M}^{*}](\hat{\eta}_{\mathsf{a}}^{(t+1)})\in\Theta_{\mathcal{M}}\subset\mathbb{R}^{k}$;

until $t=t_{1}-1$.

final step: We output the final estimate
$\hat{\theta}_{{\mathsf{a}},f}^{(t_{1})}:=\hat{\theta}_{\mathsf{a}}^{(t_{2})}\in\Theta_{\mathcal{M}}$
by using $t_{2}:=\mathop{\rm
argmin}\limits_{t=2,\ldots,t_{1}}D^{F}(\theta^{(t)}\|\theta_{(t)})$, where
$\theta_{(t)}:=\psi_{\mathcal{M}}^{(e)}(\theta_{\mathsf{a}}^{(t)})$ and
$\theta^{(t)}:=\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}(\theta_{(t)})$.

###### Theorem 4.4

Assume that the conditions (B1), (B2) and (B3) hold for a pair of a
$k$-dimensional mixture subfamily $\mathcal{M}$ and an $l$-dimensional
exponential subfamily $\mathcal{E}$ and the maximizer
$\theta^{*}:=\theta^{*}(\mathcal{M},\mathcal{E})$ in (49) exists. We define
the set
$\mathcal{M}_{0}:=\\{\theta\in\mathcal{M}|D^{F}(\theta^{*}\|\theta)\leq
D^{F}(\theta^{*}\|\theta^{(1)})\\}\subset\mathcal{M}$. Then, in Algorithm 3,
the quantity $D^{F}(\theta^{(t)}\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{(t)}))$ converges to the minimum
$C_{\sup}(\mathcal{M},\mathcal{E})$ with the speed

$\displaystyle
C_{\sup}(\mathcal{M},\mathcal{E})-D^{F}(\theta_{f}^{(t_{1})}\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta_{f}^{(t_{1})}))$ $\displaystyle\leq$
$\displaystyle\max\Big{(}\frac{D^{F}(\theta^{*}\|\theta^{(1)})}{t_{1}-1}+2\gamma\sqrt{D^{F}(\theta^{*}\|\theta^{(1)})\epsilon}+(\gamma+1)\epsilon,2\gamma\sqrt{D^{F}(\theta^{*}\|\theta^{(1)})\epsilon}+(\gamma+1)\epsilon\Big{)},$
(71)

where $\gamma:=\gamma(\mathcal{M}_{0}|\mathcal{M})$. Further, when
$t_{1}-1\geq\frac{2D^{F}(\theta^{*}\|\theta^{(1)})}{\epsilon^{\prime}}$ and
$\epsilon\leq\frac{{\epsilon^{\prime}}^{2}}{4(3\gamma+1)^{2}{D^{F}(\theta^{*}\|\theta^{(1)})}}$,
the parameter $\theta_{f}^{(t_{1})}$ satisfies

$\displaystyle
C_{\sup}(\mathcal{M},\mathcal{E})-D^{F}(\theta_{f}^{(t_{1})}\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta_{f}^{(t_{1})}))\leq\epsilon^{\prime}.$ (72)

Theorem 4.4 is proven in Appendix E.

###  4.5 Algorithm based on quadratic approximation

Now, we apply the quadratic approximation in the minimization in Algorithm 2.
We define $\bar{\eta}_{\mathsf{a}}\in\mathbb{R}^{k}$ and
$\bar{\theta}_{\mathsf{c}}\in\mathbb{R}^{l}$ as

$\displaystyle\bar{\eta}_{\mathsf{a}}=\nabla^{(e)}[F_{{\cal
M}}](\hat{\theta}_{\mathsf{a}}),\quad\bar{\eta}_{\mathsf{a}}V_{1}=\nabla^{(e)}[F_{{\cal
E}}](\bar{\theta}_{\mathsf{c}}),~{}(\hbox{i.e.,}~{}\bar{\theta}_{\mathsf{c}}=\nabla^{(m)}[F_{{\cal
E}}^{*}](\bar{\eta}_{\mathsf{a}}V_{1})).$ (73)

Then, we have

$\displaystyle F_{{\cal E}}^{*}(\hat{\eta}_{\mathsf{a}}V_{1})$
$\displaystyle\cong$ $\displaystyle F_{{\cal
E}}^{*}(\bar{\eta}_{\mathsf{a}}V_{1})+(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})V_{1}\nabla^{(m)}[F_{{\cal
E}}^{*}](\bar{\eta}_{\mathsf{a}}V_{1})$
$\displaystyle+\frac{1}{2}(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})V_{1}(J[F_{{\cal
E}}^{*}](\bar{\eta}_{\mathsf{a}}V_{1}))V_{1}^{T}(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})^{T}$
$\displaystyle=$ $\displaystyle F_{{\cal
E}}^{*}(\bar{\eta}_{\mathsf{a}}V_{1})+(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})V_{1}\bar{\theta}_{\mathsf{c}}+\frac{1}{2}(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})D^{F}(\bar{\theta}_{\mathsf{c}})(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})^{T},$
(74)

where

$\displaystyle D(\bar{\theta}_{\mathsf{c}}):=V_{1}(J[F_{{\cal
E}}^{*}](\bar{\eta}_{\mathsf{a}}V_{1}))V_{1}^{T}=V_{1}(J[F_{{\cal
E}}](\bar{\theta}_{\mathsf{c}}))^{-1}V_{1}^{T}.$ (75)

Hence, we have

$\displaystyle F_{{\cal
E}}^{*}(\hat{\eta}_{\mathsf{a}}V_{1})-\langle\hat{\eta}_{\mathsf{a}},\hat{\theta}_{\mathsf{c}}^{(t)}\rangle$
$\displaystyle\cong$ $\displaystyle F_{{\cal
E}}^{*}(\bar{\eta}_{\mathsf{a}}V_{1})-\langle\bar{\eta}_{\mathsf{a}},\hat{\theta}_{\mathsf{a}}^{(t)}\rangle+(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})(V_{1}\bar{\theta}_{\mathsf{c}}-\hat{\theta}_{\mathsf{a}})+\frac{1}{2}(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})D(\bar{\theta}_{\mathsf{c}})(\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}})^{T}$
$\displaystyle=$ $\displaystyle F_{{\cal
E}}^{*}(\bar{\eta}_{\mathsf{a}}V_{1})-\langle\bar{\eta}_{\mathsf{a}},\hat{\theta}_{\mathsf{a}}^{(t)}\rangle$
$\displaystyle+\frac{1}{2}\big{(}\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}}-D(\bar{\theta}_{\mathsf{c}})^{-1}(V_{1}\bar{\theta}_{\mathsf{c}}-\hat{\theta}_{\mathsf{a}})\big{)}D(\bar{\theta}_{\mathsf{c}})\big{(}\hat{\eta}_{\mathsf{a}}-\bar{\eta}_{\mathsf{a}}-D(\bar{\theta}_{\mathsf{c}})^{-1}(V_{1}\bar{\theta}_{\mathsf{c}}-\hat{\theta}_{\mathsf{a}})\big{)}^{T}.$
(76)

The minimum in Algorithm 2 is approximately achieved when

$\displaystyle\hat{\eta}_{\mathsf{a}}=\bar{\eta}_{\mathsf{a}}+D(\bar{\theta}_{\mathsf{c}})^{-1}(V_{1}\bar{\theta}_{\mathsf{c}}-\hat{\theta}_{\mathsf{a}}).$
(77)

This approximation is effective when $\hat{\theta}_{\mathsf{a}}$ is close to
the minimizer $\theta^{*}$.

###  4.6 Algorithm based on minimization under natural parameter

The above algorithms are based on the mixture parameter of $\mathcal{E}$ for
the calculation of $\nabla^{(e)}[(F_{\cal E}^{*}\circ R[V_{1}])^{*}]$. To make
an alternative algorithm based on the natural parameter of $\mathcal{E}$, we
introduce additional conditions.

(B4)

The $k\times l$ matrix $V_{1}$ has the following form; $V_{1}=(I,V_{3})$ with
a $k\times(l-k)$ matrix $V_{3}$.

(B5)

The relation
$\Theta_{\mathcal{E}}=\Theta_{\mathcal{E},\mathsf{a}}\times\Theta_{\mathcal{E},\mathsf{b}}$
holds with $\Theta_{\mathcal{E},\mathsf{a}}=\mathbb{R}^{k}$ and
$\Theta_{\mathcal{E},\mathsf{b}}=\mathbb{R}^{l-k}$. $F_{\cal E}$ has the
following form; $F_{\cal E}(\theta_{\mathsf{a}},\theta_{\mathsf{b}})=F_{{\cal
E},\mathsf{a}}(\theta_{\mathsf{a}})+F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}})$ with
$(\theta_{\mathsf{a}},\theta_{\mathsf{b}})\in\Theta_{\mathcal{E}}$.

The meaning of Conditions (B4) and (B5) are the following. Condition (B5)
means that the exponential family is given as the product of two exponential
families ${\cal E}_{\mathsf{a}}$ and ${\cal E}_{\mathsf{b}}$. Condition (B3)
gives a linear map from a natural parameter in ${\cal M}$ to a natural
parameter in ${\cal E}$ and a linear map from a mixture parameter in ${\cal
E}$ to a mixture parameter in ${\cal M}$ via $V_{1}$. When Condition (B4)
holds, the above linear maps can be simplified.

Then, we have the following theorem.

###### Theorem 4.5

When the conditions (B3) and (B4) hold, for $\hat{\theta}\in\Theta_{{\cal
M}}\subset\mathbb{R}^{k}$, we have

$\displaystyle\nabla^{(e)}[(F_{\cal E}^{*}\circ R[V_{1}])^{*}](\hat{\theta})=$
$\displaystyle\nabla^{(e)}[F_{\cal
E}](\bar{\theta})\left(\begin{array}[]{c}I_{k}\\\ 0\end{array}\right),$ (80)

where
$\bar{\theta}_{\mathsf{c}}:=(\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}),\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}))^{T}$
and $\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}):=\mathop{\rm
argmin}\limits_{\theta_{\mathsf{b}}\in\mathbb{R}^{l-k}}F_{{\cal
E}}(\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}},\theta_{\mathsf{b}})$.

Theorem 4.5 is proven in Appendix F.

Additionally, when the condition (B5) holds, we can use the following
corollary.

###### Corollary 2

When conditions (B3), (B4), and (B5) hold, for
$\hat{\theta}_{\mathsf{a}}\in\Theta_{{\cal M}}\subset\mathbb{R}^{k}$, we have

$\displaystyle\nabla^{(e)}[(F_{\cal E}^{*}\circ
R[V_{1}])^{*}](\hat{\theta}_{\mathsf{a}})=$
$\displaystyle\nabla^{(e)}[F_{{\cal
E},1}](\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}})),$
(81)

where $\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}):=\mathop{\rm
argmin}\limits_{\theta_{\mathsf{b}}\in\mathbb{R}^{l-k}}F_{{\cal
E},\mathsf{a}}(\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}})+F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}})$.

Therefore, thanks to Theorem 4.5, Corollary 2, and (i) of Theorem 4.3, we can
use Algorithm 4 to calculate $\hat{\theta}_{\mathsf{a}}^{(t+1)}$ from
$\hat{\theta}_{\mathsf{a}}^{(t)}$ instead of Algorithm 2. To implement
Algorithm 4, we need to calculate the minimization

$\displaystyle\min_{\theta_{\mathsf{b}}\in\mathbb{R}^{l-k}}F_{{\cal
E}}(\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}},\theta_{\mathsf{b}}).$
(82)

The merit of our method is determined by whether the minimization (82) is
easier than the original maximization (47). Since $F_{{\cal E}}$ is a convex
function, the minimization (82) can be solved by the convex optimization.
However, there is a case that the maximization (47) is also given as the
minimization of a concave function. Hence, this type of comparison depends on
the target problem.

Algorithm 4 Reverse em-algorithm with natural parameter under conditions (B1),
(B3), and (B4)

Choose the initial value
$\hat{\theta}_{\mathsf{a}}^{(1)}\in\Theta_{\mathcal{M}}\subset\mathbb{R}^{k}$;

repeat

Set
$\hat{\theta}_{\mathsf{a}}=\hat{\theta}_{\mathsf{a}}^{(t)}\in\Theta_{\mathcal{M}}$;

Calculate $\bar{\theta}_{\mathsf{b}}^{*}(\hat{\theta}):=\mathop{\rm
argmin}\limits_{\theta_{\mathsf{b}}\in\mathbb{R}^{l-k}}F_{{\cal
E}}(\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}},\theta_{\mathsf{b}})$
and
$\bar{\theta}_{\mathsf{a}}:=(\hat{\theta}_{\mathsf{a}}-V_{3}\bar{\theta}_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}),\bar{\theta}_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}))^{T}$;

Calculate $\hat{\theta}_{\mathsf{a}}^{(t+1)}:=\nabla^{(m)}[F_{\cal
M}^{*}]\left(\nabla^{(e)}[F_{\cal
E}](\bar{\theta}_{\mathsf{a}})\left(\begin{array}[]{c}I_{k}\\\
0\end{array}\right)\right)\in\mathbb{R}^{k}$;

until convergence.

When the condition (B5) holds additionally, the calculation of
$\hat{\theta}_{\mathsf{a}}^{(t+1)}$ can be simplified as
$\hat{\theta}_{\mathsf{a}}^{(t+1)}:=\nabla^{(m)}[F_{\cal
M}^{*}]\left(\nabla^{(e)}[F_{{\cal
E},\mathsf{a}}](\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}))\right)$
with $\theta_{\mathsf{b}}^{*}(\hat{\theta}_{\mathsf{a}}):=\mathop{\rm
argmin}\limits_{\theta_{\mathsf{b}}\in\mathbb{R}^{l-k}}F_{{\cal
E},\mathsf{a}}(\hat{\theta}_{\mathsf{a}}-V_{3}\theta_{\mathsf{b}})+F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}})$.

###  4.7 Conversion to em-problem

Next, we convert the reverse em-problem (47) to the em-problem (46). We focus
on the fixed point in Algorithm 2. Theorem 4.1 guarantees that the convergence
point is the maximizer of the maximization (47). Since the fixed point equals
the convergence point, the fixed point is the maximizer of the maximization
(47). Therefore, characterizing the fixed point by Theorem 4.3, we have the
following theorem.

###### Theorem 4.6

Assume Conditions (B1) and (B3). Then, the following three conditions for
$\theta_{\mathsf{a}}\in\Theta_{{\cal M}}$ are equivalent.

(D1)

$\theta_{\mathsf{a}}\in\Theta_{{\cal M}}$ is an invariant point of the map
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$, i.e., an
invariant point of the inverse map $(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}})^{-1}$.

(D2)

The relation $V_{1}\nabla^{(m)}[F_{\cal E}^{*}](\nabla^{(e)}[F_{\cal
M}](\theta_{\mathsf{a}})V_{1})=\theta$ holds.

(D3)

The mixture parameter $\eta_{\mathsf{a}}=\nabla^{(e)}[F_{\cal
M}](\theta_{\mathsf{a}})$ satisfies

$\displaystyle V_{1}\nabla^{(m)}[F_{\cal
E}^{*}](\eta_{\mathsf{a}}V_{1})=\nabla^{(m)}[F_{\cal
M}^{*}](\eta_{\mathsf{a}}).$ (83)

When Condition (B2) holds in addition to (B1) and (B3), the following two
conditions for the pair of ${\cal E}$ and ${\cal M}$ are equivalent.

(D4)

There exists an element $\theta_{\mathsf{a}}\in\Theta_{{\cal M}}$ to satisfy
the condition (D1), (D2), or (D3).

(D5)

The set $\Theta^{*}(\mathcal{M},\mathcal{E})$ is not empty.

###### Proof

First, we show the equivalence among (D1), (D2), and (D3). When
$\theta_{\mathsf{a}}$ satisfies Condition (D1), $\theta_{\mathsf{a}}$ is a
fixed point for the iteration given in Theorem 4.3, which is equivalent to the
condition:

$\displaystyle\nabla^{(m)}[F_{\cal M}^{*}]\circ\nabla^{(e)}[(F_{\cal
E}^{*}\circ R[V_{1}])^{*}](\theta_{\mathsf{a}})=\theta_{\mathsf{a}}.$ (84)

We choose the mixture parameter $\eta_{\mathsf{a}}=\nabla^{(e)}[F_{\cal
M}](\theta_{\mathsf{a}})$, which implies

$\displaystyle\nabla^{(m)}[F_{\cal
M}^{*}](\eta_{\mathsf{a}})=\theta_{\mathsf{a}}.$ (85)

Hence, the condition (84) is equivalent to

$\displaystyle\nabla^{(e)}[(F_{\cal E}^{*}\circ
R[V_{1}])^{*}](\theta_{\mathsf{a}})=\eta_{\mathsf{a}}.$ (86)

Due to (69), the condition (86) is equivalent to

$\displaystyle V_{1}\nabla^{(m)}[F_{\cal
E}^{*}](\eta_{\mathsf{a}}V_{1})=\theta_{\mathsf{a}}.$ (87)

The combination of (85) and (87) implies the equivalence between (D1) and
(D3). Also, substituting $\nabla^{(e)}[F_{\cal M}](\theta_{\mathsf{a}})$ into
$\eta_{\mathsf{a}}$ at (87), we obtain the equivalence between (D1) and (D2).

Under Conditions (B1), (B2), and (B3), Corollary 1 guarantees that an
invariant point is limited to an element of the set
$\Theta^{*}(\mathcal{M},\mathcal{E})$. Hence, we obtain the equivalence
between (D4) and (D5) for $\theta_{\mathsf{a}}\in\Theta_{{\cal M}}$.

We define the exponential family $\Theta_{{\cal M},{\cal E}}:=\Theta_{{\cal
M}}\times\Theta_{{\cal E}}$ with the potential function $F_{{\cal M},{\cal
E}}((\theta_{\mathsf{a}},\theta_{\mathsf{c}})^{T}):=F_{{\cal
M}}(\theta_{\mathsf{a}})+F_{{\cal E}}(\theta_{\mathsf{c}})$. This exponential
family has the mixture parameter $(\eta_{\mathsf{a}},\eta_{\mathsf{c}})$ as

$\displaystyle\nabla^{(e)}[F_{{\cal M},{\cal E}}]=(\nabla^{(e)}[F_{{\cal
M}}],\nabla^{(e)}[F_{{\cal E}}]).$ (88)

We define the mixture subfamily $\hat{\cal M}$ and the exponential subfamily
$\hat{\cal E}$ as

$\displaystyle\hat{\cal M}:=$
$\displaystyle\left\\{\left(\begin{array}[]{c}\theta_{\mathsf{a}}\\\
\theta_{\mathsf{c}}\end{array}\right)\left|(\eta_{\mathsf{a}},\eta_{\mathsf{c}})=\nabla^{(e)}[F_{{\cal
M},{\cal E}}]\left(\begin{array}[]{c}\theta_{\mathsf{a}}\\\
\theta_{\mathsf{c}}\end{array}\right),~{}(\eta_{\mathsf{a}},\eta_{\mathsf{c}})\left(\begin{array}[]{c}V_{1}\\\
-I\end{array}\right)=0\right.\right\\}$ (95) $\displaystyle\hat{\cal E}:=$
$\displaystyle\left\\{\left.\left(\begin{array}[]{c}\theta_{\mathsf{a}}\\\
\theta_{\mathsf{c}}\end{array}\right)\right|V_{1}\theta_{\mathsf{c}}=\theta_{\mathsf{a}}\right\\}=\left\\{\left(\begin{array}[]{c}V_{1}\theta_{\mathsf{c}}\\\
\theta_{\mathsf{c}}\end{array}\right)\right\\}=\left\\{\left(\begin{array}[]{c}V_{1}\\\
I\end{array}\right)\theta_{\mathsf{c}}\right\\}.$ (102)

By using $\theta_{\mathsf{c}}=\nabla^{(m)}[F_{\cal
E}^{*}](\eta_{\mathsf{a}}V_{1})\in\Theta_{{\cal E}}$, (D3) of Theorem 4.6 is
rewritten as

$\displaystyle\eta_{\mathsf{a}}V_{1}=\nabla^{(e)}[F_{\cal
E}](\theta_{\mathsf{c}}),\quad\eta_{\mathsf{a}}=\nabla^{(e)}[F_{\cal
M}](V_{1}\theta_{\mathsf{c}}),$ (103)

which implies that

$\displaystyle\nabla^{(e)}[F_{\cal
M}](V_{1}\theta_{\mathsf{c}})V_{1}=\nabla^{(e)}[F_{\cal
E}](\theta_{\mathsf{c}}).$ (104)

Since the condition (104) for $\theta_{\mathsf{c}}$ is equivalent to the
condition that the element
$\left(\begin{array}[]{c}V_{1}\theta_{\mathsf{c}}\\\
\theta_{\mathsf{c}}\end{array}\right)\in\hat{\cal E}$ belongs to $\hat{\cal
M}$, we have the following corollary of Theorem 4.6.

###### Corollary 3

Assume that Conditions (B1) and (B3) hold and the intersection $\hat{\cal
M}\cap\hat{\cal E}$ is not empty. For an element
$(\theta_{\mathsf{a},*},\theta_{\mathsf{c},*})\in\hat{\cal M}\cap\hat{\cal
E}$, $\theta_{\mathsf{a},*}\in\Theta_{{\cal M}}$ is an invariant point of the
map $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$, i.e., an
invariant point of the inverse map $(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}})^{-1}$.

When Condition (B2) holds additionally, the maximization (47) is written as
follows.

$\displaystyle C_{\sup}({\cal M},{\cal E})=D^{F}(\phi^{(e)}_{{\cal
M}}(\theta_{\mathsf{a},*})\|\phi^{(e)}_{{\cal E}}(\theta_{\mathsf{c},*})).$
(105)

Therefore, the reverse em-problem (47) is reduced to finding the element
$(\theta_{\mathsf{a},*},\theta_{\mathsf{c},*})\in\hat{\cal M}\cap\hat{\cal
E}$. This element can be found by solving the following minimization problem;

$\displaystyle\mathop{\rm
argmin}\limits_{(\theta_{\mathsf{a}},\theta_{\mathsf{c}})\in\hat{\cal
M}}\min_{(\theta_{\mathsf{a}}^{\prime},\theta_{\mathsf{c}}^{\prime})\in\hat{\cal
E}}D^{F_{{\cal
M}}}(\theta_{\mathsf{a}}\|\theta_{\mathsf{a}}^{\prime})+D^{F_{{\cal
E}}}(\theta_{\mathsf{c}}\|\theta_{\mathsf{c}}^{\prime}).$ (106)

Since $\hat{\cal E}$ is an exponential family and $\hat{\cal M}$ is a mixture
family, the above minimization problem (106) is a special case of the em-
problem (46). Therefore, to solve (106), we can employ the em-algorithm,
Algorithm 1.

As another method to characterize the intersection $\hat{\cal M}\cap\hat{\cal
E}$, we assume Condition (B4), and introduce the parameterizations
$\theta_{\mathsf{c}}=(\theta_{\mathsf{a}},\theta_{\mathsf{b}})$ and
$\eta_{\mathsf{c}}=(\eta_{\mathsf{a}},\eta_{\mathsf{b}})$. Additionally, we
introduce the following new condition.

(B6)

Condition (B4) and the relation $k\geq 2l$ hold. The rank of $V_{3}$ is $l$.
The vector

$\displaystyle\theta_{\mathsf{a},*}:=\nabla^{(m)}[F_{{\cal
M}}^{*}](\eta_{\mathsf{a}})-\nabla_{\mathsf{a}}^{(m)}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}(I,V_{3}))$ (107)

does not depend on $\eta_{\mathsf{a}}\in\Xi_{{\cal M}}\subset\mathbb{R}^{l}$,
where

$\displaystyle\nabla^{(m)}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}(I,V_{3}))=\left(\begin{array}[]{c}\nabla^{(m)}_{\mathsf{a}}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}(I,V_{3}))\\\ \nabla^{(m)}_{\mathsf{b}}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}(I,V_{3}))\end{array}\right).$ (110)

When Condition (B6) holds, the first $l$ natural parameters of
$\eta_{\mathsf{a}}(I,V_{3})$ in ${\cal E}$ can be calculated from the natural
parameters of $\eta_{\mathsf{a}}$ in ${\cal M}$.

We choose an element $\theta_{\mathsf{b},*}\in\mathbb{R}^{k-l}$ and a
$(k-l)\times(k-2l)$ matrix $V_{4}$ such that

$\displaystyle\theta_{\mathsf{a},*}=$ $\displaystyle
V_{3}\theta_{\mathsf{b},*}$ (111) $\displaystyle\mathop{\rm Ker}V_{3}=$
$\displaystyle\mathop{\rm Im}V_{4}.$ (112)

The existence of $\theta_{\mathsf{b},*}$ is guaranteed by Condition (B6) (the
rank condition for $V_{3}$). Then, we define the following exponential and
mixture subfamilies of ${\cal E}$ as

$\displaystyle\overline{\cal E}:=$
$\displaystyle\\{(\theta_{\mathsf{a}},\theta_{\mathsf{b},*}+V_{4}\theta_{\mathsf{e}})^{T}|\theta_{\mathsf{a}}\in\mathbb{R}^{l},\theta_{\mathsf{e}}\in\mathbb{R}^{k-2l}\\}$
(113) $\displaystyle\overline{\cal M}:=$
$\displaystyle\\{(\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T}|(\eta_{\mathsf{a}},\eta_{\mathsf{b}})=\nabla^{(e)}[F_{{\cal
E}}]((\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T}),~{}\eta_{\mathsf{a}}V_{3}-\eta_{\mathsf{b}}=0\\}.$
(114)

We have the following corollary of Corollary 3.

###### Corollary 4

Assume Conditions (B1), (B3), (B4), and (B6). The following two conditions for
an element $(\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T}\in\Theta_{{\cal E}}$
are equivalent.

(F1)

The point $\mathop{\Gamma}\nolimits^{(e),F}_{\Theta_{\cal E}\to{\cal
M}}((\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T})$ is invariant for the map
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$.

(F2)

The element $(\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T}$ belongs to the
intersection $\overline{\cal E}\cap\overline{\cal M}$.

(F3)

There is an element $\eta_{\mathsf{a}}^{\prime}\in\Xi_{\cal M}$ such that
$\psi_{\cal M}^{(m)}(\eta_{\mathsf{a}}^{\prime})$ is invariant for the map
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$ and
$(\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T}=\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal
M}\to\Theta_{\cal E}}(\eta_{\mathsf{a}}^{\prime})$.

When Condition (B2) holds additionally, (F1) is equivalent to the following
condition.

(F1’)

The maximum exists in (47), i.e.,

$\displaystyle C_{\sup}({\cal M},{\cal
E})=D^{F}(\mathop{\Gamma}\nolimits^{(e),F}_{\Theta_{\cal E}\to{\cal
M}}(\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T})\|\phi^{(e)}_{{\cal
E}}((\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T}).$ (115)

Therefore, when the intersection $\overline{\cal E}\cap\overline{\cal M}$ is
not empty and Conditions (B1), (B2), (B3), (B4), and (B6) hold, the
maximization (47) is written by the element of $\overline{\cal
E}\cap\overline{\cal M}$ as (115).

###### Proof

We choose $(\eta_{\mathsf{a}},\eta_{\mathsf{b}})=\nabla^{(e)}[F_{{\cal
E}}]((\theta_{\mathsf{a}},\theta_{\mathsf{b}})^{T})$. The equivalent between
(F1) and (F3) is trivial.

In order that $\psi_{{\cal E}}^{(e)}(\eta_{\mathsf{a}},\eta_{\mathsf{b}})$
satisfies the condition (F1), $(\eta_{\mathsf{a}},\eta_{\mathsf{b}})$ needs to
be written as $\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal M}\to\Xi_{\cal
E}}(\eta_{\mathsf{a}}^{\prime})$ with $\eta_{\mathsf{a}}^{\prime}\in\Xi_{\cal
M}$. In addition, Lemma 10 guarantees that
$\mathop{\Gamma}\nolimits^{(m),F}_{\Xi_{\cal M}\to\Xi_{\cal
E}}(\eta_{\mathsf{a}}^{\prime})=\eta_{\mathsf{a}}^{\prime}(I,V_{3})$ and
$\eta_{\mathsf{a}}=\eta_{\mathsf{a}}^{\prime}$. That is, the condition (i)
$(\eta_{\mathsf{a}},\eta_{\mathsf{b}})=\eta_{\mathsf{a}}(I,V_{3})$, i.e.,
$\eta_{\mathsf{a}}V_{3}-\eta_{\mathsf{b}}=0$, is a necessary condition for
(F1). In the following, we discuss the equivalent condition for (F1) under
this necessary condition (i).

Condition (F1) is equivalent to each of the following conditions.

$\displaystyle\theta_{\mathsf{a},*}=$ $\displaystyle
V_{3}\nabla^{(m)}_{\mathsf{b}}[F_{{\cal E}}^{*}](\eta_{\mathsf{a}}(I,V_{3}))$
(116) $\displaystyle\nabla^{(m)}[F_{{\cal M}}^{*}](\eta_{\mathsf{a}})=$
$\displaystyle V_{1}\nabla^{(m)}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}(I,V_{3}))$ (117)

because (117) is the same as (83), which is equivalent to Condition (E1), and
we have

$\displaystyle\theta_{\mathsf{a},*}-V_{3}\nabla^{(m)}_{\mathsf{b}}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}^{\prime}(I,V_{3}))$ $\displaystyle\overset{(a)}{=}$
$\displaystyle\nabla^{(m)}[F_{{\cal
M}}^{*}](\eta_{\mathsf{a}}^{\prime})-\nabla^{(m)}_{\mathsf{a}}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}^{\prime}(I,V_{3}))-V_{3}\nabla^{(m)}_{\mathsf{b}}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}^{\prime}(I,V_{3}))$ $\displaystyle\overset{(b)}{=}$
$\displaystyle\nabla^{(m)}[F_{{\cal
M}}^{*}](\eta_{\mathsf{a}}^{\prime})-V_{1}\nabla^{(m)}[F_{{\cal
E}}^{*}](\eta_{\mathsf{a}}^{\prime}(I,V_{3})),$ (118)

where $(a)$ and $(b)$ follow from (B6) and the relation $V_{1}=(I,V_{3}))$,
respectively.

The condition (116) is equivalent to the condition
$\theta_{\mathsf{a},*}=V_{3}\theta_{\mathsf{b}}$. This condition is equivalent
to the condition (ii) that $\theta_{\mathsf{b}}$ is written as
$\theta_{\mathsf{b},*}+V_{4}\theta_{\mathsf{e}}$. Since the conditions (i) and
(ii) correspond to the sets $\overline{\cal M}$ and $\overline{\cal E}$,
respectively. Therefore, (F1) implies (F2).

Conversely, when Condition (F2) holds, the conditions (i) and (ii) hold. Due
to (118), under the condition (i), the condition (ii), i.e., (116) implies
(117), which is equivalent to (F1). Therefore, (F2) implies (F1). The desired
equivalence is obtained.

Therefore, the reverse em-problem (47) is reduced to finding the element
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})^{T}\in\overline{\cal
E}\cap\overline{\cal M}$. This element can be found by solving the following
minimization problem;

$\displaystyle\mathop{\rm
argmin}\limits_{(\theta_{\mathsf{a}},\theta_{\mathsf{b}})\in\overline{\cal
M}}\min_{(\theta_{\mathsf{a}}^{\prime},\theta_{\mathsf{b}}^{\prime})\in\overline{\cal
E}}D^{F_{{\cal
E}}}((\theta_{\mathsf{a}},\theta_{\mathsf{b}})\|(\theta_{\mathsf{a}}^{\prime},\theta_{\mathsf{b}}^{\prime})).$
(119)

Since $\overline{\cal E}$ is an exponential family and $\overline{\cal M}$ is
a mixture family, the above minimization problem (119) is another special case
of the em-problem (46). Therefore, to solve (119), we can employ the em-
algorithm, Algorithm 1. The minimization problem (119) has a smaller number of
free parameters than the minimization problem (106).

The following is an alternative method to find an element of
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$. Find an
element $\eta_{\mathsf{a},*}$ to realize an extremal value of the following
function;

$\displaystyle\kappa(\eta_{\mathsf{a}}):=F_{{\cal
E}^{*}}(\eta_{\mathsf{a}}(I,V_{3}))-F_{{\cal
M}^{*}}(\eta_{\mathsf{a}})-\langle\eta_{\mathsf{a}},\theta_{\mathsf{a},*}\rangle-\langle\eta_{\mathsf{a}},V_{3}\theta_{\mathsf{b},*}\rangle.$
(120)

###### Lemma 12

Assume Conditions (B1), (B3), (B4), and (B6). The condition

$\displaystyle\nabla[\kappa](\eta_{\mathsf{a},*})=0$ (121)

is equivalent to $\nabla^{(m)}[F_{{\cal
E}^{*}}](\eta_{\mathsf{a},*}(I,V_{3}))\in\overline{\cal M}\cap\overline{\cal
E}$.

That is, the above extremal value gives the solution (115).

###### Proof

We have

$\displaystyle\nabla[\kappa](\eta_{\mathsf{a},*})$ $\displaystyle=$
$\displaystyle(I,V_{3})(\nabla^{(m)}[F_{{\cal
E}^{*}}](\eta_{\mathsf{a},*}(I,V_{3}))-\nabla^{(m)}[F_{{\cal
M}^{*}}](\eta_{\mathsf{a},*})-\theta_{\mathsf{a},*}-V_{3}\theta_{\mathsf{b},*}$
$\displaystyle\overset{(a)}{=}$ $\displaystyle
V_{3}(\nabla^{(m)}_{\mathsf{b}}[F_{{\cal
E}^{*}}](\eta_{\mathsf{a},*}(I,V_{3}))-\theta_{\mathsf{b},*}),$

where $(a)$ follows from (107) in (B6). Hence, (121) is equivalent to
$\nabla^{(m)}[F_{{\cal E}^{*}}](\eta_{\mathsf{a},*}(I,V_{3}))\in\overline{\cal
E}$.

###  4.8 Non-iterative method

We directly characterize the maximizer of the maximization (47) without
iterations. For this aim, we assume Condition (B5) in addition to (B1), (B3),
and (B4). When Condition (B5) holds, Condition (B6) is rewritten as follows.

(B6+)

Condition (B4) and the relation $k\geq 2l$ hold. The rank of $V_{3}$ is $l$.
The vector $\theta_{\mathsf{a},*}:=\nabla^{(m)}[F_{{\cal
M}}^{*}](\eta_{\mathsf{a}})-\nabla^{(m)}[F_{{\cal
E},\mathsf{a}}^{*}](\eta_{\mathsf{a}})$ does not depend on
$\eta_{\mathsf{a}}\in\Xi_{{\cal M}}\subset\mathbb{R}^{l}$.

Using the solution $\theta_{\mathsf{b},*}$ of (111), we define the following
exponential and mixture subfamilies of ${\cal E}_{\mathsf{b}}$ as

$\displaystyle\overline{\cal E}_{\mathsf{b}}:=$
$\displaystyle\\{\theta_{\mathsf{b},*}+V_{4}\theta_{\mathsf{e}}\in\Theta_{{\cal
E},\mathsf{b}}|\theta_{\mathsf{e}}\in\mathbb{R}^{k-2l}\\}$ (122)
$\displaystyle\overline{\cal M}_{\mathsf{b}}:=$
$\displaystyle\\{\theta_{\mathsf{b}}\in\Theta_{{\cal
E},\mathsf{b}}|\eta_{\mathsf{b}}=\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\theta_{\mathsf{b}}),~{}\eta_{\mathsf{b}}V_{4}=0\\}.$ (123)

We have the following corollary of Corollary 4.

###### Corollary 5

Assume Conditions (B1), (B3), (B4), (B5), (B6+), and $\Theta=\mathbb{R}^{d}$.
The following condition (E4) for an element
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})^{T}\in\Theta_{{\cal
E}}$ is equivalent to (F1), (F2), and (F3) in Corollary 4.

(F4)

The following relations hold.

$\displaystyle\bar{\theta}_{\mathsf{b},*}$ $\displaystyle\in\overline{\cal
E}_{\mathsf{b}}\cap\overline{\cal M}_{\mathsf{b}}$ (124)
$\displaystyle\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\bar{\theta}_{\mathsf{b},*})$
$\displaystyle=\nabla^{(e)}[F_{{\cal
E},\mathsf{a}}](\bar{\theta}_{\mathsf{a},*})V_{3}.$ (125)

###### Proof

Condition (F2) element
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})^{T}\in\Theta_{{\cal
E}}$ is equivalent to the pair of the following conditions. (i)
$\bar{\theta}_{\mathsf{b},*}$ has the form
$\theta_{\mathsf{b},*}+V_{4}\theta_{\mathsf{e}}$, which corresponds to the
condition
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})^{T}\in\overline{\cal
E}$. (ii) The pair $(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})$
satisfies the condition (125), which corresponds to the condition
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})^{T}\in\overline{\cal
M}$. To satisfy (125), $\nabla^{(e)}[F_{{\cal
E}_{\mathsf{b}}}](\bar{\theta}_{\mathsf{b},*})$ needs to have the form
$\bar{\eta}_{\mathsf{a},*}V_{3}$ with
$\bar{\eta}_{\mathsf{a},*}\in\mathbb{R}^{l}$, which is equivalent to the
condition (iii); $\nabla^{(e)}[F_{{\cal
E}_{\mathsf{b}}}](\bar{\theta}_{\mathsf{b},*})V_{4}=0$, i.e.,
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})^{T}\in\overline{\cal
M}_{\mathsf{b}}$. Since the conditions (i), (ii), and (iii) are equivalent to
Condition (F4), we obtain the desired statement.

Although $\overline{\cal E}_{\mathsf{b}}$ is an exponential family and
$\overline{\cal M}_{\mathsf{b}}$ is a mixture family, we do not need to employ
the em-algorithm, Algorithm 1, because it can be solved directly as follows.
Since the generating vectors of $\overline{\cal E}_{\mathsf{b}}$ is the same
as that of $\overline{\cal M}_{\mathsf{b}}$, the intersection (124) can be
calculated by solving the following minimization. That is, the following
method finds the element in $\overline{\cal M}_{\mathsf{b}}$ among elements in
$\overline{\cal E}_{\mathsf{b}}$. Define $\bar{\theta}_{\mathsf{e},*}$ as

$\displaystyle\bar{\theta}_{\mathsf{e},*}:=\mathop{\rm
argmin}\limits_{\theta_{3}\in\mathbb{R}^{k-2l}}F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b},*}+V_{4}\theta_{\mathsf{e}}),$ (126)

where $\theta_{\mathsf{b},*}$ is defined by (107) and (111). Then, we have
$\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\theta_{\mathsf{b},*}+V_{4}\bar{\theta}_{\mathsf{e},*})V_{4}=0$,
which implies
$\theta_{\mathsf{b},*}+V_{4}\bar{\theta}_{\mathsf{e},*}\in\overline{\cal
M}_{\mathsf{b}}$. Thus,

$\displaystyle\bar{\theta}_{\mathsf{b},*}:=\theta_{\mathsf{b},*}+V_{4}\bar{\theta}_{\mathsf{e},*}\in\overline{\cal
E}_{\mathsf{b}}\cap\overline{\cal M}_{\mathsf{b}}.$ (127)

Therefore, the statement of Corollary 5 is rewritten as follows.

###### Theorem 4.7

Assume Conditions (B1), (B3), (B4), (B5), (B6+), and $\Theta=\mathbb{R}^{d}$.
We choose $\bar{\theta}_{\mathsf{b},*}$ by combining (127) and the solution of
(126). Also, we choose $\bar{\eta}_{\mathsf{a},*}\in\mathbb{R}^{l}$ as
$\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\bar{\theta}_{\mathsf{b},*})=\bar{\eta}_{\mathsf{a},*}V_{3}$.
When $\bar{\eta}_{\mathsf{a},*}\in\mathbb{R}^{l}$ belongs to the image of
$\nabla^{(e)}[F_{{\cal E},\mathsf{a}}]$, there exists
$\bar{\theta}_{\mathsf{a},*}\in\Theta_{{\cal E},\mathsf{a}}$ to satisfy the
condition (125), i.e., $\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\bar{\theta}_{\mathsf{b},*})=\nabla^{(e)}[F_{{\cal
E},\mathsf{a}}](\bar{\theta}_{\mathsf{a},*})V_{3}$, and the parameter
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})$ is invariant for
the map $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal M}\to{\cal E}}$. When
Condition (B2) holds additionally, the parameter
$(\bar{\theta}_{\mathsf{a},*},\bar{\theta}_{\mathsf{b},*})$ is the solution of
the maximum in (47).

Due to Corollary 5, the existence of the maximum in (47), Condition (E1), is
equivalent to the existence of $\bar{\eta}_{\mathsf{a},*}\in\mathbb{R}^{l}$
that belongs to the image of $\nabla^{(e)}[F_{{\cal E}_{\mathsf{a}}}]$. That
is, although an element $\bar{\theta}_{\mathsf{b},*}\in\Theta_{{\cal
E}_{\mathsf{b}}}$ exists, there is a possibility that no element
$\bar{\theta}_{\mathsf{a},*}\in\Theta_{{\cal E}_{\mathsf{a}}}$ satisfies the
condition (125) with $\bar{\theta}_{\mathsf{b},*}$. Therefore, the method of
this subsection works only when the maximum in (47) exists. That is, when the
maximum does not exist in (47), the non-iterative method does not work at all.
Instead of the non-iterative method, as proven in Theorem 4.1, the iterative
algorithms in the previous subsection work even when the maximum does not
exist in (47).

Now, we compare the minimization (126) with the original reverse em-problem
(47). The minimization (126) is given as the minimization of the convex
function $F_{{\cal E},\mathsf{b}}$. This objective function $F_{{\cal
E},\mathsf{b}}$ has a simpler form than the objective function of the original
reverse em-problem (47) because it is a part of the potential function to
define the exponential family ${\cal E}$. Further, the number of free
parameters in the minimization (126) is $k-2l$. When $k<3l$, the number of
free parameters in this method is smaller than the number of free parameters
of the original reverse em-problem. Depending on the situation, this method
reduces the number of free parameters. In particular, when $k=2l$, the matrix
$V_{3}$ is a square matrix of size $l$ and we do not need to solve the
minimization (126) as follows. In this case, when the rank of $V_{3}$ is $l$,
$\mathop{\rm Ker}V_{3}$ is $\\{0\\}$, which implies $V_{4}=0$. Hence, as the
special case with $k=2l$, i.e., the case when the number of parameters in
${\cal E}$ is twice of that of ${\cal M}$, we have the following corollary.

###### Corollary 6

Assume Conditions (B1), (B3), (B4), (B5), (B6+), $\Theta=\mathbb{R}^{d}$, and
$k=2l$. Then, the intersection $\overline{\cal E}\cap\overline{\cal M}$ is
given as $\\{\theta_{\mathsf{b},*}\\}$, where $\theta_{\mathsf{b},*}$ is
defined by (107) and (111). In addition, when there exists
$\bar{\theta}_{\mathsf{a},*}\in\Theta_{{\cal M}}$ such that

$\displaystyle\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\theta_{\mathsf{b},*})=\nabla^{(e)}[F_{{\cal
E},\mathsf{a}}](\bar{\theta}_{\mathsf{a},*})V_{3},$ (128)

the relation (115) holds under the choice
$\bar{\theta}_{\mathsf{b},*}=\theta_{\mathsf{b},*}$.

That is, Corollary 6 shows a simple calculation method for $k=2l$. However, it
works when an element $\bar{\theta}_{\mathsf{a},*}\in\Theta_{{\cal M}}$ to
satisfy (128) exists. In addition, as explained in Sections 5 and 7, the
algorithms in the reference exact  are special cases of the method based on
Theorem 4.7. Hence, this method can be considered as an extension of
algorithms in the reference exact .

Here, we notice that Condition (B2) can be replaced by the unique existence of
the solution of the maximization (47) in the discussions in Subsections 4.7
and 4.8. When we drop this condition, the methods in Subsections 4.7 and 4.8
work for finding the local maximizer of the maximization (47).

##  5 Capacity of classical channel

###  5.1 Problem setting

Let ${\mathcal{X}}:=\\{1,\ldots,n_{1}\\}$ and
${\mathcal{Y}}:=\\{1,\ldots,n_{2}\\}$ be finite sets. We call a map
$W:{\mathcal{X}}\rightarrow{\cal P}_{{\mathcal{Y}}}$ a channel from
${\mathcal{X}}$ to ${\mathcal{Y}}$. We use the notation $W_{x}(y):=W(y|x)$.
For $q\in{\cal P}_{{\mathcal{X}}}$ and $r\in{\cal P}_{{\mathcal{Y}}}$, $W\cdot
q\in{\cal P}_{{\mathcal{Y}}}$, $W\times q\in{\cal
P}_{{\mathcal{X}}\times{\mathcal{Y}}}$, and $q\times
r\in\mathcal{P}_{{\mathcal{X}}\times{\mathcal{Y}}}$ are defined by $(W\cdot
q)(x,y):=\sum_{x\in{\mathcal{X}}}W(y|x)q(x)$, $(W\times q)(x,y):=W(y|x)q(x)$,
and $(q\times r)(x,y):=q(x)r(y)$ respectively. The channel capacity of a
channel $W$ is given by

$\displaystyle\max_{q\in{{\cal P}_{{\mathcal{X}}}}}D(W\times q\|(W\cdot
q)\times q)=\max_{q\in{{\cal P}_{{\mathcal{X}}}}}\min_{q^{\prime}\in{{\cal
P}_{{\mathcal{X}}}},q^{\prime\prime}\in{{\cal P}_{{\mathcal{Y}}}}}D(W\times
q\|q^{\prime\prime}\times q^{\prime}).$ (129)

As explained in Subsection 5.4, the set of product distributions
$q^{\prime\prime}\times q^{\prime}$ forms an exponential subfamily ${\cal E}$
and the set of distributions $W\times q$ forms a mixture subfamily ${\cal M}$.
That, the maximization problem (129) is a special case of the maximization
(47) with $k=n_{1}-1$, $l=n_{1}+n_{2}-2$, and $d=n_{1}n_{2}-1$. In the
following, we apply Algorithm 4. For this aim, we need to choose a suitable
coordinate to satisfy conditions (B1), (B3), (B4), and (B5) and check
Condition (B2).

###  5.2 Constructions of vectors
$u_{1},\ldots,u_{n_{1}n_{2}-1},v_{1},\ldots,v_{n_{1}+n_{2}-2}$

To choose a suitable coordinate to satisfy conditions (B3), (B4), and (B5), we
need to choose suitable vectors
$u_{1},\ldots,u_{n_{1}n_{2}},v_{1},\ldots,v_{n_{1}+n_{2}-1}$. For this aim, we
define various functions on ${\cal Y}$ and ${\cal X}\times{\cal Y}$.

First, we choose $n_{2}-1$ linearly independent functions $f_{j}$ on ${\cal
Y}$ for $j=1,\ldots,n_{2}-1$ to satisfy the condition that

$\displaystyle\sum_{y\in{\cal Y}}f_{j}(y)W_{n_{1}}(y)=0$ (130)

and the linear space spanned by $f_{1},\ldots,f_{n_{2}-1}$ does not contain a
constant function. As a typical case, $f_{j}$ can be chosen as follows.

$\displaystyle f_{j}(y):=\left\\{\begin{array}[]{ll}W_{n_{1}}(j+1)&\hbox{when
}y=j\\\ -W_{n_{1}}(j)&\hbox{when }y=j+1\\\
0&\hbox{otherwise}.\end{array}\right.$ (134)

Then, we define the functions $\xi_{1},\ldots,\xi_{n_{1}n_{2}-1}$ on ${\cal
X}\times{\cal Y}$ as follows.

$\displaystyle\xi_{i}(x,y):=$ $\displaystyle\delta_{i}(x)$ (135)
$\displaystyle\xi_{n_{1}-1+(i-1)(n_{2}-1)+j}(x,y):=$
$\displaystyle(f_{j}(y)-h_{i,j})\delta_{i}(x)$ (136)
$\displaystyle\xi_{(n_{1}-1)n_{2}+j}(x,y):=$ $\displaystyle
f_{j}(y)\delta_{n_{1}}(x)$ (137)

for $i=1,\ldots,n_{1}-1$ and $j=1,\ldots,n_{2}-1$, where we define

$\displaystyle h_{i,j}:=\sum_{y}f_{j}(y)W_{i}(y)$ (138)

for $i=1,\ldots,n_{1}$ and $j=1,\ldots,n_{2}-1$.

Then, we define the $C^{\infty}-$strictly convex function $F$ on
$\mathbb{R}^{n_{1}n_{2}-1}$ as

$\displaystyle
F(\theta):=\log\sum_{x,y}e^{\sum_{i=1}^{n_{1}n_{2}-1}\theta^{i}\xi_{i}(x,y)}$
(139)

That is, we consider the Bregman divergence system $(\mathbb{R}^{d},F,D^{F})$.
We define the distribution $P_{\theta,XY},P_{\theta,X},P_{\theta,Y}$ as

$\displaystyle P_{\theta,XY}(x,y)$
$\displaystyle:=e^{\sum_{i=1}^{n_{1}n_{2}-1}\theta^{i}\xi_{i}(x,y)-F(\theta)},$
(140) $\displaystyle P_{\theta,X}(x)$
$\displaystyle:=\sum_{y}e^{\sum_{i=1}^{n_{1}n_{2}-1}\theta^{i}\xi_{i}(x,y)-F(\theta)},$
(141) $\displaystyle P_{\theta,Y}(y)$
$\displaystyle:=\sum_{x}e^{\sum_{i=1}^{n_{1}n_{2}-1}\theta^{i}\xi_{i}(x,y)-F(\theta)}.$
(142)

Then, as a special case of (40), we have

$\displaystyle
D^{F}(\theta\|\theta^{\prime})=D(P_{\theta,XY}\|P_{\theta^{\prime},XY}).$
(143)

Next, we choose the matrix $U$ as the identity matrix, and
$u_{1},\ldots,u_{n_{1}n_{2}-1}$ are chosen as its $n_{1}n_{2}-1$ column
vectors. Then, we define vectors $v_{1},\ldots,v_{n_{1}+n_{2}-2}$ as follows,
whereas $V=(v_{1},\ldots,v_{n_{1}+n_{2}-2})$.

$\displaystyle v_{i}:=$ $\displaystyle u_{i}\hbox{ for }i=1,\ldots,n_{1}-1,$
(144) $\displaystyle v_{n_{1}-1+j}:=$
$\displaystyle\sum_{i=1}^{n_{1}}u_{n_{1}-1+(i-1)(n_{2}-1)+j}+\sum_{i=1}^{n_{1}-1}h_{i,j}u_{i}\hbox{
for }j=1,\ldots,n_{2}-1.$ (145)

Then, we have

$\displaystyle\sum_{i=1}^{n_{1}n_{2}-1}\xi_{i}(x,y)v_{j}^{i}=\left\\{\begin{array}[]{ll}\delta_{j}(x)&\hbox{when
}j=1,\ldots,n_{1}-1\\\ f_{j-n_{1}+1}(y)&\hbox{when
}j=n_{1},\ldots,n_{1}+n_{2}-1.\end{array}\right.$ (148)

The case with $j=n_{1},\ldots,n_{1}+n_{2}-1$ can be shown as follows. For
$j=1,\ldots,n_{2}-1$, we have

$\displaystyle\sum_{i=1}^{n_{1}n_{2}-1}\xi_{i}(x,y)v_{n_{1}-1+j}^{i}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n_{1}n_{2}-1}\xi_{i}(x,y)\Big{(}\sum_{i^{\prime}=1}^{n_{1}}u^{i}_{n_{1}-1+(i^{\prime}-1)(n_{2}-1)+j}+\sum_{i^{\prime}=1}^{n_{1}-1}h_{i^{\prime},j}u_{i^{\prime}}^{i}\Big{)}$
$\displaystyle=$
$\displaystyle\sum_{i^{\prime}=1}^{n_{1}}\xi_{n_{1}-1+(i^{\prime}-1)(n_{2}-1)+j}(x,y)+\sum_{i^{\prime}=1}^{n_{1}-1}\xi_{i^{\prime}}(x,y)h_{i^{\prime},j}$
$\displaystyle=$
$\displaystyle\xi_{(n_{1}-1)n_{2}+j}(x,y)+\sum_{i^{\prime}=1}^{n_{1}-1}\xi_{n_{1}-1+(i^{\prime}-1)(n_{2}-1)+j}(x,y)+\sum_{i^{\prime}=1}^{n_{1}-1}\xi_{i^{\prime}}(x,y)h_{i^{\prime},j}$
$\displaystyle=$ $\displaystyle
f_{j}(y)\delta_{n_{1}}(x)+\sum_{i=1}^{n_{1}-1}(f_{j}(y)-h_{i,j})\delta_{i}(x)+\sum_{i=1}^{n_{1}-1}\delta_{i}(x)h_{i,j}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{n_{1}}f_{j}(y)\delta_{i}(x)=f_{j}(y).$ (149)

###  5.3 Parameterizations of ${\cal E}$ and ${\cal M}$

Using

$\displaystyle F_{{\cal E},\mathsf{a}}(\theta^{1},\ldots,\theta^{n_{1}-1})$
$\displaystyle:=\log\sum_{x}e^{\sum_{i=1}^{n_{1}-1}\theta^{i}\delta_{i}(x)}$
(150) $\displaystyle F_{{\cal
E},\mathsf{b}}(\theta^{n_{1}},\ldots,\theta^{n_{1}+n_{2}-2})$
$\displaystyle:=\log\sum_{y}e^{\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+j}f_{j}(y)},$
(151)

we define the distributions on ${\mathcal{X}}$ and ${\mathcal{Y}}$ as

$\displaystyle\bar{P}_{\theta_{\mathsf{a}},X}(x):=$ $\displaystyle
e^{\sum_{i=1}^{n_{1}-1}\theta^{i}\delta_{i}(x)-F_{{\cal
E},1}(\theta_{\mathsf{a}})}$ (152)
$\displaystyle\bar{P}_{\theta_{\mathsf{b}},Y}(y):=$ $\displaystyle
e^{\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+j}f_{j}(y)-F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}})}$ (153)

for $\theta_{\mathsf{a}}:=(\theta^{1},\ldots,\theta^{n_{1}-1})$ and
$\theta_{\mathsf{b}}:=(\theta^{n_{1}},\ldots,\theta^{n_{1}+n_{2}-2})$. Then,
we have

$\displaystyle
P_{\sum_{j=1}^{n_{1}-1}\theta_{\mathsf{a}}^{j}v_{j}+\sum_{j^{\prime}=1}^{n_{2}-1}\theta_{\mathsf{b}}^{j}v_{n_{1}-1+j},XY}=\bar{P}_{\theta_{\mathsf{a}},X}\times\bar{P}_{\theta_{\mathsf{b}},Y}.$
(154)

Hence, the set of product distributions is written as the exponential
subfamily ${\cal
E}:=\\{P_{\sum_{j=1}^{n_{1}+n_{2}-2}\bar{\theta}^{j}v_{j},XY}\\}$ generated by
$v_{1},\ldots,v_{n_{1}+n_{2}-2}$ at the point $(0,\ldots,0)$. Then, we have
$F_{{\cal E}}(\theta_{\mathsf{a}},\theta_{\mathsf{b}})=F_{{\cal
E},\mathsf{a}}(\theta_{\mathsf{a}})+F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}})$.

We define the mixture family ${\cal M}$ by the constraint
$\sum_{i=1}^{n_{1}n_{2}-1}u^{i}_{n_{1}-1+j^{\prime}}\partial_{i}F(\theta)=0$
for $j^{\prime}=1,\ldots,n_{1}(n_{2}-1)$. This constraint is equivalent to

$\displaystyle\sum_{y}(f_{j}(y)-h_{i^{\prime},j})P_{\theta,XY}(i^{\prime},y)=0,\quad\sum_{y}f_{j}(y)P_{\theta,XY}(n_{1},y)=0$
(155)

for $i^{\prime}=1,\ldots,n_{1}-1$ and $j=1,\ldots,n_{2}-1$. Hence, the mixture
family ${\cal M}$ is composed of distributions with the form $W\times q$.
Thus, the problem (129) is written as the problem (47) with the above defined
${\cal E}$ and ${\cal M}$. The conditional probability
$P_{\theta,Y|X}(y|i)=\frac{P_{\theta,XY}(i,y)}{\sum_{y^{\prime}}P_{\theta,XY}(i,y^{\prime})}$
depends only on $(\theta^{n_{1}-1+(i-1)(n_{2}-1)+j})_{j=1}^{n_{2}-1}$ for
$i=1,\ldots,n_{1}$. Since

$\displaystyle P_{\theta,Y|X}(y|i)=$
$\displaystyle\frac{e^{\theta^{i}+\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j}\xi_{n_{1}-1+(i-1)(n_{2}-1)+j}(i,y)}}{\sum_{y^{\prime}}e^{\theta^{i}+\sum_{j^{\prime}=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j^{\prime}}\xi_{n_{1}-1+(i-1)(n_{2}-1)+j^{\prime}}(i,y^{\prime})}}$
$\displaystyle=$
$\displaystyle\frac{e^{\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j}(f_{j}(y)-h_{i,j})}}{\sum_{y^{\prime}}e^{\sum_{j^{\prime}=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j^{\prime}}(f_{j}(y^{\prime})-h_{i,j^{\prime}})}},$
(156)

we choose
$\theta_{\mathsf{b}}^{\dagger}=(\theta^{n_{1},\dagger},\ldots,\theta^{n_{1}n_{2}-1,\dagger})$
as

$\displaystyle
W_{i}(y)=\frac{e^{\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j,\dagger}(f_{j}(y)-h_{i,j})}}{\sum_{y^{\prime}}e^{\sum_{j^{\prime}=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j^{\prime},\dagger}(f_{j^{\prime}}(y^{\prime})-h_{i,j^{\prime}})}}.$
(157)

In this choice, we have

$\displaystyle\log\sum_{y^{\prime}}e^{\sum_{j^{\prime}=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j^{\prime},\dagger}(f_{j^{\prime}}(y^{\prime})-h_{i,j^{\prime}})}=H(W_{i})$
(158)

because

$\displaystyle\sum_{y^{\prime}}(f_{j}(y^{\prime})-h_{i,j})e^{\sum_{j^{\prime}=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j^{\prime},\dagger}(f_{j^{\prime}}(y^{\prime})-h_{i,j^{\prime}})}=0$
(159)

for $j=1,\ldots,n_{2}-1$.

Then, ${\cal M}$ is written as
$\\{(\theta_{\mathsf{a}},\theta_{\mathsf{b}}^{\dagger})|\theta_{\mathsf{a}}\in\mathbb{R}^{n_{1}-1}\\}$.
That is, ${\cal M}$ forms an exponential subfamily generated by
$u_{1},\ldots,u_{n_{1}-1}$. Using (139), the function $F_{{\cal M}}$ is
written as

$\displaystyle F_{{\cal
M}}(\theta_{\mathsf{a}})=F(\theta_{\mathsf{a}},\theta_{\mathsf{b}}^{\dagger})=\log\sum_{x,y}e^{\sum_{i=1}^{n_{1}-1}\theta^{i}\delta_{i}(x)+\sum_{i=n_{1}}^{n_{1}n_{2}-1}\theta^{i,\dagger}\xi_{i}(x,y)}$
(160)

Hence, the maximization (129) is rewritten as

$\displaystyle\sup_{q\in{{\cal P}_{{\mathcal{X}}}}}D(W\times q\|q\times(W\cdot
q))=\max_{\theta\in\mathcal{M}}D^{F}(\theta\|\mathop{\Gamma}\nolimits^{(m),F}_{\mathcal{E}}(\theta))=\max_{\theta\in\mathcal{M}}\min_{\theta^{\prime}\in\mathcal{E}}D^{F}(\theta\|\theta^{\prime}).$
(161)

###  5.4 Check of Conditions (B1), (B2), (B3), (B4), and (B5)

Lemma 7 guarantees Condition (B1). We define the $(n_{1}-1)\times(n_{2}-1)$
matrix $H:=(h_{i,j})$. Then, the relation (145) guarantees that the
$(n_{1}-1)\times(n_{1}+n_{2}-2)$ matrix $V_{1}$ is $(I,H)$. That is, the
$(n_{1}-1)\times(n_{2}-1)$ matrix $V_{3}$ is $H$. Hence, Conditions (B3) and
(B4) hold. Since the exponential family ${\cal E}$ satisfies $F_{{\cal
E}}(\bar{\theta}_{\mathsf{a}},\bar{\theta}_{\mathsf{b}})=F_{{\cal
E},1}(\bar{\theta}_{\mathsf{a}})+F_{{\cal E},2}(\bar{\theta}_{\mathsf{b}})$,
we obtain Condition (B5). Therefore, we can apply Algorithm 4 with Condition
(B5). Therefore, we can apply Algorithms 3 and 4 to calculate the maximum
(129).

As we have

$\displaystyle P_{\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta),XY}=P_{\theta,X}\times P_{\theta,Y}$ (162)

for any $\theta$, we have

$\displaystyle D^{F}(\theta^{\prime}\|\theta)=$ $\displaystyle
D(P_{\theta,XY}\|P_{\theta^{\prime},XY})=D(P_{\theta,X}\|P_{\theta^{\prime},X})$
$\displaystyle\leq$ $\displaystyle
D(P_{\theta,X}\|P_{\theta^{\prime},X})+D(P_{\theta,Y}\|P_{\theta^{\prime},Y})$
$\displaystyle=$ $\displaystyle D(P_{\theta,X}\times
P_{\theta,Y}\|P_{\theta^{\prime},X}\times
P_{\theta^{\prime},Y})=D(P_{\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta)}\|P_{\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{\prime})})$ $\displaystyle=$ $\displaystyle
D^{F}(\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta)\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}(\theta^{\prime}))$
(163)

for $\theta,\theta^{\prime}\in{\cal M}$. Thus, condition (B2) holds.
Therefore, Theorem 4.1 guarantees the global convergence. When $\theta^{(1)}$
is $W\times P_{{\rm uni},X}$ with the uniform distribution $P_{{\rm uni},X}$
on ${\cal X}$, we have

$\displaystyle\sup_{\theta\in\mathcal{M}}D^{F}(\theta\|\theta^{(1)})=$
$\displaystyle\sup_{q\in{\cal P}({\cal X})}D(W\times q\|W\times P_{{\rm
uni},X})$ $\displaystyle=$ $\displaystyle\sup_{q\in{\cal P}({\cal
X})}D(q\|P_{{\rm uni},X})=\log n_{1}.$ (164)

Therefore, when Theorem 4.1 is applied, we obtain the precision (54) with
$\frac{\log n_{1}}{\epsilon}$ iterations. Also, we can apply Theorem 4.4 to
the error evaluation in Algorithm 4.

With the above choice of $\theta^{(1)}$, we consider the case when the
distributions $\\{W_{x}\\}_{x}$ are linearly independent. We have
$D^{F}(\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta^{*})\|\mathop{\Gamma}\nolimits^{(m),F}_{{\cal
E}}(\theta))-D^{F}(\theta^{*}\|\theta)=D(W\cdot P_{\theta^{*},X}\|W\cdot
P_{\theta,X})$. Since the set
$\\{\theta\in\mathcal{M}|D(P_{\theta^{*},X}\|P_{\theta,X})\leq
D(P_{\theta^{*},X}\|P_{\theta^{(1)},X})\\}$ is compact and $D(W\cdot
P_{\theta^{*},X}\|W\cdot P_{\theta,X})>0$, there exists $\alpha>0$ such that
$\frac{D(W\cdot P_{\theta^{*},X}\|W\cdot
P_{\theta,X})}{D(P_{\theta^{*},X}\|P_{\theta,X})}\geq\alpha$ for
$\theta\in\\{\theta\in\mathcal{M}|D(P_{\theta^{*},X}\|P_{\theta,X})\leq
D(P_{\theta^{*},X}\|P_{\theta^{(1)},X})\\}$. This condition implies the
condition (B2+). Hence, we can apply Theorem 4.2 instead of Theorem 4.1. When
$\theta^{(1)}$ is the uniform distribution on ${\cal X}$, we obtain the
precision (57) with $\frac{\log\log n_{1}-\log\epsilon}{\log(1+\alpha)}$
iterations.

However, each step in Algorithms 3 and 4 contains a minimization problem.
Unfortunately, this minimization requires convex minimization. Since Arimoto-
Blahut algorithm Arimoto ; Blahut  has a simple procedure in each step, the
application of these methods to the classical channel capacity does not have
an advantage over existing methods.

###### Remark 2

As shown in the end of Section 4 of Toyota Shoji , the algorithm by Arimoto
Arimoto  and Blahut Blahut  does not use the inverse map
$(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal M}})^{-1}$ in each
iteration. Toyota Shoji  proposed to use the inverse map
$(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}\circ\mathop{\Gamma}\nolimits^{(m),F}_{{\cal E}}|_{{\cal M}})^{-1}$ in each
iteration instead of the original Arimoto-Blahut algorithm, he did not derive
the exact expression of the inverse map.

###  5.5 Non-iterative method

Next, we characterize the maximization (129) without any iterative method. To
check Condition (B6+), we prepare the following lemmas.

###### Lemma 13

The relation

$\displaystyle
P_{(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger}),X}=\bar{P}_{\theta_{\mathsf{a}},X}$
(165)

holds, where
$\theta_{\mathsf{a}}^{\dagger}=(\theta^{1,\dagger},\ldots,\theta^{n_{1}-1,\dagger})$
is defined as $\theta^{i,\dagger}:=-H(W_{i})+H(W_{n_{1}})$ for
$i=1\ldots,n_{1}-1$.

###### Proof

We define
$\theta_{(i)}^{\dagger}=(\theta^{n_{1}-1+(i-1)(n_{2}-1)+1,\dagger},\ldots,\theta^{n_{1}-1+i(n_{2}-1),\dagger})\in\mathbb{R}^{n_{1}-1}$.
Since $W_{i}=\bar{P}_{\theta_{(i)}^{\dagger},Y}$, we have
$W_{i}(y)=e^{\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j,\dagger}(f_{j}(y)-h_{i,j})-F_{{\cal
E},2}(\theta_{(i)}^{\dagger})}$. Because

$\displaystyle e^{F_{{\cal
E},\mathsf{b}}(\theta_{(i)}^{\dagger})}=\sum_{y\in{\mathcal{Y}}}e^{\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+(i-1)(n_{2}-1)+j,\dagger}(f_{j}(y)-h_{i,j})},$
(166)

(158) implies the relation

$\displaystyle H(W_{i})=-\sum_{y}W_{i}(y)\log W_{i}(y)=F_{{\cal
E},2}(\theta_{(i)}^{\dagger})$ (167)

for $i=1,\ldots,n_{1}$.

Now, we choose an element $\theta_{1}^{\prime}\in\mathbb{R}^{n_{1}-1}$ such
that

$\displaystyle
P_{(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger}),X}=\bar{P}_{\theta_{\mathsf{a}}^{\prime},X}.$
(168)

Since we have

$\displaystyle
P_{(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger}),X}(n_{1})=e^{F_{{\cal
E},\mathsf{b}}(\theta_{(n_{1})}^{\dagger})-F_{{\cal
M}}(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger})},$
(169)

the relation
$P_{(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger}),X}(n_{1})=\bar{P}_{\theta_{\mathsf{a}}^{\prime},X}(n_{1})$
yields

$\displaystyle e^{F_{{\cal E},\mathsf{b}}(\theta_{(n_{1})}^{\dagger})-F_{{\cal
M}}(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger})}=e^{-F_{{\cal
E},\mathsf{a}}(\theta_{\mathsf{a}}^{\prime})}.$ (170)

For $x\neq n_{1}$, we have

$\displaystyle\bar{P}_{\theta_{\mathsf{a}}^{\prime},X}(x)=P_{(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger}),X}(x)=e^{\theta_{\mathsf{a}}^{x}+\theta_{\mathsf{a}}^{x,\dagger}+F_{{\cal
E},\mathsf{b}}(\theta_{(x)}^{\dagger})-F_{{\cal
M}}(\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger})}$
$\displaystyle\overset{(a)}{=}$ $\displaystyle
e^{\theta_{\mathsf{a}}^{x}+\theta_{\mathsf{a}}^{x,\dagger}+F_{{\cal
E},\mathsf{b}}(\theta_{(x)}^{\dagger})-F_{{\cal
E},\mathsf{b}}(\theta_{(n_{1})}^{\dagger})-F_{{\cal
E},\mathsf{a}}(\theta_{\mathsf{a}}^{\prime})}\overset{(b)}{=}e^{\theta_{\mathsf{a}}^{x}-F_{{\cal
E},\mathsf{a}}(\theta_{\mathsf{a}}^{\prime})},$ (171)

where $(a)$ and $(b)$ follow from (170) and the pair of (167) and the
definition of $\theta_{\mathsf{a}}^{x,\dagger}$, respectively. This relation
shows (165).

In the same way as the end of the previous subsection, we assume that the
distributions $\\{W_{x}\\}_{x}$ are linearly independent. Then, the rank of
$H$ is $n_{1}-1$. The combination of this fact and Lemma 13 guarantees

$\displaystyle\nabla^{(m)}[F_{{\cal
M}}^{*}](\eta_{\mathsf{a}})-\nabla^{(m)}[F_{{\cal
E},\mathsf{a}}^{*}](\eta_{\mathsf{a}})=\theta_{\mathsf{a}}+\theta_{\mathsf{a}}^{\dagger}-\theta_{\mathsf{a}}=\theta_{\mathsf{a}}^{\dagger},$
(172)

which implies Condition (B6+). We choose the parameter
$\theta_{\mathsf{b}}^{\ddagger}\in\mathbb{R}^{n_{2}-1}$ such that
$H\theta_{\mathsf{b}}^{\ddagger}=\theta_{\mathsf{a}}^{\dagger}$. We choose the
$(n_{2}-1)\times(n_{2}-n_{1})$ matrix $G$ such that $\mathop{\rm
Im}G=\mathop{\rm Ker}H$. Then, ${\cal E}_{2}$ and ${\cal M}_{2}$ defined in
(122) and (123) are written as

$\displaystyle{\cal E}_{\mathsf{b}}$
$\displaystyle=\\{\theta_{\mathsf{b}}^{\ddagger}+G\theta_{\mathsf{e}}|\theta_{\mathsf{e}}\in\mathbb{R}^{n_{2}-n_{1}}\\},$
(173) $\displaystyle{\cal M}_{\mathsf{b}}$
$\displaystyle=\\{\theta_{\mathsf{b}}\in\mathbb{R}^{n_{2}-1}|\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\theta_{2})G=0\\}.$ (174)

As explained in Subsection 4.7, the intersection ${\cal
E}_{\mathsf{b}}\cap{\cal M}_{\mathsf{b}}$ is composed of a unique element. As
the solution of the following minimization (175), we choose
$\theta_{\mathsf{e}}^{\ddagger}$ as

$\displaystyle\theta_{\mathsf{e}}^{\ddagger}:=\mathop{\rm
argmin}\limits_{\theta_{\mathsf{e}}\in\mathbb{R}^{n_{2}-n_{1}}}F_{{\cal
E},2}(\theta_{\mathsf{b}}^{\ddagger}+G\theta_{\mathsf{e}}),$ (175)

Then, we set
$\bar{\theta}_{\mathsf{b}}^{\ddagger}:=\theta_{\mathsf{b}}^{\ddagger}+G\theta_{\mathsf{e}}^{\ddagger}\in{\cal
E}_{\mathsf{b}}\cap{\cal M}_{\mathsf{b}}$. Then, we have the following
corollary of Theorem 4.7.

###### Corollary 7

When there exists $\theta_{\mathsf{a}}^{\ddagger}\in\mathbb{R}^{n_{1}-1}$ such
that $\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\bar{\theta}_{\mathsf{b}}^{\ddagger})=\nabla^{(e)}[F_{{\cal
E},\mathsf{a}}](\theta_{\mathsf{a}}^{\ddagger})H$, which is equivalent to

$\displaystyle
W\cdot\bar{P}_{\theta_{\mathsf{a}}^{\ddagger},X}=\bar{P}_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y},$
(176)

the maximizer in (164) is
$(\theta_{\mathsf{a}}^{\ddagger}+\theta_{\mathsf{a}}^{\dagger},{\theta}_{\mathsf{b}}^{\dagger})\in{\cal
M}$. When the above condition holds, the maximum (164) is

$\displaystyle
D(P_{(\theta_{\mathsf{a}}^{\ddagger}+\theta_{\mathsf{a}}^{\dagger},\theta_{\mathsf{b}}^{\dagger}),XY}\|\bar{P}_{\theta_{\mathsf{a}}^{\ddagger},X}\times\bar{P}_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y})=-H(W_{n_{1}})+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger}),$ (177)

The derivation of (177) follows from the following calculation.

$\displaystyle
D(W_{x}\|\bar{P}_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y})=\sum_{y}W_{x}(y)(\log
W_{x}(y)-\log\bar{P}_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y}(y))$
$\displaystyle=$
$\displaystyle-H(W_{x})-\sum_{y}W_{x}(y)(\sum_{j=1}^{n_{2}-1}\bar{\theta}^{n_{1}-1+j,\ddagger}f_{j}(y)-F_{{\cal
E},2}(\bar{\theta}_{\mathsf{b}}^{\ddagger}))$ $\displaystyle=$
$\displaystyle-H(W_{x})-\sum_{j=1}^{n_{2}-1}\bar{\theta}^{n_{1}-1+j,\ddagger}h_{x,j}+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger})$ $\displaystyle=$
$\displaystyle-H(W_{x})-\sum_{j=1}^{n_{2}-1}\theta^{n_{1}-1+j,\ddagger}h_{x,j}+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger})$ $\displaystyle=$
$\displaystyle-H(W_{x})-\theta^{x,\dagger}+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger})$ $\displaystyle=$
$\displaystyle-H(W_{x})-(-H(W_{x})+H(W_{n_{1}}))+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger})$ $\displaystyle=$
$\displaystyle-H(W_{n_{1}})+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger}).$ (178)

When $n_{1}=n_{2}$, we have $l=n_{1}-1=n_{2}-1$, which enables us to apply
Corollary 6. In this case, as another typical case, we can choose the
functions $f_{j}$ such that $(f_{j}(i))_{1\leq i,j\leq n_{2}-1}$ is the
inverse matrix of $(W_{i}(j))_{1\leq i,j\leq n_{2}-1}$. Under this choice,
$h_{i,j}$ is the identity matrix and the calculation of the maximization (129)
based on Corollary 6 is done by Algorithm 1 in the reference exact .
Therefore, the method based on Theorem 4.7 can be considered as a
generalization of Algorithm 1 in the reference exact . In addition, the above
discussion shows that Algorithm 1 in the reference exact  can be characterized
as finding the intersection of the exponential family ${\cal E}_{2}$ and the
mixture family ${\cal M}_{2}$, which is an information geometrical
characterization.

However, there is a case that no distribution $P_{X}$ on ${\mathcal{X}}$
satisfy (176) because there does not necessarily exist
$\theta_{\mathsf{a}}^{\ddagger}\in\mathbb{R}^{n_{1}-1}$ such that
$\nabla^{(e)}[F_{{\cal
E},\mathsf{b}}](\bar{\theta}_{\mathsf{b}}^{\ddagger})=\nabla^{(e)}[F_{{\cal
E},\mathsf{a}}](\theta_{\mathsf{a}}^{\ddagger})H$. In this case, instead of a
distribution on ${\mathcal{X}}$, there exists a function $f_{X}$ on
${\mathcal{X}}$ such that

$\displaystyle\sum_{x\in{\mathcal{X}}}f_{X}(x)W_{x}=\bar{P}_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y},~{}\sum_{x\in{\mathcal{X}}}f_{X}(x)=1.$
(179)

That is, the above function $f_{X}$ may take negative value(s). Also, in this
case, there does not exist the maximum in (164), and the maximum (129) is
achieved in the boundary of ${\mathcal{P}}_{\mathcal{X}}$. We denote the value
(177) by $\hat{C}({\mathcal{X}})$, define the subset

$\displaystyle{\cal N}({\mathcal{X}}):=\\{x\in{\mathcal{X}}|f_{X}(x)<0\\}.$
(180)

When ${\cal N}({\mathcal{X}})$ is the empty set, $\hat{C}({\mathcal{X}})$ is
the channel capacity.

Algorithm 5 Non-iterative algorithm for classical channel capacity in the
special case

Step 1: Set the parameters $h_{i,j}=\delta_{i,j}$ for $1\leq i\leq n_{1}-1$
and $1\leq j\leq n_{2}-1$, and $h_{n_{1},j}=0$ for $1\leq j\leq n_{2}-1$.
Choose $f_{1},\ldots,f_{n_{2}-1}$ such that
$h_{i,j}=\sum_{y}f_{j}(y)W_{i}(y)$. Here, we use Algorithm 6.

Step 2: Set the parameter $\theta^{i,\dagger}=-H(W_{i})+H(W_{n_{1}})$ for
$i=1,\ldots,n_{1}-1$.

Step 3: Define the function $F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}}):=\log\sum_{y}e^{\sum_{j=1}^{n_{2}-1}\theta_{\mathsf{b}}^{j}f_{j}(y)}$
for $\theta_{\mathsf{b}}\in\mathbb{R}^{n_{2}-1}$.

Step 4: Choose $\theta_{\mathsf{e}}^{\ddagger}\in\mathbb{R}^{n_{2}-n_{1}}$ as
$\displaystyle\theta_{\mathsf{e}}^{\ddagger}:=\mathop{\rm
argmin}\limits_{\theta_{\mathsf{e}}\in\mathbb{R}^{n_{2}-n_{1}}}F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{a}}^{\ddagger},\theta_{\mathsf{e}}).$ (181)

Step 5: Set
$\bar{\theta}_{\mathsf{b}}^{\ddagger}:=(\theta_{\mathsf{a}}^{\ddagger},\theta_{\mathsf{e}}^{\ddagger})\in{\cal
E}_{\mathsf{b}}\cap{\cal M}_{\mathsf{b}}$, and calculate
$P_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y}(y)$ by using (153).

Step 6: Calculate $P_{X}$ by solving
$\sum_{x}P_{X}(x)W_{x}(y)=P_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y}(y)$ with
the condition $\sum_{x}P_{X}(x)=1$. We output $-H(W_{n_{1}})+F_{{\cal
E},\mathsf{b}}(\bar{\theta}_{\mathsf{b}}^{\ddagger})$ and
$\\{x\in{\mathcal{X}}|P_{X}(x)<0\\}$ as $\hat{C}({\mathcal{X}})$ and ${\cal
N}({\mathcal{X}})$, respectively. In particular, if $P_{X}$ does not have a
negative component, $\hat{C}({\mathcal{X}})$ is the capacity.

Algorithm 6 Algorithm for finding $f_{1},\ldots,f_{n_{2}-1}$

Step 1: We reorder elements of ${\mathcal{Y}}$ such that vectors
$(W_{i}(y))_{y=1,\ldots,n_{1}-1}$ are linearly independent for
$i=1,\ldots,n_{1}-1$ and $W_{n_{1}}(n_{1})>0$.

Step 2: We denote the inverse matrix of
$(W_{i}(y)-\frac{W_{i}(n_{1})W_{n_{1}}(y)}{W_{n_{1}}(n_{1})})_{i,y=1,\ldots,n_{1}-1}$
by $c_{j,y}$, i.e.,
$\sum_{y=1}^{n_{1}-1}c_{j,y}(W_{i}(y)-\frac{W_{i}(n_{1})W_{n_{1}}(y)}{W_{n_{1}}(n_{1})})=\delta_{i,j}$.

Step 3: We set $f_{1},\ldots f_{n_{1}-1}$ as $f_{j}(y)=c_{j,y}$ for
$y=1,\ldots,n_{1}-1$,
$f_{j}(n_{1})=-\sum_{y=1}^{n_{1}-1}c_{j,y}\frac{W_{n_{1}}(y)}{W_{n_{1}}(n_{1})}$,
and $f_{j}(y)=0$ for $y=n_{1},\ldots,n_{2}$.

Step 4: We set $f_{n_{1}},\ldots,f_{n_{2}-1}$ as follows. We set
$f_{j}(y)=\delta_{j+1,y}$ for $j=n_{1},\ldots,n_{2}-1$ and
$y=n_{1},\ldots,n_{2}$. We choose $f_{j}(y)$ for $j=n_{1},\ldots,n_{2}-1$ and
$y=1,\ldots,n_{1}-1$ as follows.  $\displaystyle
f_{j}(y)=-\sum_{i=1}^{n_{1}-1}\hat{c}_{i,y}W_{i}(j+1),$ (182) where
$(\hat{c}_{i,y})_{i,j=1,\ldots,n_{1}-1}$ is the inverse matrix of
$(W_{i}(y))_{i,j=1,\ldots,n_{1}-1}$.

###  5.6 Algorithms for non-iterative method

Using Corollary 7, we have the following lemma.

###### Lemma 14

With the use of Algorithm 6, Algorithm 5 calculates $\hat{C}({\mathcal{X}})$
and ${\cal N}({\mathcal{X}})$.

###### Proof

In Algorithm 5, for a simple calculation, we set the parameters $h_{i,j}$ in
the way as Step 1. The choice of functions $f_{1},\ldots,f_{n_{2}-1}$ given in
Step 1 follows from (138). The choice of $\theta^{i,\dagger}$ given in Step 2
follows from Lemma 13. The choice of $F_{{\cal
E},\mathsf{b}}(\theta_{\mathsf{b}})$ given in Step 3 follows from (151). The
choice of $\theta_{\mathsf{e}}^{\ddagger}$ given in Step 4 follows from (175).
Then, Corollary 7 guarantees that the remaining part gives $\hat{C}({\cal X})$
and ${\cal N}({\cal X})$.

In addition, the output of Algorithm 6 satisfies the requirement of Step 1 of
Algorithm 5, whose reason is the following. For $i=1,\ldots,n_{1}$ and
$j=1,\ldots,n_{1}$, we have
$\sum_{y=1}^{n_{2}-1}f_{j}(y)W_{i}(y)=\sum_{y=1}^{n_{1}-1}f_{j}(y)W_{i}(y)+f_{j}(n_{1})W_{i}(n_{1})=\sum_{y=1}^{n_{1}-1}c_{j,y}W_{i}(y)-\sum_{y=1}^{n_{1}-1}c_{j,y}\frac{W_{n_{1}}(y)}{W_{n_{1}}(n_{1})}W_{i}(n_{1})=\delta_{i,j}$.
For $i=1,\ldots,n_{1}$ and $j=n_{1},\ldots,n_{2}-1$, we have
$\sum_{y=1}^{n_{2}-1}f_{j}(y)W_{i}(y)=\sum_{y=1}^{n_{1}-1}f_{j}(y)W_{i}(y)+W_{i}(j+1)=0$
due to (182). That is, the conditions in Step 1 of Algorithm 5 is satisfied.

Although Algorithm 5 contains the minimization (181), its objective function
has a simpler form as defined in Step 3 than the mutual information. Hence,
even when the number of free parameters is large, the minimization (181) can
be easily calculated.

Algorithm 1 in the reference exact  covers only the case when $n_{1}=n_{2}$
and ${\cal N}({\mathcal{X}})$ is the empty set. In this special case,
Algorithm 5 coincides with Algorithm 1 in the reference exact  while Step 4 of
Algorithm 5 is a trivial procedure in this case.

To see the case beyond Algorithm 1 in the reference exact , we study the case
when ${\cal N}({\mathcal{X}})$ is not the empty set. In this case, we need a
more complicated procedure. To handle this case, we expand the definitions of
$\hat{C}({\mathcal{X}})$ and ${\cal N}({\mathcal{X}})$. That is, we define
$\hat{C}({\mathcal{X}}_{0})$ and ${\cal N}({\mathcal{X}}_{0})$ for a subset
${\mathcal{X}}_{0}\subset{\mathcal{X}}$ in the same way, and they can be
calculated by Algorithm 5. In this case, Algorithm 7 gives an algorithm to
calculate the capacity.

In order to show this fact, we choose a subset
${\mathcal{X}}_{2,*}\subset{\mathcal{X}}_{2}$ as the support of the maximizer
$q^{2,*}\in{\mathcal{P}}_{{\mathcal{X}}_{2}}$ of (129) and denote the maximum
value (129) by $C({\mathcal{X}}_{2})$ when ${\mathcal{X}}_{2}$ is substituted
into ${\mathcal{X}}$. In particular, when ${\mathcal{X}}_{2}={\mathcal{X}}$,
we denote ${\mathcal{X}}_{2,*}$ and $q^{2,*}$ by ${\mathcal{X}}_{*}$ and
$q^{*}$, respectively. To show the correctness of Algorithm 7, we prepare the
following lemma.

###### Lemma 15

The relation

$\displaystyle({\mathcal{X}}_{2}\setminus{\mathcal{X}}_{2,*})\cap{\cal
N}({\mathcal{X}}_{2})\neq\emptyset$ (183)

holds for any subset ${\mathcal{X}}_{2}\subset{\mathcal{X}}$.

###### Proof

It is sufficient to show the desired statement for the case with
${\mathcal{X}}_{2}={\mathcal{X}}$. Hence, we assume the relation
${\mathcal{X}}_{2}={\mathcal{X}}$.

We define the mixture family ${\cal
M}:=\\{\sum_{x\in{\mathcal{X}}_{*}}f_{X}(x)W_{x}\in{\mathcal{P}}_{{\mathcal{Y}}}|\sum_{x\in{\mathcal{X}}_{*}}f_{X}(x)=1\\}$.
We denote the distribution $\bar{P}_{\bar{\theta}_{\mathsf{b}}^{\ddagger},Y}$
by $q^{**}$. Then, we obtain $\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}(q^{**})\in{\cal M}$. Pythagorean theorem (Proposition 1) guarantees the
relation

$\displaystyle D(W_{x}\|q^{*})=D(\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}(q_{**})\|q^{*})+D(W_{x}\|\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}(q^{**}))$ (184)

for $x\in X_{*}$. Since $D(W_{x}\|\mathop{\Gamma}\nolimits^{(e),F}_{{\cal
M}}(q^{**}))$ does not depend on $x\in X_{*}$,
$\mathop{\Gamma}\nolimits^{(e),F}_{{\cal M}}(q^{**})=q^{*}$. We choose the
generator $g$ of the exponential family ${\cal E}$ that connects $q^{**}$ and
$q^{*}$ as follows.

$\displaystyle
q^{**}(y)=q^{*}(y)e^{g(y)-C},\quad\sum_{y\in{\mathcal{Y}}}q^{*}(y)g(y)=0,$
(185)

where $C:=\log\sum_{y\in{\mathcal{Y}}}q^{*}(y)e^{g(y)}$. Hence, we have

$\displaystyle\sum_{y\in{\mathcal{Y}}}q^{**}(y)g(y)>0.$ (186)

We define the hyperplane ${\cal
M}_{c}:=\\{P\in{\mathcal{P}}_{\mathcal{Y}}|\sum_{y\in{\mathcal{Y}}}g(y)P(y)=c\\}$.
We denote the unique element of ${\cal M}_{c}\cap{\cal E}$ by $q_{c}$. Due to
(186), $q^{**}$ is written as $q_{t}$ with a positive number $t$.

Since this exponential family is orthogonal to ${\cal M}$,
$\sum_{y\in{\mathcal{Y}}}g(y)W_{x}(y)=0$ for any element $x\in X_{*}$, i.e.,
${\cal M}\subset{\cal M}_{0}$. For
$x\in{\mathcal{X}}\setminus{\mathcal{X}}_{*}$, we choose $c(x)$ such that
$W_{x}\in{\cal M}_{c(x)}$. Pythagorean theorem (Proposition 1) guarantees the
relation

$\displaystyle D(W_{x}\|q^{*})=D(q_{c(x)}\|q^{*})+D(W_{x}\|q_{c(x)})$ (187)

for $x\in{\mathcal{X}}\setminus X_{*}$. Since

$\displaystyle D(W_{x}\|q^{*})\leq
D(W_{x}\|q^{**})=D(q_{c(x)}\|q^{**})+D(W_{x}\|q_{c(x)}),$ (188)

we have $D(q_{c(x)}\|q_{0})=D(q_{c(x)}\|q^{*})\leq
D(q_{c(x)}\|q^{**})=D(q_{c(x)}\|q_{t})$. Hence, $c(x)<0$ because $t>0$.

Now, we write $q^{**}$ and $q^{*}$ as
$q^{**}=\sum_{x\in{\mathcal{X}}}v_{1}(x)W_{x}$ and
$q^{*}=\sum_{x\in{\mathcal{X}}_{*}}v_{2}(x)W_{x}$ by using a distribution
$v_{2}$ on ${\mathcal{X}}_{*}$ and a function $v_{1}$ with the condition
$\sum_{x\in{\mathcal{X}}}v_{1}(x)=1$. Using a function $v_{3}$, $q^{**}-q^{*}$
is written as

$\displaystyle q^{**}-q^{*}=\sum_{x\in{\mathcal{X}}}v_{3}(x)(W_{x}-q^{*})$
(189)

by using a function $v_{3}$. Since $c(x)<0$ for
$x\in{\mathcal{X}}\setminus{\mathcal{X}}_{*}$ and $c(x)=0$ for
$x\in{\mathcal{X}}_{*}$, there exists an element $x_{*}\in{\mathcal{X}}_{*}$
such that $v_{3}(x_{*})<0$. Hence,

$\displaystyle
q^{**}=q^{*}+\sum_{x\in{\mathcal{X}}}v_{3}(x)(W_{x}-q^{*})=\sum_{x\in{\mathcal{X}}}v_{3}(x)W_{x}+\Big{(}1-\sum_{x\in{\mathcal{X}}}v_{3}(x)\Big{)}q^{*}$
$\displaystyle=$
$\displaystyle\sum_{x\in{\mathcal{X}}}v_{3}(x)W_{x}+\Big{(}1-\sum_{x\in{\mathcal{X}}}v_{3}(x)\Big{)}\sum_{x\in{\mathcal{X}}_{*}}v_{2}(x)W_{x}$
$\displaystyle=$
$\displaystyle\sum_{x\in{\mathcal{X}}\setminus{\mathcal{X}}_{*}}v_{3}(x)W_{x}+\sum_{x\in{\mathcal{X}}_{*}}\Big{(}v_{3}(x)+\Big{(}1-\sum_{x\in{\mathcal{X}}}v_{3}(x)\Big{)}v_{2}(x)\Big{)}W_{x},$
(190)

which shows the desired statement.

The following lemma holds for Algorithm 7.

###### Lemma 16

${\mathcal{X}}_{*}$ is contained in one of sets
$\\{{\mathcal{X}}\setminus{\mathcal{X}}_{1}\\}_{{\mathcal{X}}_{1}\in{\cal
A}_{j}\cup{\cal B}^{j}}$ for any $j$. Hence, when ${\cal A}_{j}$ is empty,
${\mathcal{X}}_{*}$ is contained in one of sets
$\\{{\mathcal{X}}\setminus{\mathcal{X}}_{1}\\}_{{\mathcal{X}}_{1}\in{\cal
B}^{j}}$, i.e., ${\mathcal{X}}_{*}$ equals ${\mathcal{X}}\setminus\mathop{\rm
argmax}\limits_{{\mathcal{X}}_{1}\in{\cal
B}^{j}}\hat{C}({\mathcal{X}}\setminus{\mathcal{X}}_{1})$.

This lemma guarantees the correctness of Algorithm 7 for the calculation of
the capacity.

###### Proof

We show the desired statement by induction for $j$. For $j=1$, the desired
statement holds as follows. Due to Lemma 15, ${\mathcal{X}}_{*}$ is contained
in one of sets
$\\{{\mathcal{X}}\setminus{\mathcal{X}}_{1}\\}_{{\mathcal{X}}_{1}\in{\cal
A}_{1}}$.

We assume that ${\mathcal{X}}_{*}$ is contained in one of sets
$\\{{\mathcal{X}}\setminus{\mathcal{X}}_{1}\\}_{{\mathcal{X}}_{1}\in{\cal
A}_{k}\cup{\cal B}^{k}}$. If ${\mathcal{X}}_{*}$ is contained in one of sets
$\\{{\mathcal{X}}\setminus{\mathcal{X}}_{1}\\}_{{\mathcal{X}}_{1}\in{\cal
B}^{k}}$, the desired statement with $j=k+1$ holds. If ${\mathcal{X}}_{*}$ is
contained in one of sets
$\\{{\mathcal{X}}\setminus{\mathcal{X}}_{1}\\}_{{\mathcal{X}}_{1}\in{\cal
A}_{k}}$, we choose ${\mathcal{X}}_{1}\in{\cal A}_{k}$ such that
${\mathcal{X}}_{*}\subset{\mathcal{X}}\setminus{\mathcal{X}}_{1}$. Due to
Lemma 15, there exists an element $x\in{\cal
N}({\mathcal{X}}\setminus{\mathcal{X}}_{1})$ such that
${\mathcal{X}}_{*}\subset{\mathcal{X}}\setminus({\mathcal{X}}_{1}\cup\\{x\\})$.