∎ 11institutetext: Lehrstuhl für Theoretische Informationstechnik,
Technische Universität München,
Munich, Germany
11email: {boche, minglai.cai<EMAIL_ADDRESS>
# The broadcast classical-quantum capacity region of a two-phase bidirectional
relaying channel

Holger Boche  Minglai Cai  Christian Deppe

###### Abstract

We studied a three-node quantum network that enables bidirectional
communication between two nodes with a half-duplex relay node for transmitting
classical messages. A decode-and-forward protocol is used to perform the
communication in two phases. In the first phase, the messages of two nodes are
transmitted to the relay node. The capacity of the first phase is well-known
by previous works. In the second phase, the relay node broadcasts a re-encoded
composition to the two nodes. We determine the capacity region of the
broadcast phase. To the best of our knowledge, this is the first paper
analyzing quantum bidirectional relay networks.

###### Keywords:

Quantum information theory; Quantum network; Quantum relay channel; Quantum
broadcast channel

##  1 Introduction

The study of quantum channel networks has become more and more important in
the last few years.

Some of the first applications of this will be secret key
transmission/generation and transmitting of secure messages over quantum
networks. The capacities for secret key transmission/generation and the
secrecy capacities for message transmission have been determined in De  and
Ca/Wi/Ye .

For these applications, the transmitters have to solve two main problems.
First, the message (a secret key or a secure message) has to be encoded in
such a way that it can be decoded correctly by the legal receiver. Second, the
message has to be encoded such that the wiretapper’s knowledge of the
transmitted classical message can be kept arbitrarily small.

Transmission of secret keys and secure messages over long distances is an
essential requirement for those applications. Thus, in our paper, we consider
the problem how to ensure that the legal receivers are able to reproduce the
original messages. This is a necessary condition for reliable secret key
transmissions/generations and transmitting of secure messages over quantum
networks.

The problem of long-distance transmissions of quantum information is one of
the biggest problems in the realization of quantum networks. The sending of
photons in optical fibers is presently limited by 200 km because of losses in
the optical-fiber channel due to absorption on the way. One solution to solve
this problem is the development of quantum repeaters (cf. Br/Due/Ci/Zo  and
Ab/Br/Be/Ka/vLo/Br ). Unfortunately, the practical realization of this
component is not given until now. The researchers already built quantum
repeaters in their laboratories, but until now it is not possible to extend
the limit of 200 km.

In this paper, we use a relay instead of a quantum repeater. The advantage of
this protocol is that it is realizable and enables quantum communication
between two parties over the double length of the distance for sending photons
in optical fibers. This protocol can also be used for free space optical
communications between satellites. The communications in several classical
practical applications such as satellite communication and cellular
communication are modeled with channels with relay nodes. Channel networks
with relay nodes have been studied extensively in the context of classical
information theory (cf. Kr/Ga/Gu  and Co/Ga ). The study of quantum channels
with relay nodes has just recently begun (cf. Sa/Wi/Vu ).

We analyze a quantum channel network model which was introduced for classical
channel networks in Oech/Sch/Bj/Bo . It is called the two-phase bidirectional
relaying channel (Figure 1). In this model we consider a three-node quantum
network with two message sets $M_{1}$ and $M_{2}$, which is called a two-user
bidirectional quantum channel. The message $m_{2}\in M_{2}$ is located at node
$1$, and the message $m_{1}\in M_{1}$ is located at node $2$, respectively,
while a relay node enables the bidirectional communication between these
nodes. We assume that the relay node cannot transmit and receive data at the
same time. This is usually called a half-duplex relay. This assumption is
reasonable for practical components in communication systems in general.

Our goal is that after the transmission the message $m_{2}\in M_{2}$ is known
at node $2$ and the message $m_{1}\in M_{1}$ is known at node $1$,
respectively. We simplify the problem by assuming an a priori separation of
the communication into two phases.

Figure 1:  Two-phase bidirectional relaying channels

There exist several strategies which are usually classified by the process at
the relay node, namely the entanglement swapping-and-forward strategy (cf.
Ja/Pi/Fr ) and the decode-and-forward strategy. We consider a two-phase
decode-and-forward protocol. The relay node’s task is to decode the messages
that it receives in the first phase and to forward the information to its
destinations in the second phase. This basically means that in the first phase
the relay measures and decodes and that in the second phase the relay prepares
and encodes. The disadvantage of this strategy is that the coherence is
destroyed. The advantage of this strategy is that in the second phase each
receiver can use its own message from the first phase as side information to
gather a higher capacity.

The goal of the communication is the transmission of classical signals,
between two partners. The problem of the optimal transmission of these
classical signals can be divided into two parts:

  1. 1.

Quantum modulation (i.e., choosing an optimal set of possible input states
which will be the input alphabet. This is equivalent to consider a special
classical-quantum channel, i.e., a quantum channel depending on the set of
chosen input states whose sender’s inputs are classical variables.)

  2. 2.

Optimal coding for the classical-quantum channel.

We also consider this problem because the model of classical-quantum channels
is a very important tool for understanding the capacity formulas for quantum
channels. The capacity of classical-quantum channels has been determined in Ho
, Ho2 , and Sch/We . It turns out that classical-quantum channels are not only
of theoretical interest, but as well as of technical interest, too; for
instance, a code for a classical-quantum channel can be used for entanglement
generation (cf. De ). Furthermore, new phenomenons such as super-additivity
and super-activation appear for carrying classical information through a
quantum channel (cf. Bo/Ca/De ).

We would like to point out that the three-node bidirectional relay network is
an extremely advantageous tool in the relay network theory. The model of
classical three-node bidirectional relay network has been extended to more
complex models such as MIMO channels (Oech/Jo/Wy/Bo , Do/Oech/Sk , Wy/Oe/Bo ,
Oech/Wy/Bo ), Gaussian channels (Wy/Oe/Bo ), polar codes (An/Wy/Oe/Sk ), and
cross-layer designs (Oech/Bo , Oech/Bo2 , Oech/Bo3 ). In view of these
previous works on the classical bidirectional relay network, our further tasks
will be to analyze these models for quantum networks (cf. Is/Hi , Ei/Wo , and
Wil/Gu ).

For classical models, the authors of Oech/Sch/Bj/Bo  use results from coding
theory for degraded broadcast channel (cf. Ber ). One of our major challenges
in this paper is that there are no equivalent tools in the quantum information
theory yet. Thus, we can only establish the capacity region with average
errors, but not the capacity region with maximal errors as in the classical
case (cf. Remark 2). It still reminds open how the capacity region with
maximal errors can be established.

Recent research has been done toward security for classical bidirectional
relay networks (cf. Wy/Wi/Bo  and An/Wy/Oe/Sk ). It is a promising task to
find similar results for quantum networks.

Another important basic feature for classical bidirectional relay networks is
the channel uncertainty (Wy/Bj/Oe/Bo , Oech/Sk ). The capacity for quantum
channels with uncertainty has been determined in Ahl/Bli , Bj/Bo/Ja/No , and
Bo/Ca/De .

The design of communication protocols for quantum networks is a challenging
task. For the design of efficient protocols, it is important to incorporate
side information into the coding schemes. In this paper, we considered the
case where both receivers have side information about the messages. Bo/Ca/No
considered recently the case where the transmitter has side information about
the channel state. This corresponds to the classical “writing on dirty paper”
coding. This coding strategy plays an important role in modern communication
systems. It is an interesting research topic to develop on the basic of
Bo/Ca/No  and the bidirectional relaying protocol of this paper for more
complicated quantum networks.

The study of relay channels in the quantum scenario is novel. We hope our
results may raise interests in further analysis.

##  2 Basic definitions

###  2.1 A two-phase protocol

By the separation of the communication, we have a multiple-access phase, where
node $1$ and node $2$ transmit messages $m_{2}$ and $m_{1}$ to the relay node,
and a broadcast phase, where the relay forwards the messages to node $2$ and
node $1$, respectively. We look at the two phases separately.

Figure 2:  The multiple access phase

In the multiple-access phase, we have a classical-quantum multiple-access
channel. The multiple-access channel is a channel such that two (or more)
senders send information to a common receiver via this channel. The optimal
coding strategies and capacity regions for classical multiple-access channels
have been given in Ahl4  and Lia . The optimal coding strategies and capacity
regions for multiple-access quantum channels have been given in Win2  and
Ya/Ha/De2 .

Figure 3:  The broadcast phase

In the broadcast phase, we have a broadcast quantum channel. In a broadcast
channel, one single sender sends information to two (or more) receivers. The
optimal coding strategies and capacity regions for classical broadcast
channels have been given in Ma , Ber , and Ga . An optimal coding strategy and
a capacity region for broadcast quantum channels have been given in Sa/Wi .

For the broadcast phase, we assume that the relay node has successfully
decoded the messages $m_{1}$ and $m_{2}$ in the multiple-access phase. Of
course, the message $m_{2}$ is also known at node $1$ and the message $m_{2}$
is also known at node $2$.

The goal of the relay node is to broadcast a message to node $1$ and node $2$
which allows both nodes to recover the unknown source. This means that node
$1$ wants to recover message $m_{1}$ and that node $2$ wants to recover
message $m_{2}$.

###  2.2 Notations and communication scenarios

For finite-dimensional complex Hilbert spaces $G$ and $G^{\prime}$, a quantum
channel $N$: $\mathcal{S}(G)\rightarrow\mathcal{S}(G^{\prime})$,
$\mathcal{S}(G)\ni\rho\rightarrow N(\rho)\in\mathcal{S}(G^{\prime})$ is
represented by a completely positive trace-preserving map that accepts input
quantum states in $\mathcal{S}(G)$ and produces output quantum states in
$\mathcal{S}(G^{\prime})$. Here, $\mathcal{S}(G)$ stands for the space of
density operators on the space $G$.

If the sender wants to transmit a classical message of a finite set $A$ to the
receiver using a quantum channel $N$, his encoding procedure will include a
classical-to-quantum encoder to prepare a quantum message state
$\rho\in\mathcal{S}(G)$ suitable as an input for the channel. If the sender’s
encoding is restricted to transmit an indexed finite set of quantum states
$\\{\rho_{x}:x\in A\\}\subset\mathcal{S}(G)$, then we can consider the choice
of the signal quantum states $\rho_{x}$ as a component of the channel. Thus,
we obtain a channel $\sigma_{x}:=N(\rho_{x})$ with classical inputs $x\in A$
and quantum outputs, which we call a classical-quantum channel. This is a map
$\mathbf{N}$: $A\rightarrow\mathcal{S}(G^{\prime})$, $A\ni
x\rightarrow\mathbf{N}(x)\in\mathcal{S}(G^{\prime})$ which is represented by
the set of $|A|$ possible output quantum states
$\left\\{\sigma_{x}=\mathbf{N}(x):=N(\rho_{x}):x\in
A\right\\}\subset\mathcal{S}(G^{\prime})$, meaning that each classical input
of $x\in A$ leads to a distinct quantum output
$\sigma_{x}\in\mathcal{S}(G^{\prime})$. In view of this, we have the following
definition.

Let $H$ be a finite-dimensional complex Hilbert space. A classical-quantum
channel is a map $N:A\rightarrow\mathcal{S}(H)$, $A\ni a\rightarrow
N(a)\in\mathcal{S}(H)$.

For a probability distribution $P$ on a finite set $A$ and a positive constant
$\delta$, we denote the set of typical sequences by

$\mathcal{T}^{n}_{P,\delta}:=\left\\{x^{n}\in
A^{n}:\left|\frac{1}{n}\left\langle x^{n}\mid
a\right\rangle-P(a)\right|\leq\frac{\delta}{|A|}\right\\}\text{ ,}$

where $\left\langle x^{n}\mid a\right\rangle$ is the number of occurrences of
the symbol $a$ in the sequence $x^{n}$.

Let $n\in\mathbb{N}$, we define $A^{n}:=\\{(a_{1},\ldots,a_{n}):a_{i}\in
A\text{ }\forall i\in\\{1,\ldots,n\\}\\}$. The space which the vectors
$\\{v_{1}\otimes\ldots\otimes v_{n}:v_{i}\in H\text{ }\forall
i\in\\{1,\ldots,n\\}\\}$ span is defined by $H^{\otimes n}$. We also write
$a^{n}$ for the elements of $A^{n}$.

Associated with a classical quantum channel, $N$: $A\rightarrow\mathcal{S}(H)$
is the channel map on the $n$-block $N^{\otimes n}$:
$A^{n}\rightarrow\mathcal{S}({H}^{\otimes n})$ such that for
$a^{n}=(a_{1},\ldots,a_{n})\in A^{n}$. We have $N^{\otimes
n}(a^{n})=N(a_{1})\otimes\ldots\otimes N(a_{n})$.

For a quantum state $\rho\in\mathcal{S}(G)$, we denote the von Neumann entropy
of $\rho$ by

$S(\rho)=-\mathrm{tr}(\rho\log\rho)\text{ .}$

Let $\mathbf{V}$: $A\rightarrow\mathcal{S}(G)$ be a classical-quantum channel.
For $P\in P(A)$ the conditional entropy of the channel for $\mathbf{V}$ with
input distribution $P$ is denoted by

$S(\mathbf{V}|P):=\sum_{x\in A}P(x)S(\mathbf{V}(x))\text{ .}$

###### Remark 1

The following definition is a more general definition of the conditional
entropy in quantum information theory. Let $\mathfrak{P}$ and $\mathfrak{Q}$
be quantum systems. We denote the Hilbert space of $\mathfrak{P}$ and
$\mathfrak{Q}$ by $G^{\mathfrak{P}}$ and $G^{\mathfrak{Q}}$, respectively. Let
$\phi^{\mathfrak{PQ}}$ be a bipartite quantum state in
$\mathcal{S}(G^{\mathfrak{PQ}})$. We denote
$S(\mathfrak{P}\mid\mathfrak{Q})_{\rho}:=S(\phi^{\mathfrak{PQ}})-S(\phi^{\mathfrak{Q}})$.
Here $\phi^{\mathfrak{Q}}=\mathrm{tr}_{\mathfrak{P}}(\phi^{\mathfrak{PQ}})$.

Let $\varPhi:=\\{\rho_{x}:x\in A\\}$ be a set of quantum states labeled by
elements of $A$. For a probability distribution $P$ on $A$ the Holevo $\chi$
quantity is defined as

$\chi(P;\varPhi):=S\left(\sum_{x\in A}P(X)\rho_{x}\right)-\sum_{x\in
A}P(X)S\left(\rho_{x}\right)\text{ .}$

We denote the identity operator on a space $G$ by $\mathrm{id}_{G}$.

A collection of positive semi-definite operators $\\{M_{i}:i\\}$ on ${G}$ is
called a positive operator valued measure, or POVM, if it is a partition of
the identity, i.e., $\sum_{i}M_{i}=\mathrm{id}_{G}.$

###  2.3 Code concepts

A two-user multiple-access quantum channel $N_{BC-A}:H^{BC}\rightarrow H^{A}$
has two senders $B$ and $C$, and a single receiver $A$. It is defined as a map
$N:H^{BC}\rightarrow H^{A}$.

An $(n,J_{n}^{(1)},J_{n}^{(2)})$ code carrying classical information for a
two-user quantum multiple access channel $N_{BC-A}:H^{BC}\rightarrow H^{A}$
consists of a ensemble of quantum states
$\\{w(m_{1}):m_{1}=1,\ldots,J_{n}^{(1)}\\}\subset\mathcal{S}({H^{B}}^{\otimes
n})$, quantum states
$\\{v(m_{2}):m_{2}=1,\ldots,J_{n}^{(2)}\\}\subset\mathcal{S}({H^{C}}^{\otimes
n})$, and a POVM
$\biggl{\\{}D_{m_{1},m_{2}}:m_{1}\in\\{1,\ldots,J_{n}^{(1)}\\},m_{2}\in\\{1,\ldots,J_{n}^{(2)}\\}\biggr{\\}}$
on ${H^{A}}^{\otimes n}$.

A pair of nonnegative numbers $(R_{1},R_{2})$ is an achievable rate pair with
classical inputs for the quantum multiple-access channel
$N_{BC-A}:H^{BC}\rightarrow H^{A}$ with average error if for every positive
$\varepsilon$, $\delta$, and a sufficiently large $n$ there is an
$(n,J_{n}^{(1)},J_{n}^{(2)})$ code carrying classical information
$(\\{w(m_{1}):m_{1}=1,\ldots,J_{n}^{(1)}\\},$
$\\{v(m_{2}):m_{2}=1,\ldots,J_{n}^{(2)}\\},\\{D_{m_{1},m_{2}}:m_{1}\in\\{1,\ldots,J_{n}^{(1)}\\},$
$m_{2}\in\\{1,\ldots,J_{n}^{(2)}\\}\\})$ such that $\frac{1}{n}\log
J_{n}^{(1)}$ $\geq R_{1}-\delta$, $\frac{1}{n}\log J_{n}^{(2)}$ $\geq
R_{2}-\delta$ and

$\frac{1}{J_{n}^{(1)}J_{n}^{(2)}}\sum_{m_{1}=1}^{J_{n}^{(1)}}\sum_{m_{2}=1}^{J_{n}^{(2)}}\mathrm{tr}\left((\mathrm{id}_{{H^{A}}^{\otimes
n}}-D_{m_{1},m_{2}})N_{BC-A}^{\otimes
n}\left((w(m_{1}),v(m_{2}))\right)\right)\leq\varepsilon\text{ .}$ (1)

The two-user broadcast quantum channel $N_{A-BC}:H^{A}\rightarrow H^{BC}$ is a
quantum channel from a single sender $A$ to two independent receivers $B$ and
$C$. The quantum channel $W_{1}$ from $A$ to $B$ is obtained by tracing out
$C$ from the channel map, i.e., $W_{1}=N_{A-B}:H^{A}\rightarrow H^{B}$, which
is the quantum channel from $A$ to $B$, is defined as
$W_{1}(\sigma)=\mathrm{tr}_{C}(N_{A-BC}(\sigma))$. Furthermore,
$W_{2}=N_{A-C}:H^{A}\rightarrow H^{B}$, which is the quantum channel from $A$
to $C$, is defined as $W_{2}(\sigma)=\mathrm{tr}_{B}(N_{A-BC}(\sigma))$.

An $(n,J_{n}^{(1)},J_{n}^{(2)})$ code carrying classical information for a
two-user broadcast quantum channel $N_{A-BC}$: $H^{A}$ $\rightarrow$ $H^{BC}$
consists of a ensemble
$\\{w((m_{1},m_{2})):m_{1}=1,\ldots,J_{n}^{(1)},m_{2}=1,\ldots,J_{n}^{(2)}\\}$
$\subset$ $\mathcal{S}({A}^{\otimes n})$, a POVM
$\left\\{D_{m_{1}}^{(1)}:m_{1}\in\\{1,\ldots,J_{n}^{(1)}\\}\right\\}$ on
${H^{B}}^{\otimes n}$, and a POVM
$\left\\{D_{m_{2}}^{(2)}:m_{2}\in\\{1,\ldots,J_{n}^{(2)}\\}\right\\}$ on
${H^{C}}^{\otimes n}$.

A pair of nonnegative numbers $(R_{1},R_{2})$ is an achievable rate pair with
a classical input for the two-user broadcast quantum channel
$N_{A-BC}:H^{A}\rightarrow H^{BC}$ with average error if for every positive
$\varepsilon$, $\delta$, and a sufficiently large $n$ there is an
$(n,J_{n}^{(1)},J_{n}^{(2)})$ code carrying classical information
$(\\{w_{t}(j):j\\},\\{D_{j}:j\\})$ such that $\frac{1}{n}\log J_{n}^{(1)}\geq
R_{1}-\delta$, $\frac{1}{n}\log J_{n}^{(2)}\geq R_{2}-\delta$, for every
$m_{2}\in M_{2}$

$\frac{1}{J_{n}^{(1)}}\sum_{j=1}^{J_{n}^{(1)}}\mathrm{tr}\left((\mathrm{id}_{{H^{B}}^{\otimes
n}}-D_{m_{1}}^{(1)})W_{1}^{\otimes
n}\left(w((m_{1},m_{2}))\right)\right)\leq\varepsilon\text{ ,}$ (2)

and for every $m_{1}\in M_{1}$

$\frac{1}{J_{n}^{(2)}}\sum_{j=1}^{J_{n}^{(2)}}\mathrm{tr}\left((\mathrm{id}_{{H^{C}}^{\otimes
n}}-D_{m_{2}}^{(1)})W_{2}^{\otimes
n}\left(w((m_{1},m_{2}))\right)\right)\leq\varepsilon\text{ ,}$ (3)

where $W_{1}=N_{A-B}$ and $W_{2}=N_{A-C}$.

The capacity regions of multiple-access quantum channels and broadcast quantum
channels are convex by the time-sharing principle: Let $(R_{1},R_{2})$ and
$(R_{1}^{\prime},R_{2}^{\prime})$ be rate tuples of $m$ and $n$ block codes,
respectively, with error probabilities $\epsilon_{1}$ and $\epsilon_{2}$,
respectively. We get an $(m+n)$ block code with error probability at most
$\epsilon_{1}+\epsilon_{2}$ and with rates
$\left(\frac{m}{m+n}R_{1}+\frac{n}{m+n}R_{1}^{\prime},\frac{m}{m+n}R_{2}+\frac{n}{m+n}R_{2}^{\prime}\right)$
by concatenating the code words to $(m+n)$ blocks and tensoring the
corresponding decoding observables.

##  3 The classical-quantum capacity region of the bidirectional relaying
quantum channel

For the multiple-access phase, the optimal coding strategy is well known from
Win2 , where the following lemma for the classical-quantum rate region of
multiple-access quantum channels was given.

###### Lemma 1

Let $N_{Y_{2}Y_{1}-X}$ be a two-user multiple-access quantum channel. Let
$H^{Y_{1}}$ be the Hilbert space whose unit vectors correspond to the pure
states of node $1$’s quantum system, $H^{Y_{2}}$ be the Hilbert space whose
unit vectors correspond to the pure states of node $2$’s quantum system, and
$H^{X}$ be the Hilbert space whose unit vectors correspond to the pure states
of the relay node’s quantum system.

We assume node $1$’s encoding is restricted to transmitting an indexed finite
set of orthogonal quantum states $Y_{1}\subset H^{Y_{1}}$.

We assume node $2$’s encoding is restricted to transmitting an indexed finite
set of orthogonal quantum states $Y_{2}\subset H^{Y_{2}}$.

The classical-quantum capacity region of the multiple-access quantum channel
$N_{Y_{2}Y_{1}-X}$ with average error is given by the set of all rate pairs
$(R_{2},R_{1})$, satisfying

$R_{2}\leq\chi(Q_{1};\sigma^{X})\text{ ,}$ (4)
$R_{1}\leq\chi(Q_{2};\sigma^{X})\text{ ,}$ (5)

and

$R_{2}+R_{1}\leq\chi(Q_{1,2};\sigma^{X})$ (6)

for any joint probability distribution $Q_{1,2}$ on $Y_{1}\times Y_{2}$. Here,
$Q_{1}$ is the marginal probability distribution of $Q_{1,2}$ on $Y_{1}$,
$Q_{2}$ is the marginal probability distribution of $Q_{1,2}$ on $Y_{2}$, and
$\sigma^{X}$ is the resulting quantum state at the outcome of the relay node.

Thus, if $n$ is sufficiently large and if for $M_{1}$ and $M_{2}$ it holds

$|M_{2}|\leq\lfloor 2^{n(\chi(Q_{1};\sigma^{X})-\epsilon)}\rfloor\text{ ,}$
$|M_{1}|\leq\lfloor 2^{n(\chi(Q_{2};\sigma^{X})-\epsilon)}\rfloor\text{ ,}$

and

$|M_{2}|+|M_{1}|\leq\lfloor
2^{n(\chi(Q_{1,2};\sigma^{X})-\epsilon)}\rfloor\text{ }$

for some positive $\epsilon$, we can assume that the relay node has
successfully decoded the messages $m_{1}\in M_{1}$ and $m_{2}\in M_{2}$.

Note that the author of Win2 , using block codes and showing a weak converse,
is able to give (4), (5), and (6) in single letter formula. Please see
Bo/Ca/No  for more discussions on the value of multiletter formulas for
quantum communication networks.

For the broadcast phase, since each node has perfect knowledge about the
message intended for the other, one can use this knowledge as a support for
the choice of the decoding strategy to decode the message intended for itself.
In view of these facts, we have the following Theorem 3.1.

###### Theorem 3.1

Let $N$ be a two-user bidirectional quantum channel. Let $H^{Y_{1}}$ be the
Hilbert space whose unit vectors correspond to the pure states of node $1$’s
quantum system, $H^{Y_{2}}$ be the Hilbert space whose unit vectors correspond
to the pure states of node $2$’s quantum system, and $H^{X}$ be the Hilbert
space whose unit vectors correspond to the pure states of the relay node’s
quantum system. Let $N_{X-Y_{1}Y_{2}}$ be the broadcast quantum channel in the
broadcast phase.

We assume that the relay node’s encoding is restricted to transmitting an
indexed finite set of orthogonal quantum states $\\{\phi_{x}:x\in X\\}\subset
H^{X}$.

For all probability distribution $P$ on $X$, the capacity region of the
bidirectional broadcast quantum channel $N_{X-Y_{1}Y_{2}}$ during the
broadcast phase for transmitting classical information with average error is
given by the set of all rate pairs $(R_{1},R_{2})$, satisfying

$R_{1}\leq\limsup_{n\rightarrow\infty}\frac{1}{n}\chi(P^{n};{\sigma^{Y_{1}}}^{\otimes
n})\text{ }$ (7)

and

$R_{2}\leq\limsup_{n\rightarrow\infty}\frac{1}{n}\chi(P^{n};{\sigma^{Y_{2}}}^{\otimes
n})\text{ .}$ (8)

Here, $\sigma^{Y_{1}}$ is the resulting quantum state at the outcome of node
$1$, while $\sigma^{Y_{2}}$ is the resulting quantum state at the outcome of
node $2$.

###### Proof

It is easy to verify that every achievable rate pair cannot exceed (7) and
(8). $R_{1}$ cannot exceed
$\limsup_{n\rightarrow\infty}\frac{1}{n}\chi(P^{n};{\sigma^{Y_{1}}}^{\otimes
n})$, even if the relay node only sends a message to node $1$ without sending
any message to node $2$ (cf. Ho2 ). For the same reason, $R_{2}$ cannot exceed
$\limsup_{n\rightarrow\infty}\frac{1}{n}\chi(P^{n};{\sigma^{Y_{2}}}^{\otimes
n})$ either. Now we will prove the achievability of the extremal point of the
rate region given by (7) and (8), since then every rate pair in the rate
region is achievable by the time-sharing principle.

At first, we present some tools which that were used for our proof:

Let $H$ be a Hilbert space. For $\rho\in\mathcal{S}(H)$ and $\alpha>0$ there
exists an orthogonal subspace projector $\Pi_{\rho,\alpha}$ commuting with
$\rho^{\otimes n}$ and satisfying

$\mathrm{tr}\left(\rho^{\otimes n}\Pi_{\rho,\alpha}\right)\geq
1-\frac{d}{4n\alpha^{2}}\text{ ,}$ (9)
$\mathrm{tr}\left(\Pi_{\rho,\alpha}\right)\leq
2^{nS(\rho)+Kd\alpha\sqrt{n}}\text{ ,}$ (10)
$\Pi_{\rho,\alpha}\cdot\rho^{\otimes n}\cdot\Pi_{\rho,\alpha}\leq
2^{-nS(\rho)+Kd\alpha\sqrt{n}}\Pi_{\rho,\alpha}\text{ ,}$ (11)

where $d:=\dim H$ and $K$ is a positive constant (cf. Wil ).
Let $A$ be a finite set and let $\mathbf{V}:A\rightarrow\mathcal{S}(H)$ be a
classical-quantum channel. For a probability distribution $P$ on $A$,
$\alpha>0$, and $x^{n}\in\mathcal{T}^{n}_{P}$ there exists an orthogonal
subspace projector $\Pi_{\mathbf{V},\alpha}(x^{n})$ commuting with
$\mathbf{V}^{\otimes n}_{x^{n}}$ and satisfying

$\mathrm{tr}\left(\mathbf{V}^{\otimes
n}(x^{n})\Pi_{\mathbf{V},\alpha}(x^{n})\right)\geq
1-\frac{ad}{4n\alpha^{2}}\text{ ,}$ (12)
$\mathrm{tr}\left(\Pi_{\mathbf{V},\alpha}(x^{n})\right)\leq
2^{nS(\mathbf{V}|P)+Kad\alpha\sqrt{n}}\text{ ,}$ (13)
$\displaystyle\Pi_{\mathbf{V},\alpha}(x^{n})\cdot\mathbf{V}^{\otimes
n}(x^{n})\cdot\Pi_{\mathbf{V},\alpha}(x^{n})$ $\displaystyle\leq
2^{-nS(\mathbf{V}|P)+Kad\alpha\sqrt{n}}\Pi_{\mathbf{V},\alpha}(x^{n})\text{
,}$ (14)

where $a:=\\#\\{A\\}$ and $K$ is a positive constant (cf. Wil ).
Let $\mathbf{V}:A\rightarrow\mathcal{S}(H)$ be a classical-quantum channel.
Then, every probability distribution $P$ on $A$ defines a quantum state
$P\mathbf{V}$ on $\mathcal{S}(H)$, which is the resulting quantum state at the
output of $\mathbf{V}$ when the input is sent according to $P$. Thus, for
$\alpha^{\prime}>0$ we can define an orthogonal subspace projector
$\Pi_{P\mathbf{V},\alpha^{\prime}\sqrt{a}}$ which fulfills (9), (10), and (11)
(here, we set $\rho=P\mathbf{V}$ and $\alpha=\alpha^{\prime}\sqrt{a}$).
Furthermore, for $\Pi_{P\mathbf{V},\alpha^{\prime}\sqrt{a}}$, we have the
following inequality

$\mathrm{tr}\left(\mathbf{V}^{\otimes
n}(x^{n})\cdot\Pi_{P\mathbf{V},\alpha^{\prime}\sqrt{a}}\right)\geq
1-\frac{ad}{4n\alpha^{2}}\text{ ,}$ (15)

where $K$ is a positive constant (cf. Wil ).

######  Lemma 2 (Measurement on Approximately Close States, cf. Wil )

Let $\sigma$ and $\rho$ be two quantum states, and let $\Pi$ be a positive
operator such that $\Pi\leq\mathrm{id}$; then,

$\mathrm{tr}(\Pi\sigma)\geq\mathrm{tr}(\Pi\rho)-\|\sigma-\rho\|_{1}\text{ .}$

######  Lemma 3 (Tender Operator, cf. Win  and Og/Na )

Let $\rho$ be a quantum state. Let $X$ be a positive operator such that
$X\leq\mathrm{id}$ and $1-\mathrm{tr}(\rho X)\leq\lambda\leq 1$; then,

$\|\rho-\sqrt{X}\rho\sqrt{X}\|\leq\sqrt{8\lambda}\text{ .}$ (16)

######  Lemma 4 (Hayashi-Nagaoka Operator Inequality, cf. Ha/Na )

For any positive operators $S$ and $T$ such that $S\leq\mathrm{id}$ we have

$\mathrm{id}-(S+T)^{-\frac{1}{2}}S(S+T)^{-\frac{1}{2}}\leq(\mathrm{id}-S)+4T\text{
.}$ (17)

The random encoding technique:

We denote $W_{1}=N_{X-Y_{1}}$ and $W_{2}=N_{X-Y_{2}}$. For any positive
$\epsilon$ let ${M^{\prime}}_{1}$ be a message set such that
$|{M^{\prime}}_{1}|\leq 2^{n(\chi(P;\sigma^{Y_{1}})-2\epsilon)}$, and let
${M^{\prime}}_{2}$ be a message set such that $|{M^{\prime}}_{2}|\leq
2^{n(\chi(P;\sigma^{Y_{2}})-2\epsilon)}$. We generate
$|{M^{\prime}}_{1}||{M^{\prime}}_{2}|$ independent random variables

$\left\\{X^{n}({m}_{1},{m}_{2}):{m}_{1}\in{M^{\prime}}_{1},{m}_{2}\in{M^{\prime}}_{2}\right\\}$

taking values in $\mathcal{T}^{n}_{P}$ i.i.d. according to the product
distribution $P(x^{n})=\prod_{i=1}^{n}P(x_{i})$.

For all $x^{n}$ $\in X^{n}$ we define $\Pi_{PW_{1},\alpha\sqrt{a}}$ on
${H^{Y_{1}}}^{\otimes n}$, $\Pi_{PW_{2},\alpha\sqrt{a}}$ on
${H^{Y_{2}}}^{\otimes n}$, $\Pi_{W_{1}^{\otimes n}(x^{n}),\alpha}$ on
${H^{Y_{1}}}^{\otimes n}$, and $\Pi_{W_{2}^{\otimes n}(x^{n}),\alpha}$ on
${H^{Y_{2}}}^{\otimes n}$ as in (12), (13), (14), and (15). Here, we set
$P=P$, $\mathbf{V}=W_{1}$, and $=W_{2}$, respectively. $\alpha$ is some
positive constant which we will choose later. We define

${D^{\prime}}^{(1)}_{x^{n}}:=\Pi_{PW_{1},\alpha\sqrt{a}}\Pi_{W_{1}^{\otimes
n}(x^{n}),\alpha}\Pi_{PW_{1},\alpha\sqrt{a}}\text{ ,}$

and

${D^{\prime}}^{(2)}_{x^{n}}:=\Pi_{PW_{2},\alpha\sqrt{a}}\Pi_{W_{2}^{\otimes
n}(x^{n}),\alpha}\Pi_{PW_{1},\alpha\sqrt{a}}\text{ .}$

Analysis of errors of the first kind:

We say an error of the first kind occurs if $(m_{1},m_{2})$ has been send by
the relay node, and either node $1$ fails to decode $m_{1}$ or node $2$ fails
to decode $m_{2}$.

For all $(m_{1},m_{2})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$ and any
realization $x^{n}(m_{1},m_{2})$ of $X^{n}(m_{1},m_{2})$ we have

$\displaystyle\mathrm{tr}\left(W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2})){D^{\prime}}_{x^{n}(m_{1},m_{2})}^{(1)}\right)\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{(}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\Pi_{PW_{1},\alpha\sqrt{a}}\Pi_{W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2})),\alpha}\Pi_{PW_{1},\alpha\sqrt{a}}\Bigr{)}\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{(}(\Pi_{PW_{1},\alpha\sqrt{a}}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\Pi_{PW_{1},\alpha\sqrt{a}})\Pi_{W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2})),\alpha}\Bigr{)}\allowdisplaybreaks$
$\displaystyle\geq\mathrm{tr}\Bigl{(}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\Pi_{W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2})),\alpha}\Bigr{)}$
$\displaystyle-\left\|\Pi_{PW_{1},\alpha\sqrt{a}}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\Pi_{PW_{1},\alpha\sqrt{a}}-W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right\|_{1}\allowdisplaybreaks$ $\displaystyle\geq
1-\frac{d}{4n\alpha^{2}}\mathrm{tr}\Bigl{(}\Pi_{W^{\otimes
n}(x^{n}(m_{1},m_{2})),\alpha}\Bigr{)}$
$\displaystyle-\left\|\Pi_{PW_{1},\alpha\sqrt{a}}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\Pi_{PW_{1},\alpha\sqrt{a}}-W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right\|_{1}\allowdisplaybreaks$ $\displaystyle\geq
1-\frac{d}{4n\alpha^{2}}-\sqrt{8\frac{ad}{4n\alpha^{2}}}\text{ .}$ (18)

The first inequality holds because of Lemma 2, the second inequality holds
because of (12), and the third inequality holds because of Lemma 3 and (15).

Similarly, we have

$\mathrm{tr}\left(W_{2}^{\otimes
n}(x^{n}(m_{1},m_{2})){D^{\prime}}_{x^{n}(m_{1},m_{2})}^{(2)}\right)\geq
1-\frac{d}{4n\alpha^{2}}-\sqrt{8\frac{ad}{4n\alpha^{2}}}\text{ .}$ (19)

Thus, the errors of the first kind go to zero if $n$ is sufficiently large.

Analysis of errors of the second kind:

We define $\rho_{2}:=PW_{2}=\sum_{x\in X}P(X)W_{2}(\phi_{x})$; then,
$\rho^{Y_{2}}=\rho_{2}$ if any realization of $X^{n}$ is used to decode the
input message. Let us fix $(m_{1},m_{2})$,
$(m_{1},m_{2}^{\prime})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$ such that
$m_{2}\not=m_{2}^{\prime}$. Node $2$ would make an error if $(m_{1},m_{2})$
has been sent, but node $2$’s decoding results in the message
$m_{2}^{\prime}$. We call it an error of the second kind. We now consider the
expected value of the probability of this case, if we use the random encoder
$X^{n}$ to decode the input message. We have

$\displaystyle E\left[\mathrm{tr}\left(W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2})){D^{\prime}}_{X^{n}(m_{1},m_{2}^{\prime})}^{(2)}\right)\right]\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\left[E\left(W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\cdot
E\left({D^{\prime}}_{X^{n}(m_{1},m_{2}^{\prime})}^{(2)}\right)\right]\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{[}\rho_{2}^{\otimes
n}E\left({D^{\prime}}_{X^{n}(m_{1},m_{2}^{\prime})}^{(2)}\right)\Bigr{]}\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{[}\rho_{2}^{\otimes
n}E\left(\Pi_{PW_{2},\alpha\sqrt{a}}\Pi_{W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}^{\prime})),\alpha}\Pi_{PW_{2},\alpha\sqrt{a}}\right)\Bigr{]}\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{[}E\left(\rho_{2}^{\otimes
n}\Pi_{PW_{2},\alpha\sqrt{a}}\Pi_{W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}^{\prime})),\alpha}\Pi_{PW_{2},\alpha\sqrt{a}}\right)\Bigr{]}\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{[}E\left((\Pi_{PW_{2},\alpha\sqrt{a}}\rho_{2}^{\otimes
n}\Pi_{PW_{2},\alpha\sqrt{a}})\Pi_{W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}^{\prime})),\alpha}\right)\Bigr{]}\allowdisplaybreaks$
$\displaystyle=\mathrm{tr}\Bigl{[}(\Pi_{PW_{2},\alpha\sqrt{a}}\rho_{2}^{\otimes
n}\Pi_{PW_{2},\alpha\sqrt{a}})E\left(\Pi_{W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}^{\prime})),\alpha}\right)\Bigr{]}\allowdisplaybreaks$
$\displaystyle\leq
2^{-n[S(\rho_{2})-\frac{1}{2}\epsilon]}\mathrm{tr}\Bigl{[}\Pi_{PW_{2},\alpha\sqrt{a}}E\left(\Pi_{W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}^{\prime})),\alpha}\right)\Bigr{]}\allowdisplaybreaks$
$\displaystyle\leq 2^{n[\sum_{x\in
X}P(X)S(W_{2}(\phi_{x}))-\frac{1}{2}\epsilon]}2^{-n[S(\rho_{2})-\frac{1}{2}\epsilon]}\mathrm{tr}\Bigl{[}\Pi_{PW_{2},\alpha\sqrt{a}}\Bigr{]}\allowdisplaybreaks$
$\displaystyle=2^{-n[\sum_{x\in X}P(X)S(W_{2}(\phi_{x}))-S(\sum_{x\in
X}P(X)W_{2}(\phi_{x}))-\epsilon]}\mathrm{tr}\Bigl{[}\Pi_{PW_{2},\alpha\sqrt{a}}\Bigr{]}\allowdisplaybreaks$
$\displaystyle=2^{-n[\chi(P,\rho^{Y_{2}})-\epsilon]}\mathrm{tr}\Bigl{[}\Pi_{PW_{2},\alpha\sqrt{a}}\Bigr{]}\allowdisplaybreaks$
$\displaystyle\leq 2^{-n[\chi(P,\rho^{Y_{2}})-\epsilon]}\text{ .}$ (20)

The first equality hold because $X^{n}(m_{1},m_{2})$ and
$X^{n}(m_{1},m_{2}^{\prime})$ are independent, the first inequality holds
because of (11), and the second inequality holds because of (13).

Similarly, let us fix $(m_{1}^{\prime},m_{2})$,
$(m_{1},m_{2})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$ such that
$m_{1}\not=m_{1}^{\prime}$. Node $1$ would make an error (of the second kind)
if $(m_{1},m_{2})$ has been sent, but node $1$’s decoding results in the
message $m_{1}^{\prime}$. We now consider the expected value of the
probability of this case if we use the random encoder $X^{n}$ to decode the
input message. We have

$E\left[\mathrm{tr}\left(W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2})){D^{\prime}}_{X^{n}(m_{1},m_{2}^{\prime})^{(1)}}\right)\right]\leq
2^{-n[\chi(P,\rho^{Y_{1}})-\epsilon]}\text{ .}$ (21)

Thus, the errors of the second kind go to zero if $n$ is sufficiently large.

Definition of the code:

For all $(m_{1},m_{2})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$ we define

$D^{(1)}_{X^{n}(m_{1},m_{2})}:=\left(\sqrt{\sum_{m_{1}^{*}\in{M^{\prime}}_{1}}{D^{\prime}}^{(1)}_{X^{n}(m_{1}^{*},m_{2})}}\right)^{-1}{D^{\prime}}^{(1)}_{X^{n}(m_{1},m_{2})}\left(\sqrt{\sum_{m_{1}^{*}\in{M^{\prime}}_{1}}{D^{\prime}}^{(1)}_{X^{n}(m_{1}^{*},m_{2})}}\right)^{-1}\text{
,}$

and

$D^{(2)}_{X^{n}(m_{1},m_{2})}:=\left(\sqrt{\sum_{m_{2}^{*}\in{M^{\prime}}_{2}}{D^{\prime}}^{(2)}_{X^{n}(m_{1},m_{2}^{*})}}\right)^{-1}{D^{\prime}}^{(2)}_{X^{n}(m_{1},m_{2})}\left(\sqrt{\sum_{m_{2}^{*}\in{M^{\prime}}_{2}}{D^{\prime}}^{(2)}_{X^{n}(m_{1},m_{2}^{*})}}\right)^{-1}\text{
,}$

which depends on the random outcome of $X^{n}$. By construction, for any
realization
$\\{x^{n}(m_{1},m_{2}):m_{1}\in{M^{\prime}}_{1},m_{2}\in{M^{\prime}}_{2}\\}$
of
$\\{X^{n}(m_{1},m_{2}):m_{1}\in{M^{\prime}}_{1},m_{2}\in{M^{\prime}}_{2}\\}$
we have for every $m_{1}\in{M^{\prime}}_{1}$,

$\sum_{m_{1}\in{M^{\prime}}_{1}}D^{(1)}_{x^{n}(m_{1},m_{2})}\leq\mathrm{id}_{{H^{B}}^{\otimes
n}}\text{ ,}$

and for every $m_{2}\in{M^{\prime}}_{2}$

$\sum_{m_{2}\in
M_{2}}D^{(2)}_{x^{n}(m_{1},m_{2})}\leq\mathrm{id}_{{H^{C}}^{\otimes n}}\text{
.}$

We combine (18) and (20), for all
$(m_{1},m_{2})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$ we have

$\displaystyle
E\left[\mathrm{tr}\left(D^{(1)}_{X^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\allowdisplaybreaks$ $\displaystyle\geq
E\left[\mathrm{tr}\left({D^{\prime}}^{(1)}_{X^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\allowdisplaybreaks$
$\displaystyle-4E\left[\mathrm{tr}\left(\sum_{m_{1}^{*}\not=m_{1}}{D^{\prime}}^{(1)}_{X^{n}(m_{1}^{*},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\allowdisplaybreaks$ $\displaystyle\geq
1-\frac{d}{4n\alpha^{2}}-\sqrt{8\frac{ad}{4n\alpha^{2}}}\allowdisplaybreaks$
$\displaystyle-4E\left[\mathrm{tr}\left(\sum_{m_{1}^{*}\not=m_{1}}{D^{\prime}}^{(1)}_{X^{n}(m_{1}^{*},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\allowdisplaybreaks$ $\displaystyle\geq
1-\frac{d}{4n\alpha^{2}}-\sqrt{8\frac{ad}{4n\alpha^{2}}}-4|{M^{\prime}}_{1}|2^{-n[\chi(P,\sigma^{Y_{1}})-\epsilon]}\allowdisplaybreaks$
$\displaystyle\geq
1-\frac{d}{4n\alpha^{2}}-\sqrt{8\frac{ad}{4n\alpha^{2}}}-2^{-n\epsilon}\text{
.}$ (22)

The first inequity holds because of Lemma 4.

Similarly, if we combine (18) and (21), we have for all
$(m_{1},m_{2})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$

$E\left[\mathrm{tr}\left(D^{(2)}_{X^{n}(m_{1},m_{2})}W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\geq
1-\frac{d}{4n\alpha^{2}}-\sqrt{8\frac{ad}{4n\alpha^{2}}}-2^{-n\epsilon}\text{
.}$ (23)

Since (22) and (23) hold for all
$(m_{1},m_{2})\in{M^{\prime}}_{1}\times{M^{\prime}}_{2}$, for any positive
$\omega$, choosing a suitable $\alpha$, if $n$ is sufficiently large, we have

$\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}E\left[\mathrm{tr}\left(D^{(1)}_{X^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\geq 1-\omega\text{ }$

and

$\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}E\left[\mathrm{tr}\left(D^{(2)}_{X^{n}(m_{1},m_{2})}W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\right]\geq 1-\omega\text{ .}$

By the law of large numbers, if $n$ is sufficiently large, for any positive
$\delta$ and $\gamma$, we have

$p\left\\{\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(1)}_{X^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\geq 1-\delta\right\\}\geq 1-\gamma\text{ }$

and

$p\left\\{\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(2)}_{X^{n}(m_{1},m_{2})}W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\geq 1-\delta\right\\}\geq 1-\gamma\text{ .}$

Thus,

$\displaystyle
p\Bigl{\\{}\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(1)}_{X^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\geq 1-\delta\text{ and }$
$\displaystyle\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(2)}_{X^{n}(m_{1},m_{2})}W_{2}^{\otimes
n}(X^{n}(m_{1},m_{2}))\right)\geq 1-\delta\Bigr{\\}}$ $\displaystyle\geq
1-2\gamma\text{ .}$

If $n$ is sufficiently large, with a positive probability, we can find a
realization $x^{n}(m_{1},m_{2})$ of $X^{n}(m_{1},m_{2})$ such that

$\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(1)}_{x^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)\geq 1-\delta\text{ ,}$

and

$\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(2)}_{x^{n}(m_{1},m_{2})}W_{2}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)\geq 1-\delta\text{ .}$

Definition of the message sets:

Assume

$\displaystyle\biggl{\lvert}\Bigl{\\{}m_{2}\in{M^{\prime}}_{2}:\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(1)}_{x^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)<1-2\delta\Bigr{\\}}\biggr{\rvert}$
$\displaystyle>\frac{1}{2}|{M^{\prime}}_{2}|\text{ .}$

We have in this case,

$\sum_{m_{1}\in{M^{\prime}}_{1}}\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{1}||{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(1)}_{x^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)<1-\delta\text{ ,}$

but this is a contradiction to the result above.

Thus, there exists a set $M_{2}\in{M^{\prime}}_{2}$ such that
$|M_{2}|=\lceil\frac{1}{2}|{M^{\prime}}_{2}|\rceil$ and for every $m_{2}\in
M_{2}$ we have

$\sum_{m_{1}\in{M^{\prime}}_{1}}\frac{1}{|{M^{\prime}}_{1}|}\mathrm{tr}\left(D^{(1)}_{x^{n}(m_{1},m_{2})}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)\geq 1-2\delta\text{ .}$ (24)

Similarly, there exists a set $M_{1}\in{M^{\prime}}_{1}$ such that
$|M_{1}|=\lceil\frac{1}{2}|{M^{\prime}}_{1}|\rceil$ and for every $m_{1}\in
M_{1}$ we have

$\sum_{m_{2}\in{M^{\prime}}_{2}}\frac{1}{|{M^{\prime}}_{2}|}\mathrm{tr}\left(D^{(2)}_{x^{n}(m_{1},m_{2})}W_{2}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)\geq 1-2\delta\text{ .}$ (25)

For every $(m_{1},m_{2})\in M_{1}\times M_{2}$, we define

$w((m_{1},m_{2})):=x^{n}(m_{1},m_{2})\text{ ,}$ (26)
$D^{(m_{1})}_{m_{2}}:=D^{(1)}_{x^{n}(m_{1},m_{2})}\text{ ,}$ (27)

and

$D^{(m_{2})}_{m_{1}}:=D^{(2)}_{x^{n}(m_{1},m_{2})}\text{ .}$ (28)

$\\{D^{(m_{2})}_{m_{1}}:m_{1}\in M_{1}\\}$ is less or equal to the partition
of the identity for every $m_{2}\in M_{2}$. $\\{D^{(m_{1})}_{m_{2}}:m_{2}\in
M_{2}\\}$ is less or equal to the partition of the identity for every
$m_{1}\in M_{1}$.

Since node $1$ already knows the message $m_{2}\in M_{2}$, it chooses the
corresponding decoding set

$\left\\{D^{(m_{2})}_{m}:m\in M_{1}\right\\}$

to decode $m_{1}\in M_{1}$. Since node $2$ already knows the message $m_{1}\in
M_{1}$, it chooses the corresponding decoding set

$\left\\{D^{(m_{1})}_{m}:m\in M_{2}\right\\}$

to decode $m_{2}\in M_{2}$.

By (24) and (25), for every $m_{2}\in M_{2}$ we have

$\sum_{m_{1}\in{M}_{1}}\frac{1}{|{M}_{1}|}\mathrm{tr}\left(D^{(m_{2})}_{m_{1}}W_{1}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)\geq 1-4\delta\text{ ,}$ (29)

and for every $m_{1}\in M_{1}$ we have

$\sum_{m_{2}\in{M}_{2}}\frac{1}{|{M}_{2}|}\mathrm{tr}\left(D^{(m_{1})}_{m_{2}}W_{2}^{\otimes
n}(x^{n}(m_{1},m_{2}))\right)\geq 1-4\delta\text{ .}$ (30)

Thus, for all sufficiently large $n\in\mathbb{N}$ any rate pairs satisfying

$R_{1}\leq\chi(P;\sigma^{Y_{1}})-2\epsilon-\frac{1}{n}\text{ }$

and

$R_{2}\leq\chi(P;\sigma^{Y_{2}})-2\epsilon-\frac{1}{n}\text{ }$

are achievable.∎

If we combine Lemma 1 and Theorem 3.1, we obtain

###### Corollary 1

Let $N$ be a two-phase bidirectional relaying quantum channel. Let $H^{Y_{1}}$
be the Hilbert space whose unit vectors correspond to the pure states of node
$1$’s quantum system, $H^{Y_{2}}$ be the Hilbert space whose unit vectors
correspond to the pure states of node $2$’s quantum system, and $H^{X}$ be the
Hilbert space whose unit vectors correspond to the pure states of the relay
node’s quantum system.

We assume that the relay node’s encoding is restricted to transmitting an
indexed finite set of orthogonal quantum states $X\subset H^{X}$.

We assume that node $1$’s encoding is restricted to transmitting an indexed
finite set of orthogonal quantum states $Y_{1}\subset H^{Y_{1}}$.

We assume that node $2$’s encoding is restricted to transmitting an indexed
finite set of orthogonal quantum states $Y_{2}\subset H^{Y_{2}}$.

The classical-quantum capacity region of the two-phase bidirectional relaying
quantum channel $N$ with average error is the intersection of two rate
regions, Region $1$ and Region $2$, which are defined as follows:
1: Region $1$ is the set of all rate pairs $(R_{1},R_{2})$ such that

$R_{2}\leq\chi(Q_{1};\sigma^{X})\text{ ,}$ (31)
$R_{1}\leq\chi(Q_{2};\sigma^{X})\text{ ,}$ (32)

and

$R_{2}+R_{1}\leq\chi(Q_{1,2};\sigma^{X})$ (33)

for any joint probability distribution $Q_{1,2}$ on $Y_{1}\times Y_{2}$. Here
$Q_{1}$ is the marginal probability distribution of $Q_{1,2}$ on $Y_{1}$,
$Q_{2}$ is the marginal probability distribution of $Q_{1,2}$ on $Y_{2}$, and
$\sigma^{X}$ is the resulting quantum state at the outcome of the relay node.
2: Region $2$ is the set of all rate pairs $(R_{1},R_{2})$ such that

$R_{1}\leq\limsup_{n\rightarrow\infty}\frac{1}{n}\chi(P^{n};{\sigma^{Y_{1}}}^{\otimes
n})\text{ }$ (34)

and

$R_{2}\leq\limsup_{n\rightarrow\infty}\frac{1}{n}\chi(P^{n};{\sigma^{Y_{2}}}^{\otimes
n})\text{ }$ (35)

for all probability distribution $P$ on $X$. Here, $\sigma^{Y_{1}}$ is the
resulting quantum state at the outcome of node $1$, while $\sigma^{Y_{2}}$ is
the resulting quantum state at the outcome of node $2$.

###### Remark 2

Note that the capacity region of a multiple-access channel with average errors
is not equal to its capacity region with maximal errors. This is a well-known
fact in the classical information theory (cf. Due  and Ahl5 ). We consider
average errors, not maximal errors in Theorem 3.1 and Corollary 35, since we
use Lemma 1, which considered average errors, for the multiple-access phase.

###### Remark 3

Without loss of generality, we assume that
$\chi(P;{\sigma^{Y_{1}}})\geq{\chi(P;\sigma^{Y_{2}}})$, i.e., $W_{2}$, the
channel which connects the relay node and node $2$, has a lower capacity than
$W_{1}$ in the broadcast phase. If
$\chi(Q_{2};\sigma^{X})={\chi(P;\sigma^{Y_{2}}})$, i.e., the capacities of
$W_{2}$ in both directions are identical, then $R_{1}$ cannot exceed
$\chi(P;{\sigma^{Y_{2}}})$ in the multiple-access phase. In this case, we may
assume that in the broadcast phase the message sets
$M_{1}=\\{1,\ldots,|M_{1}|\\}$ and $M_{2}=\\{1,\ldots,|M_{2}|\\}$, that the
relay node sends to node $1$ and node $2$, satisfy $|M_{1}|\leq
2^{n\chi(P;{\sigma^{Y_{2}}})-\epsilon}$ and $|M_{2}|\leq
2^{n\chi(P;{\sigma^{Y_{2}}})-\epsilon}$ for a positive $\epsilon$.

In this case, we have a very simple coding strategy for the broadcast phase.
The common message set which the relay node sends to both node $1$ and node
$2$ in the broadcast phase is a set $M^{\prime}=\\{1,\ldots,|M^{\prime}|\\}$
which satisfies $|M^{\prime}|=\lfloor
2^{n\chi(P;\sigma^{Y_{2}})-\epsilon}\rfloor$.

We consider the case that the relay node wants to send $(m_{1},m_{2})\in
M_{1}\times M_{2}$, where node $1$ shall detect $m_{1}$, while node $2$ shall
detect $m_{2}$. Then, the relay node sends $m_{1}+m_{2}\mod|M^{\prime}|$ as a
common message to both node $1$ and node $2$. By the HSW Random Coding Theorem
(cf. Sch/We  and Ho2 ) node $1$ and node $2$ can decode the common message if
the size of the message set is less than $2^{n\chi(P;\sigma^{Y_{2}})}$

Since node $1$ already knows $m_{2}$, it can obtain $m_{1}$ by simply
subtracting $m_{2}$ from $m_{1}+m_{2}$ modulo $|M^{\prime}|$. Since node $2$
already knows $m_{1}$, it can obtain $m_{2}$ by subtracting $m_{1}$ from
$m_{1}+m_{2}$ modulo $|M^{\prime}|$.

## Acknowledgment

Support by the Bundesministerium für Bildung und Forschung (BMBF) via Grant
16BQ1050 and 16BQ1052 is gratefully acknowledged.

## References

  * (1) S. Abruzzo, S. Bratzik, N. K. Bernardes, H. Kampermann, P. van Loock, and D. Bruß, Quantum repeaters and quantum key distribution: analysis of secret key rates, Phys. Rev. A, Vol. 87, 052315, 2013.
  * (2) R. Ahlswede, On two-way communication channels and a problem by Zarankiewicz, Sixth Prague Conf. on Inf. Th., Stat. Dec. Fct’s and Rand. Proc., Publ. House Chechosl. Academy of Sc., Prague, pp. 23-37, 1973.
  * (3) R. Ahlswede, Multi-way communication channels, Proceedings of 2nd International Symposium on Information Theory, Thakadsor, Armenian SSR, 1971, Akademiai Kiado, Budapest, pp. 23-52, 1973.
  * (4) R. Ahlswede and V. Blinovsky, Classical capacity of arbitrarily classical-quantum varying channels, IEEE Trans. Inform. Theory, Vol. 53, No. 2, pp. 526-533, 2007.
  * (5) M. Andersson, R. F. Schaefer (Wyrembelski), T. J. Oechtering, and M. Skoglund, Polar coding for bidirectional broadcast channels with common and confidential messages, IEEE Journal on Selected Areas in Communications, Vol. 31, No. 9, 1901-1908, 2013.
  * (6) P. P. Bergmans, Random coding theorem for broadcast channels with degraded components, IEEE Trans. Inf. Theory, Vol. IT-19, No. 2, pp. 197-207, 1973.
  * (7) I. Bjelaković, H. Boche, G. Janßen, and J. Nötzel, Arbitrarily varying and compound classical-quantum channels and a note on quantum zero-error capacities, Information Theory, Combinatorics, and Search Theory, in Memory of Rudolf Ahlswede, H. Aydinian, F. Cicalese, and C. Deppe eds., LNCS Vol.7777, 247-283, arXiv:1209.6325, 2012.
  * (8) H. Boche, M. Cai, and C. Deppe, Classical-quantum arbitrarily varying wiretap channel - capacity formula with Ahlswede Dichotomy - resources, arXiv:1307.8007, 2014.
  * (9) H. Boche, N. Cai, and J. Nötzel, The classical-quantum channel with random state parameters known to the sender, arXiv:1506.06479, 2015.
  * (10) H. J. Briegel , W. Dür, J. I. Cirac, and P. Zoller, Quantum repeaters for communication, arXiv:quant-ph/9803056v1, 1998.
  * (11) N. Cai, A. Winter, and R. W. Yeung, Quantum privacy and quantum wiretap channels, Problems of Information Transmission, Vol. 40, No. 4, 318-336, 2004.
  * (12) T. M. Cover, Comments on broadcast channels, IEEE Trans. Inf. Theory, Vol. IT-44, pp. 2524-2530, 1998.
  * (13) T. M. Cover and A. El Gamal, Capacity theorems for the relay channel, IEEE Trans. Inf. Theory, Vol. IT-25, No. 5, pp. 572-584, 1979\.
  * (14) I. Devetak, The private classical information capacity and quantum information capacity of a quantum channel, IEEE Trans. Inform. Theory, Vol. 51, No. 1, pp. 44-55, 2005.
  * (15) T. T. Do, T. J. Oechtering, and M. Skoglund, Optimal transmission for the MIMO bidirectional broadcast channel in the wideband regime, IEEE Trans. on Signal Processing, Vol. 61, No. 20, pp. 5103-5116, 2013.
  * (16) G. Dueck, Maximal error capacity regions are smaller than average error capacity regions for multi-user channels, Probl. Contr. Inf. Theory, Vol. 7, No. 1, pp. 11-19, 1978.
  * (17) J. Eisert and M. M. Wolf, Gaussian Quantum Channels, Quantum Information with Continuous Variables of Atoms and Light, Imperial College Press, London, pp.23-42, 2007.
  * (18) A. El Gamal and E. Van der Meulen, A proof of Marton’s coding theorem for the discrete memoryless broadcast channel, IEEE Trans. Inf. Theory, Vol. IT-27, pp. 120-122, 1981.
  * (19) M. Hayashi and H. Nagaoka, General formulas for capacity of classical-quantum channels, IEEE Trans. Inf. Theory, Vol. 49, No. 7, pp. 1753-1768, 2003.
  * (20) A. S. Holevo, Statistical problems in quantum physics, Proceedings of the Second Japan-USSR Symposium on Probability Theory, ser. Lecture Notes in Mathematics, G. Maruyama and J. V. Prokhorov, Eds., Vol. 330, pp. 104-119, Springer-Verlag, Berlin, 1973.
  * (21) A. S. Holevo, The capacity of the quantum channel with general signal states, IEEE Trans. Inf. Theory, Vol. 44, pp. 269-273, 1998.
  * (22) S. Ishizaka and T. Hiroshima, Quantum teleportation scheme by selecting one of multiple output ports. Phys. Rev. A, Vol. 79, 042306, 2009.
  * (23) B.C. Jacobs, T.B. Pittman, and J.D. Franson, Quantum relays and noise suppression using linear optics, Phys. Rev. A, Vol. 66, 052307, No. 5, 2002.
  * (24) G. Kramer, M. Gastpar, and P. Gupta, Cooperative strategies and capacity for relay networks, IEEE Trans. Inf. Theory, Vol. 51, No. 9, pp. 3037-3063, 2005.
  * (25) H. Liao, Multiple access channels, Ph.D. dissertation, Department of Electrical Engineering, University of Hawaii, Honolulu, 1972.
  * (26) K. Marton, A coding theorem for the discrete memoryless broadcast channel, IEEE Trans. Inf. Theory, Vol. IT-25, pp. 306-311, 1979.
  * (27) T. J. Oechtering and H. Boche, Stability region of an optimized bidirectional regenerative half-duplex relaying protocol. IEEE Trans. on Communications Vol. 56, No. 9, pp. 1519-1529, 2008.
  * (28) T. J. Oechtering and H. Boche, Bidirectional regenerative half-duplex relaying using relay selection, IEEE Transactions on Wireless Communications, Vol. 7, No. 5, pp. 1879-1888, 2008.
  * (29) T. J. Oechtering, H. Boche, Optimal time-division for bidirectional relaying using superposition encoding, IEEE Communications Letters, Vol. 12, No. 4, 265-267, 2008.
  * (30) T. J. Oechtering, E. A. Jorswieck, R. F. Schaefer (Wyrembelski), and H. Boche, On the optimal transmit strategy for the MIMO bidirectional broadcast channel. IEEE Trans.
  * (31) T. J. Oechtering and M. Skoglund, Bidirectional broadcast channel with random states noncausally known at the encoder, IEEE Trans. Inf. Theory, Vol. 59, No. 1, pp. 64-75, 2013.
  * (32) T. J. Oechtering, R. F. Schaefer (Wyrembelski), and H. Boche, Multiantenna bidirectional broadcast channels - optimal transmit strategies IEEE Trans. on Signal Processing, Vol. 57, No. 5, pp. 1948-1958, 2009. on Communications, Vol. 57, No. 12, pp. 3817-3826, 2009.
  * (33) T. J. Oechtering, C. Schnurr, I. Bjelaković, and H. Boche, Broadcast capacity region of two-phase bidirectional relaying, IEEE Trans. Inf. Theory, Vol. 54, No. 1, pp. 454-458, 2008.
  * (34) T. Ogawa and H. Nagaoka, Making good codes for classical-quantum channel coding via quantum hypothesis testing, IEEE Trans. Inform. Theory, Vol. 53, No. 6, 2261-2266, 2007.
  * (35) I. Savov and M. Wilde, Classical codes for quantum broadcast channels, Proceedings of ISIT 2012, pp. 721-725, 2012.
  * (36) I. Savov, M. Wilde, and M. Vu, Partial decode-forward for quantum relay channels, Proceedings of ISIT 2012, pp. 731-735, 2012.
  * (37) R. F. Schaefer (Wyrembelski), T. J. Oechtering, and H. Boche, MIMO Gaussian bidirectional broadcast channels with common messages, IEEE Trans. on Wireless Communications, Vol. 10, No. 9, pp. 2950-2959, 2011.
  * (38) R. F. Schaefer (Wyrembelski), I. Bjelaković, T. J. Oechtering, and H. Boche, Optimal coding strategies for bidirectional broadcast channels under channel uncertainty. IEEE Trans. on Communications, Vol. 58, No. 10, pp. 2984-2994, 2010.
  * (39) R. F. Schaefer (Wyrembelski), M. Wiese, and H. Boche, Strong secrecy in bidirectional broadcast channels with confidential messages, IEEE Trans. on Information Forensics and Security, Vol. 8, No. 2, pp. 324-334, 2013.
  * (40) B. Schumacher and M. A. Nielsen, Quantum data processing and error correction, Phys. Rev. A, Vol. 54, 2629, 1996.
  * (41) B. Schumacher and M. D. Westmoreland, Sending classical information via noisy quantum channels, Phys. Rev. A, Vol. 56, pp. 131-138, 1997.
  * (42) M. Wilde, Quantum Information Theory, Cambridge University Press, 2013.
  * (43) M. Wilde and S. Guha, Polar codes for classical-quantum channels, IEEE Trans. Inf. Theory, Vol. 59, No. 2, pp. 1175-1187, 2013.
  * (44) A. Winter, Coding theorem and strong converse for quantum channels, IEEE Trans. Inf. Theory, Vol. 45, No. 7, pp. 2481-2485, 1999\.
  * (45) A. Winter, The capacity of the quantum multiple-access channel, IEEE Trans. Inf. Theory, Vol. 47, No. 7, pp. 3059-3065, 2001.
  * (46) J. Yard, P. Hayden, and I. Devetak, Capacity theorems for quantum multiple access channels — classical-quantum and quantum-quantum capacity regions, IEEE Trans. Inf. Theory, Vol. 54, No. 7, pp. 3091-3113, 2008\.


11institutetext: Satbayev University, Satbayev str. 22, Almaty 050013,
Kazakhstan 22institutetext: Laboratory for Analysis and Modeling of
Information Processes, Institute of Information and Computational
Technologies, Pushkin str. 125, Almaty 050010, Kazakhstan
22email<EMAIL_ADDRESS>33institutetext: University of Washington, Department
of Mathematics, Padelford Hall C-138, Seattle 98195-4350, WA, USA
33email<EMAIL_ADDRESS>
# Superior Parallel Big Data Clustering through Competitive Stochastic Sample
Size Optimization in Big-means

Rustam Mussabayev 1122 0000-0001-7283-5144 Ravil Mussabayev 1133
0000-0003-1105-5990

###### Abstract

This paper introduces a novel K-means clustering algorithm, an advancement on
the conventional Big-means methodology. The proposed method efficiently
integrates parallel processing, stochastic sampling, and competitive
optimization to create a scalable variant designed for big data applications.
It addresses scalability and computation time challenges typically faced with
traditional techniques. The algorithm adjusts sample sizes dynamically for
each worker during execution, optimizing performance. Data from these sample
sizes are continually analyzed, facilitating the identification of the most
efficient configuration. By incorporating a competitive element among workers
using different sample sizes, efficiency within the Big-means algorithm is
further stimulated. In essence, the algorithm balances computational time and
clustering quality by employing a stochastic, competitive sampling strategy in
a parallel computing setting.

###### Keywords:

Big-means Clustering Parallel Computing Data Mining Stochastic Variation
Sample Size Competitive Environment Parallelization Strategy Machine Learning
Big Data Analysis Optimization Cluster Analysis K-means K-means++ Unsupervised
Learning.

##  1 Introduction

Clustering is a foundational task in the field of data analysis and machine
learning, serving as the cornerstone of unsupervised learning techniques [11].
The ultimate goal of clustering is to partition a set of objects into groups,
known as clusters, in such a way that objects belonging to the same cluster
exhibit higher similarity to each other than to those in different clusters
[12]. This task is driven by the inherent human instinct to understand and
organize large volumes of information, and it mirrors our natural desire to
categorize or group similar objects together.

The importance and ubiquity of clustering in various domains cannot be
overstated. For instance, in the realm of image processing and computer
vision, clustering algorithms are routinely employed for image segmentation,
where similar pixels are grouped together to identify regions of interest [5].
In the world of business and marketing, customer segmentation is crucial for
targeted marketing, and it heavily relies on clustering methods to identify
groups of customers with similar buying patterns or behaviors [19].

In bioinformatics, clustering is used in gene expression data analysis where
genes with similar expression patterns are grouped, leading to the
identification of functionally related groups of genes [8]. In the field of
natural language processing, clustering is used to group similar texts,
helping in tasks like topic modeling and sentiment analysis [6]. Additionally,
social network analysis often uses clustering to identify communities or
groups of users with similar interests or behaviors [10].

Despite the diverse applications, all clustering methods share a common goal —
to maximize the intra-cluster similarity and minimize the inter-cluster
similarity. Among various clustering methods, one common and widely accepted
criterion for clustering is the minimum-sum-of-squares clustering (MSSC)
criterion. The MSSC criterion is also known as the K-means criterion, as the
popular K-means algorithm optimizes this criterion [14].

The MSSC criterion aims to partition the data into K clusters, such that the
sum of squared Euclidean distances between the data points and their
associated cluster centers is minimized [9]. In mathematical terms, if we
denote the center of a cluster by $c\in C$ and the points in a cluster by
$x\in X$, then we aim to minimize

$\min\limits_{C}\ \ \
f\left(C,X\right)=\sum\limits_{i=1}^{m}\min_{j=1,\ldots,k}\|x_{i}-c_{j}\|^{2}$
(1)

where $k$ is the number of clusters, and $\|\cdot\|$ stands for the Euclidean
norm.

In practice, the MSSC criterion often leads to high-quality clusters when the
underlying clusters in the data are spherical and evenly sized [7]. However,
the criterion and its associated algorithms are sensitive to the initial
configuration and are susceptible to getting trapped in local minima [1]. This
motivates the search for advanced and robust clustering algorithms that can
overcome these limitations [4].

The purpose of this paper is to introduce a novel parallel clustering
algorithm with competitive stochastic sample size optimization and evaluate
its performance. Competitive optimization involves multiple solutions or
agents (parallel processes or algorithms) competing to achieve optimal
results, leading to a dynamic and adaptive optimization process. Stochastic
sampling, the random selection of data subsets, is used by each process to
reduce computational load while maintaining a representative data set. The new
algorithm is a parallel version of the Big-means clustering algorithm [18,
17], enhanced with competitive stochastic sample size optimization. Each
parallel process competes using different sample sizes for K-means clustering,
striving for the most efficient clustering outcome. Results of extensive
experiments suggest that this approach is more efficient and scales better
with large datasets compared to traditional K-means and all of its variants.

The rest of the paper is structured as follows. Section 2 motivates the
creation of the new algorithm. Section 3 provides a comprehensive literature
review of available methods, highlighting their main shortcomings. Section 4
presents the proposed method in detail. Section 5 describes the experimental
setup used to evaluate the performance of the algorithm. Section 6 discusses
the results and compares the new algorithm with existing methods. Finally,
Section 7 concludes the paper and suggests directions for future work.

##  2 Problem Statement

As the volume of data being generated and collected continues to grow
exponentially, the demand for efficient, scalable, and robust algorithms for
data analysis tasks like clustering has been significantly heightened. This is
especially true for MSSC algorithms that can handle large datasets, often
referred to as big data. Despite the ubiquity of MSSC clustering in various
domains, several challenges hinder the efficient execution of these algorithms
on big datasets.

Firstly, many of the existing MSSC algorithms do not scale well with the size
of the dataset. The computational complexity of these algorithms grows rapidly
as the number of data points increases, rendering them impractical for use on
big data. Notably, the popular K-means algorithm, while simple and effective
on smaller datasets, suffers from a high computational cost when dealing with
large-scale data due to the need to compute distances between each data point
and each centroid in each iteration.

Secondly, several current algorithms do not fully harness the potential of
modern high-performance computing systems. With the advancements in multi-core
and multi-processor architectures, as well as the advent of distributed
computing platforms, there exists a great opportunity to develop parallel
algorithms for MSSC that can process large datasets efficiently by utilizing
all available computational resources. However, the development of such
parallel algorithms is not straightforward and involves tackling challenges
like data partitioning, load balancing, and communication overhead among the
processing units.

Finally, a persistent challenge in MSSC is the sensitivity of the algorithms
to the initial configuration, which can lead to sub-optimal clustering
solutions trapped in local minima. This problem becomes more pronounced in the
case of big data due to the increased complexity and diversity of the data.

Therefore, the need for a new MSSC clustering algorithm that is both efficient
and scalable, can handle big data, takes full advantage of modern high-
performance computing systems, and provides robust clustering solutions
regardless of the initial configuration, is evident. Such an algorithm would
significantly enhance our ability to extract valuable insights from large
datasets in various fields.

##  3 Related Works

Clustering has been an intensely studied area in machine learning, and
numerous algorithms have been proposed to solve the problem of minimum-sum-of-
squares clustering. The K-means algorithm, owing to its simplicity, is the
most popular and widely used of these algorithms [15]. However, K-means has
several notable limitations. It tends to get stuck in local minima, is
sensitive to the initial placement of centroids, and its performance degrades
with an increase in the size of the dataset.

To overcome these limitations, several variants of K-means have been proposed.
The K-means++ algorithm introduces a smarter initialization technique that
aims to provide better initial centroids, thereby improving the final
clustering result [1]. While this technique reduces the risk of getting stuck
in poor local minima, it does not adequately address scalability issues.

MiniBatch K-means is a variant designed to handle larger datasets more
efficiently by operating on a randomly selected subset of the data at each
step [21]. While this improves computational efficiency, it comes at the cost
of potentially reduced clustering quality compared to standard K-means.

Scalable K-means++, as the name suggests, is designed to scale better with big
data. This variant selects initial centers in an “oversampling” phase and then
reduces the number of centers in a “reduce phase”, improving scalability.
However, the complexity of the algorithm and the need for multiple passes over
the data limit its practicality [2].

Bisecting K-means adopts a divide-and-conquer strategy where the algorithm
iteratively splits clusters [22]. This can potentially result in a better
quality of clustering but requires more computational resources as the number
of clusters or the size of the data increases.

Fuzzy C-means provides a probabilistic approach where each data point can
belong to multiple clusters with varying membership grades [3]. This can offer
more nuanced cluster assignments but increases the computational complexity
significantly.

X-means and G-means algorithms try to determine the appropriate number of
clusters automatically, thereby removing the need for explicit cluster number
specification [20]. However, this automation introduces its complexities and
can result in increased computational cost.

Hierarchical K-means presents a hierarchical approach to clustering, which can
handle larger datasets and provide a more intuitive cluster hierarchy [24].
Yet, it suffers from high computational costs for large datasets.

Finally, Distributed K-means algorithms take advantage of distributed
computing resources to scale the K-means clustering process to larger datasets
[23]. While this approach effectively utilizes modern computational resources,
the communication overhead and the need for data to be partitioned
appropriately can limit its efficiency.

Despite the strengths of these algorithms, they often introduce additional
computational complexity or do not adequately scale with larger datasets.
Hence, the need for a new algorithm that efficiently handles large datasets
while taking full advantage of modern high-performance computing resources is
evident.

##  4 Methodology

###  4.1 Big-means Algorithm

The Big-means algorithm is specifically designed to tackle large-scale Minimum
Sum-of-Squares Clustering (MSSC) problems. The concept underlying the Big-
means algorithm is straightforward [18]: in each iteration, a new uniformly
random sample of size $s\ll|X|$ is drawn from the provided dataset and
clustered using K-means. The K-means++ algorithm initializes clustering for
the first sample. Every subsequent sample is initialized using the best
solution found thus far across previous iterations in terms of minimizing the
objective function (1) on the samples. During intermediate iterations, only
degenerate clusters are reinitialized using K-means++. Iterations persist
until a “stop condition” is met. This “stop condition” can be a limit on CPU
time or a maximum number of samples to be processed. The outcome of the
algorithm is the set of centroids that achieved the best objective function
value (1) across the iterations. Ultimately, all data points can be allocated
to clusters based on their proximity to the resulting centroids.

The shaking procedure is a vital component of the Big-means algorithm. It
refers to the generation of a new sample in each iteration, which perturbs the
current (incumbent) solution and introduces variability into the clustering
results. When the full dataset is viewed as a cloud of points in an
$n$-dimensional space, each sample represents only a sparse approximation of
this cloud. This procedure instills diversity and adaptability into the
clustering process. It accomplishes this by iteratively applying the K-means
algorithm to random subsets of the data, progressively refining the centroid
locations, and effectively managing degenerate clusters.

The algorithm’s scalability can be fine-tuned by selecting appropriate sample
sizes and counts. Processing smaller subsets of data in each iteration
significantly reduces computational demands. Additionally, this strategy
prevents the algorithm from getting trapped in suboptimal solutions. This is
achieved by using random data subsets in each iteration and periodically re-
initializing the centroids of degenerate clusters. The Big-means algorithm is
a promising approach for clustering large datasets, offering scalability,
efficiency, and robustness.

###  4.2 Competitive Sample Size Big-means Algorithm

1 Initialization:

2 $C_{w}\leftarrow\text{Mark all }k\text{ centroids as degenerate for each
worker }w$;

3 $\hat{f}_{w}\leftarrow\infty$ for each worker $w$;

4 $t_{w}\leftarrow 0$ for each worker $w$;

5 $L\leftarrow\text{Empty list}$;

6 while  _$t_{w} <T$ for any worker $w$_ do

7 for  _each parallel worker $w$_ do

8 $s_{w}\leftarrow\text{Random integer in }[s_{min},s_{max}]$;

9 Recalculate $\hat{f}_{w}$ with the new $s_{w}$;

10 $p_{w}\leftarrow 0$;

11 while  _$p_{w} <p$_ do

12 $S_{w}\leftarrow\text{Random sample of size }s_{w}\text{ from }X$;

13 for  _each $c\in C_{w}$_ do

14 if  _$c$ is the centroid associated with a degenerate cluster_ then

15 Reinitialize $c\text{ using K-means++ on }S_{w}$;

16

17 end if

18

19 end for

20 $C_{\text{new},w}\leftarrow\text{K-means clustering on }S_{w}\text{ with
initial centroids }C_{w}$;

21 if  _$f(C_{\text{new},w},S_{w}) <\hat{f}_{w}$_ then

22 $C_{w}\leftarrow C_{\text{new},w}$;

23 $\hat{f}_{w}\leftarrow f(C_{\text{new},w},S_{w})$;

24 Add $s_{w}$ to list $L$;

25

26 end if

27 $p_{w}\leftarrow p_{w}+1$;

28

29 end while

30 $t_{w}\leftarrow t_{w}+1$;

31

32 end for

33

34 end while

35Analyze distribution of $s_{i}$ values in list $L$;

36 $s_{opt}\leftarrow s_{i}$ value with highest probability of improving
objective function;

37 $S\leftarrow\text{Random sample of size }s_{opt}\text{ from }X$;

38

39for  _each parallel worker $w$_ do

40 Recalculate $\hat{f}_{w}$ with $s_{opt}$ using $S$;

41

42 end for

43

44$C_{\text{best}}\leftarrow\text{Centroids of the worker with the smallest
}\hat{f}_{w}\text{ value}$;

45 $Y\leftarrow\text{Assign each point in }X\text{ to nearest centroid in
}C_{\text{best}}$;

46 return _$C_{\text{best}}$ , $Y$, $s_{opt}$_;

Algorithm 1 Detailed pseudocode of Parallel Big-means Clustering with
Competitive Stochastic Sample Size Optimization

In our study, we propose a novel strategy to parallelize the Big-means
clustering algorithm, wherein the size $s$ of the clustered sample from big
data used at each iteration varies. Within this parallelization strategy,
during the algorithm’s initialization stage, each of the $w$ workers randomly
selects their sample size $s_{w}$ from the permissible range
$[s_{min};s_{max}]$. Subsequently, each worker operates in parallel for $p$
iterations, adhering to the standard Big-means algorithm’s scheme using the
allocated sample size $s_{w}$.

After $p$ iterations, each $i$-th worker is assigned a new random sample size
$s_{w}$. Simultaneously, the value of the target criterion for the worker’s
current incumbent solution is recalculated to reflect the change in $s_{w}$,
as any change in $s_{w}$ necessitates such a recalculation. As the algorithm
operates, comprehensive statistics relating to improvements in the objective
function’s value for a given $s_{w}$ are collected for all workers.
Essentially, each worker, upon witnessing an improvement in the value of its
objective function, contributes its current $s_{w}$ value to a shared list.

By the end of the algorithm’s execution, we obtain a list of all $s_{w}$
values that led to improvements in the objective function’s value. By
analyzing the distribution of values in this list, we select the $s_{opt}$
value from the list that offers the highest probability of enhancing the
objective function’s value. The desired result can be achieved by calculating
a simple mean of the given list, which corresponds to the expected value of
the improving sample size.

This strategy effectively creates a competitive environment among workers,
allowing for simultaneous variation in the used sample size $s_{w}$ and
subsequent determination of its optimal value.

###  4.3 Detailed Algorithm Description

The algorithm presented in Algorithm 1 details a parallel implementation of
the K-means clustering method with competitive stochastic sample size
optimization. The method aims to determine the best cluster centroids and
assign data points to these clusters efficiently.

The algorithm initializes by marking all $k$ centroids as degenerate for each
worker $w$. Each worker also has an initial best-so-far objective function
value $\hat{f}_{w}$ and iteration count $t_{w}$ set to $\infty$ and 0,
respectively. An empty list $L$ is also defined to keep track of sample sizes
that lead to improvement in the objective function.

In each iteration of the main loop, every worker operates in parallel,
choosing a random sample size $s_{w}$ between $s_{min}$ and $s_{max}$, and
recomputing the $\hat{f}_{w}$ with the new sample size. Then, within the
defined maximum number of passes $p$, the worker takes a random sample of size
$s_{w}$ from the data set $X$ and processes the centroids. For each centroid
$c$ associated with a degenerate cluster, the worker reinitializes $c$ using
K-means++ on the sample $S_{w}$. The worker performs K-means clustering on
$S_{w}$ with initial centroids $C_{w}$ to get new centroids
$C_{\text{new},w}$. If the new centroids result in a better objective function
value, the worker updates its current centroids, best-so-far objective
function value, and adds the sample size to list $L$. The pass counter $p_{w}$
is then incremented.

After all workers finish their iterations or reach the maximum number of
iterations $T$, the algorithm proceeds to analyze the distribution of sample
sizes in list $L$. The algorithm selects the sample size $s_{opt}$, which has
the highest probability of improving the objective function. This selection
can be achieved by calculating the simple mean of the values in the list $L$.
Then, a new sample of size $s_{opt}$ is taken from the dataset $X$, and each
worker recalculates its best-so-far objective function value with this new
sample size.

Finally, the algorithm chooses the centroids $C_{\text{best}}$ of the worker
with the smallest $\hat{f}_{w}$ value, assigns each point in $X$ to its
nearest centroid in $C_{\text{best}}$, and returns these centroids, the
cluster assignments, and the optimal sample size $s_{opt}$.

In this article, we assume that each worker has equal access to the full-sized
dataset and can independently draw samples from it. For the sake of
simplicity, in this study we are not exploring various available opportunities
for further optimization of the algorithm, particularly those concerning
distributed data storage across different nodes of the computing system. Such
optimizations merit a separate study.

##  5 Experiment Setup

Our experiments utilized a system with Ubuntu 22.04 (64-bit), an AMD EPYC 7663
56-Core Processor, and 1.46 TB RAM. Up to 16 cores were deployed, running
Python 3.10.11, NumPy 1.24.3, and Numba 0.57.0. Numba [16] was essential for
Python code acceleration and parallelism.

The study involved comparing the proposed algorithm to the best-performing
hybrid-parallel version of the Big-means algorithm [17], using 19 public
datasets (details and URLs are available in [18] and [17]), plus four
normalized datasets, totaling 23. These datasets, with 2 to 5,000 attributes
and 7,797 to 10,500,000 instances, were used to assess our algorithm’s
versatility.

We executed each algorithm on the 23 datasets $n_{exec}$ times for cluster
sizes of 2, 3, 5, 10, 15, 20, 25. Select datasets underwent additional
clustering into 4 clusters, following Karmitsa et al. [13]. This resulted in
7,366 individual clustering processes. The algorithms’ performances were
measured in terms of relative clustering accuracy $\varepsilon$, CPU time $t$,
and baseline time $\overline{t}$.

The relative clustering accuracy $\varepsilon$ is defined as

$\varepsilon(\%)=\frac{100\times(f-f^{*})}{f^{*}},$

with $f^{*}=f^{*}(X,k)$ being the best historical objective function value for
dataset $X$ and cluster number $k$.

To objectively measure clustering time, we use a special baseline time metric
$\overline{t}$, which helps to avoid bias from minor late-stage improvements.
For every algorithm, time $\overline{t}$ is the time it takes for an algorithm
to achieve the baseline sample objective value $\overline{f}_{s}$. For every
pair $(X,k)$ and sample size $s$, $\overline{f}_{s}$ is derived from comparing
the sample objective values achieved by different Big-means parallelization
strategies: sequential, inner, competitive, and collective [17]. Specifically,
$\overline{f}_{s}$ is defined as the maximum of the median (median is taken
over $n_{exec}$ executions for the pair $(X,k)$) best sample objective
function values across iterations obtained by the considered parallel Big-
means versions. Essentially, this method determines the worst-performing
parallel Big-means version and treats its accuracy on the best processed
sample as the baseline. In multi-worker settings, $\overline{t}$ is the time
taken by the fastest worker to reach $\overline{f}_{s}$.

Clustering was limited to 300 iterations or a relative tolerance of $10^{-4}$,
and K-means++ was used with three candidate points for centroid generation.
For the proposed algorithm, $s_{min}$ was chosen to be $0.5$ of the sample
size $s$ used in Big-means, while $s_{max}$ was chosen to be 2 times $s$ (or
$m$, if this number exceeds $m$ for the given dataset). We set the parameter
value $p=10$ for all experiments. For each pair $(X,k)$, the choice of
parameters $s,t_{max}$ and $n_{exec}$ precisely matched the values specified
in the original Big-means paper [18].

Preliminary experiments established the optimal number of CPUs, baselines, as
well as the optimal parameter values for the hybrid parallel version of Big-
means, as described in [17]. The main experiment used these baselines and
parameter values. We calculated the minimum, median, and maximum values of
relative accuracy and CPU time for each $(X,k)$ pair over $n_{exec}$ runs. The
results are summarized in Tables 2 – 2. These tables highlight top
performances, providing a comprehensive evaluation across all datasets.

##  6 Experimental Results and Discussion

###  6.1 Performance Evaluation

Table 1: Relative clustering accuracies $\epsilon$ (%) for different
algorithms. The highest accuracies for each experiment (algorithm, data pair
$(X,k)$) are displayed in bold. Success is indicated when an algorithm’s
performance matches the best result among all algorithms for the current
experiment.

Dataset |  Proposed algorithm |  Big-means
---|---|---
#Succ | Min | Median | Max | #Succ | Min | Median | Max
CORD-19 Embeddings | 45/49 | -0.07 | 0.01 | 0.21 | 4/49 | 0.01 | 0.03 | 0.38
HEPMASS | 41/49 | -0.07 | 0.04 | 0.33 | 8/49 | 0.0 | 0.12 | 0.44
US Census Data 1990 | 102/140 | 0.0 | 1.43 | 4.74 | 38/140 | 0.03 | 1.97 | 5.6
Gisette | 97/105 | -1.86 | 0.0 | 0.1 | 8/105 | -1.71 | 0.01 | 0.29
Music Analysis | 135/140 | 0.01 | 0.23 | 1.3 | 5/140 | 0.02 | 0.54 | 3.57
Protein Homology | 103/105 | -0.05 | 0.05 | 1.83 | 2/105 | 0.11 | 0.8 | 2.69
MiniBooNE Particle Identification | 92/105 | -0.54 | 0.0 | 2.36 | 13/105 | -0.38 | 0.01 | 2.36
MiniBooNE Particle Identification (normalized) | 139/140 | -0.0 | 0.14 | 0.8 | 1/140 | 0.01 | 0.41 | 3.16
MFCCs for Speech Emotion Recognition | 131/140 | 0.0 | 0.05 | 1.99 | 9/140 | 0.02 | 0.11 | 2.21
ISOLET | 86/105 | -0.49 | 0.01 | 0.67 | 19/105 | -0.15 | 0.25 | 1.66
Sensorless Drive Diagnosis | 224/280 | -2.42 | -0.0 | 5.58 | 56/280 | -2.41 | -0.0 | 162.06
Sensorless Drive Diagnosis (normalized) | 237/280 | 0.0 | 1.02 | 4.45 | 43/280 | 0.01 | 1.28 | 7.87
Online News Popularity | 130/140 | -0.39 | 0.17 | 5.02 | 10/140 | 0.01 | 0.88 | 11.59
Gas Sensor Array Drift | 166/210 | -0.92 | 0.04 | 4.06 | 44/210 | -0.77 | 0.26 | 8.42
3D Road Network | 267/280 | 0.0 | 0.04 | 0.66 | 13/280 | 0.0 | 0.22 | 2.76
Skin Segmentation | 181/210 | -1.38 | 0.1 | 5.34 | 29/210 | -1.3 | 0.21 | 10.01
KEGG Metabolic Relation Network (Directed) | 114/140 | -1.27 | 0.0 | 2.93 | 26/140 | -1.24 | 0.03 | 27.4
Shuttle Control | 99/120 | -3.22 | 0.0 | 6.93 | 21/120 | -3.12 | 1.38 | 16.48
Shuttle Control (normalized) | 145/160 | 0.01 | 0.23 | 5.59 | 15/160 | 0.05 | 1.34 | 10.43
EEG Eye State | 143/160 | -0.09 | 0.0 | 4.25 | 17/160 | -0.06 | 0.01 | 29.91
EEG Eye State (normalized) | 212/240 | -0.38 | -0.0 | 0.7 | 28/240 | -0.33 | 0.0 | 598.89
Pla85900 | 264/280 | -0.06 | 0.04 | 1.44 | 16/280 | 0.0 | 0.12 | 1.6
D15112 | 100/105 | -0.02 | 0.01 | 0.69 | 5/105 | 0.01 | 0.12 | 1.33
Overall Results | 3253/3683 | -0.57 | 0.29 | 2.69 | 430/3683 | -0.49 | 0.66 | 39.61

Table 2: Resulting clustering times $\overline{t}$ (sec.) with respect to
baseline sample objective values $\overline{f}_{s}$. The lowest clustering
times for each experiment (algorithm, data pair $(X,k)$) are displayed in
bold.

Dataset |  Proposed algorithm |  Big-means
---|---|---
Min | Median | Max | Min | Median | Max
CORD-19 Embeddings | 1.69 | 13.2 | 41.17 | 2.14 | 13.19 | 40.1
HEPMASS | 1.5 | 4.77 | 24.6 | 0.75 | 2.77 | 21.53
US Census Data 1990 | 0.46 | 2.07 | 5.21 | 0.09 | 0.74 | 2.75
Gisette | 2.38 | 14.53 | 43.52 | 5.07 | 26.14 | 56.92
Music Analysis | 0.19 | 3.49 | 14.33 | 0.6 | 3.58 | 12.87
Protein Homology | 0.08 | 3.24 | 13.25 | 0.37 | 3.69 | 10.43
MiniBooNE Particle Identification | 0.59 | 4.92 | 15.56 | 0.62 | 4.71 | 15.48
MiniBooNE Particle Identification (normalized) | 0.02 | 0.6 | 1.82 | 0.03 | 0.74 | 2.04
MFCCs for Speech Emotion Recognition | 0.03 | 0.67 | 2.34 | 0.23 | 0.81 | 1.62
ISOLET | 0.04 | 1.81 | 7.29 | 0.62 | 2.57 | 6.96
Sensorless Drive Diagnosis | 0.22 | 1.72 | 4.86 | 0.08 | 1.63 | 4.62
Sensorless Drive Diagnosis (normalized) | 0.01 | 0.21 | 0.9 | 0.01 | 0.28 | 0.56
Online News Popularity | 0.01 | 0.53 | 1.47 | 0.03 | 0.52 | 1.56
Gas Sensor Array Drift | 0.01 | 0.7 | 2.23 | 0.22 | 1.15 | 3.13
3D Road Network | 0.02 | 0.63 | 2.2 | 0.03 | 0.69 | 2.52
Skin Segmentation | 0.01 | 0.06 | 0.61 | 0.01 | 0.17 | 0.39
KEGG Metabolic Relation Network (Directed) | 0.02 | 0.77 | 1.96 | 0.02 | 0.69 | 2.11
Shuttle Control | 0.03 | 0.54 | 1.56 | 0.21 | 0.62 | 1.29
Shuttle Control (normalized) | 0.0 | 0.05 | 0.39 | 0.01 | 0.27 | 0.4
EEG Eye State | 0.07 | 0.48 | 1.35 | 0.04 | 0.58 | 1.2
EEG Eye State (normalized) | 0.01 | 0.18 | 0.84 | 0.01 | 0.16 | 0.77
Pla85900 | 0.01 | 0.17 | 0.68 | 0.01 | 0.57 | 1.51
D15112 | 0.01 | 0.04 | 0.39 | 0.03 | 0.38 | 1.04
Overall Results | 0.32 | 2.64 | 8.2 | 0.49 | 3.04 | 8.34

A summary of the results of the main experiment are provided in Tables 2 – 2.
Based on the experimental results, it was observed that the proposed algorithm
performed consistently better than Big-means on all datasets, both with
respect to the accuracy and time.

We attribute the outstanding performance of the proposed algorithm to its
ability to approximate the probability distribution of sample sizes that
improve the sample objective function. In the competitive parallelization
strategy, each worker starts with its own K-means++ initialization, which
strengthens the final result via diversification. Also, due to this kind of
parallelism, the algorithm is able to accumulate the necessary statistics for
the approximation in a very timely efficient manner. Then, the optimal sample
size value $s_{opt}$ can be obtained by evaluating the simple mean of the
accumulated sample size occurrence distribution.

The value $s_{opt}$ is the size of a sample that attains the best balance
between sparsifying high-density clusters while still including enough mass of
low-density clusters into the sample. In addition to the accumulation of the
improving sample size distribution, competitive workers are able to
dynamically guide the flow of centroids through unfavorable situations by
using various random sample sizes in the range $[s_{min},s_{max}]$. For
instance, these unfavorable situations might occur when a sample has large
gaps between highly dense clusters (thus preventing the fluidity of centroids
between them) or excludes some clusters due to an overly intense
sparsification.

##  7 Conclusion and Future Works

In this work, we proposed a parallel Big-means clustering algorithm equipped
with competitive stochastic sample size optimization, as well as thoroughly
evaluated its performance against the state-of-the-art hybrid-parallel version
of the Big-means algorithm [17] using a wide array of real-world datasets from
the Big-means’ original paper [18]. The idea of using an automatic procedure
for approximating the optimal sample size stemmed from multiple
considerations. First, it is practically hard and error-prone to estimate the
sample size for real-world big datasets. Second, using a fixed sample size
makes the iterative improvement nature of the Big-means algorithm too rigid.
Indeed, sampling with a fixed sample size is limited in the flexibility of
approximating and sparsifying regions of the dataset with different densities.

Our improved version of Big-means exhibited exceptional results both in the
resulting quality and time, pushing much further the state of the art in the
field of big data clustering. We are confident that our work presents a
valuable contribution to the scientific field, as well as brings a tool of
considerable practical value to practitioners in the field of big data.

For future research, we plan to investigate other dimensions for
experimentation, including different ways to explore the range
$[s_{min},s_{max}]$ and exploit the currently best obtained sample size across
iterations.

## Acknowledgements

This research was funded by the Science Committee of the Ministry of Science
and Higher Education of the Republic of Kazakhstan (grant no. BR21882268).

## References

  * [1] Arthur, D., Vassilvitskii, S.: K-means++: The advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms. p. 1027–1035. SODA ’07, Society for Industrial and Applied Mathematics, USA (2007)
  * [2] Bahmani, B., Moseley, B., Vattani, A., Kumar, R., Vassilvitskii, S.: Scalable k-means++. Proceedings of the VLDB Endowment 5(7), 622–633 (2012)
  * [3] Bezdek, J.C.: Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press, New York (1981)
  * [4] Celebi, M.E.: Comparative Performance of Seeding Methods for k-Means Algorithm. Springer (2013)
  * [5] Comaniciu, D., Meer, P.: Mean shift: a robust approach toward feature space analysis. IEEE Transactions on Pattern Analysis and Machine Intelligence 24(5), 603–619 (2002)
  * [6] Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K., Harshman, R.: Indexing by latent semantic analysis. Journal of the American Society for Information Science 41(6) (1990)
  * [7] Ding, C., He, X.: K-means clustering via principal component analysis. In: Proceedings of the twenty-first international conference on Machine learning (2004)
  * [8] Eisen, M.B., Spellman, P.T., Brown, P.O., Botstein, D.: Cluster analysis and display of genome-wide expression patterns. Proceedings of the National Academy of Sciences 95(25), 14863–14868 (1998)
  * [9] Forgy, E.W.: Cluster analysis of multivariate data: efficiency vs interpretability of classifications. Tech. Rep. RM-5437-PR, RAND Corporation (1965)
  * [10] Fortunato, S.: Community detection in graphs. Physics Reports 486(3-5), 75–174 (2010)
  * [11] Hastie, T., Tibshirani, R., Friedman, J.: The elements of statistical learning: data mining, inference, and prediction. Springer Science & Business Media (2009)
  * [12] Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recognition Letters 31, 651–666 (2010)
  * [13] Karmitsa, N., Bagirov, A.M., Taheri, S.: Clustering in large data sets with the limited memory bundle method. Pattern Recognition (2018)
  * [14] MacQueen, J.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the fifth Berkeley symposium on mathematical statistics and probability. vol. 1, pp. 281–297 (1967)
  * [15] MacQueen, J.B.: Some methods for classification and analysis of multivariate observations 1(14) (1967)
  * [16] Marowka, A.: Python accelerators for high-performance computing. The Journal of Supercomputing 74(4), 1449–1460 (2018)
  * [17] Mussabayev, R., Mussabayev, R.: Strategies for parallelizing the big-means algorithm: A comprehensive tutorial for effective big data clustering (2023)
  * [18] Mussabayev, R., Mladenovic, N., Jarboui, B., Mussabayev, R.: How to use k-means for big data clustering? Pattern Recognition 137, 109269 (2023). https://doi.org/10.1016/j.patcog.2022.109269
  * [19] Ng, A.Y., Jordan, M.I., Weiss, Y.: On spectral clustering: Analysis and an algorithm. In: Advances in neural information processing systems. pp. 849–856 (2002)
  * [20] Pelleg, D., Moore, A.: X-means: Extending k-means with efficient estimation of the number of clusters. In Proceedings of the 17th International Conf. on Machine Learning pp. 727–734 (2000)
  * [21] Sculley, D.: Web-scale k-means clustering. Proceedings of the 19th international conference on World wide web pp. 1177–1178 (2010)
  * [22] Steinbach, M., Karypis, G., Kumar, V.: A comparison of document clustering techniques. In: KDD Workshop on Text Mining (2000)
  * [23] Zaharia, M., Chowdhury, M., Das, T., Dave, A., Ma, J., McCauly, M., Franklin, M.J., Shenker, S., Stoica, I.: Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In: Proceedings of the 9th USENIX conference on Networked Systems Design and Implementation. USENIX Association (2012)
  * [24] Zhang, T., Ramakrishnan, R., Livny, M.: Birch: An efficient data clustering method for large databases. ACM SIGMOD Record 25(2), 103–114 (1996)