# How to Coordinate Edge Devices for Over-the-Air Federated Learning?

Mohammad Ali Sedaghat1, Ali Bereyhi2, Saba Asaad2, and Ralf R. Müller2,
1Qualcomm CDMA Technologies GmbH Nuremberg
2Friedrich-Alexander Universität Erlangen-Nürnberg (FAU)
<EMAIL_ADDRESS>{ali.bereyhi, saba.asaad<EMAIL_ADDRESS>
###### Abstract

This work studies the task of device coordination in wireless networks for
over-the-air federated learning (OTA-FL). For conventional metrics of
aggregation error, the task is shown to describe the zero-forcing (ZF) and
minimum mean squared error (MMSE) schemes and reduces to the NP-hard problem
of subset selection. We tackle this problem by studying properties of the
optimal scheme. Our analytical results reveal that this scheme is found by
searching among the leaves of a tree with favorable monotonic features.
Invoking these features, we develop a low-complexity algorithm that
approximates the optimal scheme by tracking a dominant path of the tree
sequentially. Our numerical investigations show that the proposed algorithm
closely tracks the optimal scheme.

###### Index Terms:

Over-the-air communication, federated Learning, multi-antenna, mean squared
error.

##  I Introduction

Federated learning (FL) is a privacy-preserving framework for distributed
learning that enables edge devices to address a learning task, e.g., training
a global model, jointly without need for sharing their local data [1, 2, 3].
This ensures device privacy and provides a joint scheme for learning that
performs considerably better than individual distributed learning while
keeping the communication load of the system tractable [4, 5, 6].

The promising learning performance in FL comes along with several challenges
which are roughly divided into the three categories of privacy, statistical
properties of local datasets and communication-efficiency. With respect to
privacy, FL has been shown to be vulnerable against model inversion attack [7,
8]. This follows from the fact that edge devices in FL share their local
models that are often strongly correlated with their local data [9, 10].
Statistical properties of local datasets further refers to the sensitivity of
FL against data distribution. Initial studies on FL have shown promising
performance and fast convergence of this framework for homogeneous local
datasets. Nevertheless, obtaining these favorable behaviors have been shown to
face some analytical challenges when we deviate from simple statistical models
for local datasets [11]. This is in particular crucial, as the exact
statistical model of data is rather unknown in practice.

This study focuses on the latter class of challenges in FL, i.e.,
communication-efficiency, that refers to communication-related challenges,
when the FL framework is to be implemented in a wireless network. In fact, FL
schemes require several rounds of communication between a central node, often
called the parameter server (PS), and the edge devices. This is in particular
challenging when the scheme runs over remote wireless devices introducing
various sources of imperfection to the setting, e.g., rate-limited
communication links and noisy assessment of local model parameters [12, 13,
14].

###  I-A Over-the-Air Federated Learning

FL performs distributed learning in three main phases:

  1. 1.

Starting with an initial global model, edge devices learn a model locally from
their datasets. They then share the local models with the PS.

  2. 2.

The PS collects the local models and aggregates them into a global model.

  3. 3.

The global model is sent back to the devices, and the devices repeat local
learning via the new global model.

The PS and edge devices keep iterating these three phases for several
communication rounds until they converge.

Classical approaches for implementation of FL in a wireless network suggest a
separate decoding and aggregation at the PS[15, 16]. This means that the PS
decodes first the received local models and then combines the decoded models
into a global model via a predefined aggregation policy. An alternative
approach is proposed in [17] which invokes the idea of analog function
computation [18] to perform model aggregation directly over the air. We refer
to this latter approach as over-the-air FL (OTA-FL) in this paper. OTA-FL
invokes the signal combination in the multiple access channel to realize the
predefined aggregation policy directly over-the-air. In other words, the edge
devices in OTA-FL transmit their local models with proper scaling, such the
desired model aggregation is calculated from the a linearly-transformed
version of the received signal at the PS. In various use-cases, OTA-FL is more
efficient than separate decoding and aggregation [19]. In fact, OTA-FL does
not need to orthogonalize communication resources, i.e., allocate individual
bandwidth and time slot to every device, and hence it enjoys both advantages
of lower computation and resource efficiency [20, 21, 22].

###  I-B Contributions and Organization

As OTA-FL relies on the uplink channel for model aggregation, coordination
plays a key role in its performance. In fact, the PS and devices need to agree
on a communication protocol, such that the over-the-air aggregated model is as
close as possible to the desired form. Prior studies often consider a basic
approach for coordination that is known to be sub-optimal from the information
theoretic point of view. In this work, we study the concept of coordination in
OTA-FL in great details. In this respect, we first formulate an optimal
coordination scheme for a given metric of aggregation error mathematically. We
then show that using the conventional metric of mean squared error (MSE) for
aggregation error, the optimal coordination scheme reduces to an MSE
minimization problem, while the commonly-used strategy for coordination is
simply zero-forcing. Our analyses show that both strategies reduce to the NP-
hard problem of subset selection and hence deal with the same level of
hardness. We tackle the problem of subset selection in both minimum MSE and
zero-forcing schemes by studying the properties of the solution. Our
investigations reveal that the solution in both cases can be found by
searching over the leaves of a tree with some monotonic properties. In the
light of these properties, we propose low-complexity algorithms which
sequentially approximate the solution by tracking a dominant path towards
leaves. Our simulation results show that the proposed tree-based algorithm can
track the optimal performance very closely while enjoying a drastically lower
computational complexity.

The remaining of this manuscript is organized as follows: We first formulate
the problem concretely in Section II. Minimum MSE and zero-forcing
coordination schemes are then illustrated in Sections III and IV ,
respectively. Sections V and VI investigates the analytical properties of the
zero-forcing and minimum MSE schemes, respectively, and propose a tree-based
algorithm for their approximation with low complexity. The validity of the
derivations are confirmed through numerical investigation in Section VII.
Finally, Section VIII concludes the paper.

###  I-C Notation

Scalars, vectors and matrices are represented with non-bold, bold lower-case
and bold upper-case letters, respectively. The transpose and transpose
conjugate of $\mathbf{H}$ is denoted by $\mathbf{H}^{\mathsf{T}}$ and
$\mathbf{H}^{\mathsf{H}}$, respectively. The Euclidean norm of $\mathbf{x}$ is
shown by $\left\|\mathbf{x}\right\|$. The notation
$\mathcal{E}\left\\{\cdot\right\\}$ denotes mathematical expectation and
$\mathcal{CN}\left(\boldsymbol{\mu},\mathbf{C}\right)$ refers to a
multivariate complex Gaussian distribution with mean vector $\boldsymbol{\mu}$
and covariance matrix $\mathbf{C}$. The complex plane is denoted by
$\mathbb{C}$, and the conjugate of $z\in\mathbb{C}$ is shown by $z^{*}$. For
brevity, $\left\\{1,\ldots,N\right\\}$ is abbreviated by $\left[N\right]$.

##  II Problem Formulation

A wireless network with $L$ single-antenna edge devices and a PS is
considered. The devices employ an FL scheme, e.g., federated averaging, to
address a common learning task, e.g., training a given model, jointly over
their distributed local datasets. The PS is equipped with an $N$-element
array-antenna. Throughout the analyses, we assume that $N\geq L$. This
assumption is however taken for the sake of brevity. The case of $N<L$ is then
discussed separately as a remark; see Remark 1.

At the beginning of each coherence interval, the devices send predefined
pilots in their uplink channels. The PS then estimates the channel state
information (CSI) based on the received signals. For simplicity, we assume
that the pilots are mutually orthogonal and that the estimation error is
negligible. Hence, the PS knows the CSI perfectly. Throughout the analyses, we
assume that the channels experience frequency-flat fading processes. This
models transmission over a channel with a narrow frequency band. The
derivations are in principle extendable to wide-band transmission in multi-
carrier systems with frequency selective fading processes.

###  II-A OTA-FL Setting

Following the FL scheme, each device determines its local model parameters
from its local dataset. It then shares this local model with the PS through
its uplink channel. Let $s_{\ell}$ be the model parameter of device $\ell$
that is to be shared with the PS in a given time-frequency slot. Device $\ell$
transmits this parameter by applying a channel-dependent scaling coefficient
$b_{\ell}$, i.e., it transmits

$\displaystyle x_{\ell}=b_{\ell}s_{\ell}.$ (1)

The local models $\left\\{s_{\ell}\right\\}$ are assumed to be independent and
identically distributed (i.i.d.) with mean zero and unit variance111Note that
in practice $\left\\{s_{\ell}\right\\}$ are unbiased versions of the model
parameters, e.g., quantized gradient values, which for weakly-correlated local
datasets fit into this model [23].. The devices are further restricted to set
their average power below a maximum power $P$. This means that over a period
of time in which the channel is approximately constant, the transmit signal of
device $\ell$ satisfies

$\displaystyle\mathcal{E}\left\\{\left|x_{\ell}\right|^{2}\right\\}=\left|b_{\ell}\right|^{2}\leq
P.$ (2)

The devices communicate over a fading Gaussian MAC. Hence, the PS receives
$\mathbf{y}\in\mathbb{C}^{N}$ which is given by

$\displaystyle\mathbf{y}=\sum_{\ell=1}^{L}\mathbf{h}_{\ell}x_{\ell}+\mathbf{n}.$
(3)

Here, $\mathbf{h}_{\ell}\in\mathbb{C}^{N}$ denotes the complex uplink channel
vector of device $\ell$, and $\mathbf{n}\in\mathbb{C}^{N}$ is additive white
Gaussian noise with mean zero and variance $\sigma^{2}$, i.e.,
$\mathbf{n}\sim\mathcal{N}\left(\boldsymbol{0},\sigma^{2}\mathbf{I}_{N}\right)$.

The ultimate goal of the PS is to combine the local models according to a
predefined strategy specified by the FL scheme. More precisely, the PS aims to
determine

$\displaystyle\theta=\sum_{\ell=1}^{L}\phi_{\ell}s_{\ell}$ (4)

for some predefined coefficients $\left\\{\phi_{\ell}\right\\}$, and then
share it with the devices through its downlink channels. To this end, the PS
invokes the idea of OTA-FL and combines the local models directly over-the-
air: it estimates the desired global model, i.e., $\theta$, by combining the
received signal elements. In other words, it employs a linear receiver
$\mathbf{m}\in\mathbb{C}^{N}$ and determines an estimate of $\theta$ as

$\displaystyle\hat{\theta}=\mathbf{m}^{\mathsf{T}}\mathbf{y}$
$\displaystyle=\sum_{\ell=1}^{L}\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}x_{\ell}+\mathbf{m}^{\mathsf{T}}\mathbf{n},$
(5)
$\displaystyle=\sum_{\ell=1}^{L}\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}b_{\ell}s_{\ell}+\mathbf{m}^{\mathsf{T}}\mathbf{n}.$
(6)

It is readily to shown that by restricting the estimation at the PS to be
linear, the OTA-FL scheme is optimal: there exists a receiver $\mathbf{m}$ and
scaling coefficients $b_{\ell}$ whose corresponding estimate of global model,
i.e., $\hat{\theta}$ in (6), recovers the estimate achieved by combining the
optimal linear estimation of local models according to the predefined strategy
in (4) [17].

###  II-B Aggregation Error of the OTA-FL Setting

As communication is carried out through a noisy network, the estimated global
model $\hat{\theta}$ contains some error as compared with the desired global
model $\theta$. This error is often called aggregation error and can be
evaluated in various respect. The classical approach in OTA-FL is to quantify
the aggregation error in terms of the mean squared error (MSE).

Using the MSE as the metric, the aggregation error in this setting is given by

$\displaystyle\epsilon\left(\mathbf{m},\left\\{b_{\ell}\right\\}\right)$
$\displaystyle=\mathcal{E}\left\\{\left|\hat{\theta}-\theta\right|^{2}\right\\},$
(7)
$\displaystyle=\mathcal{E}\left\\{\left|\sum_{\ell=1}^{L}\left(\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}b_{\ell}-\phi_{\ell}\right)s_{\ell}+\mathbf{m}^{\mathsf{T}}\mathbf{n}\right|^{2}\right\\},$
(8)
$\displaystyle=\sum_{\ell=1}^{L}\left|\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}b_{\ell}-\phi_{\ell}\right|^{2}+\sigma^{2}\left\|\mathbf{m}\right\|^{2}.$
(9)

The error expression can be compactly represented as

$\displaystyle\epsilon\left(\mathbf{m},\mathbf{B}\right)$
$\displaystyle=\left\|\mathbf{B}\mathbf{H}^{\mathsf{T}}\mathbf{m}-\boldsymbol{\phi}\right\|^{2}+\sigma^{2}\left\|\mathbf{m}\right\|^{2}$
(10)

where $\mathbf{B}=\mathrm{Diag}\left\\{b_{\ell}\right\\}$,
$\phi=\left[\phi_{1},\ldots,\phi_{L}\right]^{\mathsf{T}}$ and $\mathbf{H}$ is
the uplink channel matrix, i.e.,

$\displaystyle\mathbf{H}=\left[\mathbf{h}_{1},\ldots,\mathbf{h}_{L}\right].$
(11)

###  II-C Coordination Schemes for the OTA-FL Setting

To establish FL in the network, the PS needs to coordinate the devices
periodically: after the uplink training phase at the beginning of a coherence
interval, the PS specifies the uplink scaling coefficients of the devices,
i.e., $\left\\{b_{\ell}\right\\}$, and the linear receiver $\mathbf{m}$. The
devices are then informed about their scaling coefficients by a downlink
transmission. Afterwards, throughout the coherence interval, the PS and
devices carry out their communication according to the OTA-FL scheme described
in Section II-A using the coefficients and receiver specified in the training
phase. It is worth mentioning that the PS only shares the scaling coefficients
with the devices and not the complete CSI.

In general, the optimality of a coordination strategy depends on the choice of
metric that determines the quality of the FL scheme. A good approach is to
consider the aggregation error as the metric and design the coordination
strategy, such that the error is minimized222This is in particular effective,
since the MSE of estimated global model directly affects the learning quality
of the FL scheme [17].. In this case, the optimal coordination strategy is
formulated as

$\displaystyle\left(\mathbf{m}^{\star},\mathbf{B}^{\star}\right)=\operatorname*{argmin}_{\mathbf{m}\in\mathbb{C}^{N},\left|b_{\ell}\right|^{2}\leq
P}\epsilon\left(\mathbf{m},\mathbf{B}\right).$ (12)

This is in fact a minimum MSE (MMSE) problem. We hence refer to this strategy
as MMSE coordination. Due to its non-convexity, MMSE coordination is
computationally intractable in a generic network.

An alternative approach for coordination is to use the idea of zero-forcing
(ZF) [17, 24]. In this approach, the PS ignores noise in the channel and
coordinates the devices, such that the noise-free version of the estimated
global model constructs the desired global model. From (6), this means that
the PS finds $\mathbf{m}$ and $\left\\{b_{\ell}\right\\}$, such that

$\displaystyle\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}b_{\ell}=\phi_{\ell}.$
(13)

In this case, the aggregation error reduces to

$\displaystyle\epsilon\left(\mathbf{m},\mathbf{B}\right)=\sigma^{2}\left\|\mathbf{m}\right\|^{2}.$
(14)

The PS hence solves the following problem

$\displaystyle\mathbf{m}^{\rm zf}=$
$\displaystyle\operatorname*{argmin}_{\mathbf{m}\in\mathbb{C}^{N}}\left\|\mathbf{m}\right\|^{2}$
(15) $\displaystyle\text{subject
to}\;\left|\frac{\phi_{\ell}}{\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}}\right|^{2}\leq
P\;\text{ for }\;\ell\in\left[L\right],$

to find the receiver. The scaling coefficients $\left\\{b_{\ell}\right\\}$ are
then determined from (13) by replacing $\mathbf{m}$ with $\mathbf{m}^{\rm
zf}$, i.e.,

$\displaystyle b_{\ell}^{\rm
zf}=\frac{\phi_{\ell}}{\mathbf{h}_{\ell}^{\mathsf{T}}\mathbf{m}^{\rm zf}}$
(16)

In the sequel, we refer to this scheme as ZF coordination.

##  III MMSE Coordination for OTA-FL

The design problem for MMSE coordination is non-convex and generally
challenging to solve. Nevertheless, for some particular cases, the solution
can be derived tractably. An instance is given in [25], where the solution of
a mathematically similar problem is derived for an uplink scenario with a
single-antenna PS in closed form, despite its non-convexity. Motivated by this
result, we present in the sequel some preliminary analyses. We show that the
problem in the general case with a multi-antenna PS is more complicated and
unlike the single-antenna case, the optimal MMSE scheme cannot be derived
analytically. The analyses however give some important insights on MMSE
coordination that pave the way for the proposed algorithms in next sections.
We start the analyses by the following lemma:

######  Lemma 1.

With MMSE coordination in the network, there is at least one device that
transmits with the maximum transmit power $P$.

###### Proof.

The proof is given by contradiction: assume that all the devices transmit with
power less than $P$ while coordinated via the MMSE scheme in (12). Let
$\mathbf{m}^{\star}$ and $\left\\{b_{\ell}^{\star}\right\\}$ refer to the
solutions of the MMSE scheme. This means that
$\left|b_{\ell}^{\star}\right|^{2}<P$. We now construct new scaling
coefficients as $\hat{b}_{\ell}=\kappa b_{\ell}^{\star}$, where $\kappa>1$ is
chosen such that

$\displaystyle\max_{\ell\in\left[L\right]}\left|\hat{b}_{\ell}\right|^{2}=P.$
(17)

A new receiver is further constructed from $\mathbf{m}^{\star}$ as
$\hat{\mathbf{m}}=\kappa^{-1}\mathbf{m}^{\star}$ and satisfies
$\left\|\hat{\mathbf{m}}\right\|<\left\|\mathbf{m}^{\star}\right\|$.

We now consider the aggregation error derived in (9). Using the new scaling
coefficients and receiver, i.e., $\hat{\mathbf{m}}$ and
$\\{\hat{b}_{\ell}\\}$, the first term in the error expression remains
unchanged as compared with the term given for $\mathbf{m}^{\star}$ and
$\left\\{b_{\ell}^{\star}\right\\}$. The second term however becomes smaller.
This means that we have found $\hat{\mathbf{m}}$ and $\\{\hat{b}_{\ell}\\}$
that satisfy

$\displaystyle\epsilon(\hat{\mathbf{m}},\\{\hat{b}_{\ell}\\})\leq\epsilon\left(\mathbf{m}^{\star},\\{b_{\ell}^{\star}\\}\right).$
(18)

This contradicts with the definition of MMSE coordination in (12), and hence
concludes the proof333A similar result has been shown in [25] for a single-
antenna PS.. ∎

Lemma 1 implies that with MMSE coordination, at least one device is
transmitting with the maximum power. From this result, we can have a simple
conclusion: let the set of devices $\left[L\right]$ be partitioned as
$\left[L\right]=\mathbb{D}\cup\bar{\mathbb{D}}$, where $\mathbb{D}$ denotes
the set of all devices transmitting with the maximum power $P$ and
$\bar{\mathbb{D}}$ represents the complement of $\mathbb{D}$ including all
devices whose transmit powers are less than $P$. Lemma 1 indicates that
$\mathbb{D}$ is always non-empty, i.e., it contains at least one device. In
general, there can be more than a single device in $\mathbb{D}$.

We next state Lemma 2 which describes a key property of the devices in
$\bar{\mathbb{D}}$:

######  Lemma 2.

Let $\mathbf{m}^{\star}$ and $\left\\{b_{\ell}^{\star}\right\\}$ be given by
MMSE coordination. For any $\ell\in\bar{\mathbb{D}}$, i.e., any device
transmitting with power less than $P$, $b_{\ell}^{\star}$ satisfies

$\displaystyle
b_{\ell}^{\star}=\frac{\phi_{\ell}}{\mathbf{h}_{\ell}^{\mathsf{T}}\mathbf{m}^{\star}}.$

###### Proof.

The proof is given by contradiction following similar steps taken in the proof
of 1. We hence skip the details. ∎

To understand this result, let us consider the aggregation error in (9). Lemma
1 indicates that with MMSE coordination, the components in the first term of
the aggregation error that correspond to the devices in $\bar{\mathbb{D}}$,
i.e.,

$\displaystyle\left|\mathbf{m}^{\star\mathsf{T}}\mathbf{h}_{\ell}b^{\star}_{\ell}-\phi_{\ell}\right|^{2}=0.$
(19)

In other words, for these devices, MMSE coordination is similar to ZF, c.f.
(16), and only the devices in $\mathbb{D}$, i.e., those who transmit with
power $P$, contribute to the first term of the aggregation error.

We next connect the receiver given by MMSE coordination, i.e.,
$\mathbf{m}^{\star}$, to the devices in $\mathbb{D}$.

######  Lemma 3.

Let $\mathbf{m}^{\star}$ be given by MMSE coordination. Then, there exists
complex scalars $\alpha_{\ell}$ for $\ell\in\mathbb{D}$, such that

$\displaystyle\mathbf{m}^{\star}=\sum_{\ell\in\mathbb{D}}\alpha_{\ell}\mathbf{h}_{\ell}.$
(20)

###### Proof.

The proof follows the results of Lemmas 1 and 2. From Lemma 2, we know that

$\displaystyle\epsilon\left(\mathbf{m}^{\star},\left\\{b_{\ell}^{\star}\right\\}\right)$
$\displaystyle=\sum_{\ell\in\mathbb{D}}\left|\mathbf{m}^{\star\mathsf{T}}\mathbf{h}_{\ell}b^{\star}_{\ell}-\phi_{\ell}\right|^{2}+\sigma^{2}\left\|\mathbf{m}^{\star}\right\|^{2}.$
(21)

Lemma 1 further implies that for $\ell\in\mathbb{D}$, the scaling coefficient
is $b^{\star}_{\ell}=\sqrt{P}\mathrm{e}^{\mathrm{j}\varphi_{\ell}}$ for some
phase $\varphi_{\ell}$. Hence, we can write

$\displaystyle\epsilon\left(\mathbf{m}^{\star},\left\\{b_{\ell}^{\star}\right\\}\right)$
$\displaystyle=\sum_{\ell\in\mathbb{D}}\left|\mathbf{m}^{\star\mathsf{T}}\mathbf{h}_{\ell}\sqrt{P}\mathrm{e}^{\mathrm{j}\varphi_{\ell}}-\phi_{\ell}\right|^{2}+\sigma^{2}\left\|\mathbf{m}^{\star}\right\|^{2}$
$\displaystyle\leq\sum_{\ell\in\mathbb{D}}\left|\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}\sqrt{P}\mathrm{e}^{\mathrm{j}\varphi_{\ell}}-\phi_{\ell}\right|^{2}+\sigma^{2}\left\|\mathbf{m}\right\|^{2}$
(22)

for any $\mathbf{m}\in\mathbb{C}^{N}$. Note that
$\varphi_{\ell}=-\vartheta_{\ell}$ with $\vartheta_{\ell}$ being the phase of
$\mathbf{m}^{\star\mathsf{T}}\mathbf{h}_{\ell}$.

From (22), we can conclude that $\mathbf{m}^{\star}$ is the solution to444Note
that we can set $\varphi_{\ell}=0$ without loss of generality.

$\displaystyle\min_{\mathbf{m}\in\mathbb{C}^{N}}\sum_{\ell\in\mathbb{D}}\left|\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}\sqrt{P}-\phi_{\ell}\right|^{2}+\sigma^{2}\left\|\mathbf{m}\right\|^{2}$
(23)

that describes a regularized ZF problem. This implies that
$\mathbf{m}^{\star}$ only linearly depends on
$\left\\{\mathbf{h}_{\ell}:\ell\in\mathbb{D}\right\\}$ and components outside
the space spanned by these channel vectors only increase the objective
function in (23). This concludes the proof. ∎

Lemma 3 describes a genie-aided solution for the MMSE scheme: assume that set
$\mathbb{D}$ is known to us. MMSE coordination is then readily found as
follows: we first set,

$\displaystyle\mathbf{m}^{\star}$
$\displaystyle=\operatorname*{argmin}_{\mathbf{m}\in\mathbb{C}^{N}}\sum_{\ell\in\mathbb{D}}\left|\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}\sqrt{P}-\phi_{\ell}\right|^{2}+\sigma^{2}\left\|\mathbf{m}\right\|^{2}$
(24)
$\displaystyle=\operatorname*{argmin}_{\mathbf{m}\in\mathbb{C}^{N}}\left\|\sqrt{P}\mathbf{H}_{\mathbb{D}}^{\mathsf{T}}\mathbf{m}-\boldsymbol{\phi}_{\mathbb{D}}\right\|^{2}+\sigma^{2}\left\|\mathbf{m}\right\|^{2}$
(25)
$\displaystyle\stackrel{{\scriptstyle\dagger}}{{=}}\frac{1}{\sqrt{P}}\mathbf{H}_{\mathbb{D}}^{*}\left(\mathbf{H}_{\mathbb{D}}^{\mathsf{T}}\mathbf{H}_{\mathbb{D}}^{*}+\frac{\sigma^{2}}{P}\mathbf{I}_{D}\right)^{-1}\boldsymbol{\phi}_{\mathbb{D}},$
(26)

where $\mathbf{H}_{\mathbb{D}}\in\mathbb{C}^{N\times D}$ with
$D=\left|\mathbb{D}\right|$ is the reduced form of the channel matrix
$\mathbf{H}$ including only the columns of $\mathbf{H}$ whose indices are in
$\mathbb{D}$. Similarly, the vector $\boldsymbol{\phi}_{\mathbb{D}}$ is the
reduced form of $\boldsymbol{\phi}$. The identity $\dagger$ further follows
the regularized ZF solution. Having $\mathbf{m}^{\star}$, we then set
$b_{\ell}^{\star}=\sqrt{P}$ for $\ell\in\mathbb{D}$ and the remaining scaling
coefficients according to (2) in Lemma 2.

The results of Lemmas 1-3 imply that the main challenge in MMSE coordination
is to find set $\mathbb{D}$, i.e., the devices that need to transmit with
maximum power. This is in general an integer programming problem. In Section
VI, we propose a low-complexity algorithm to approximate this set. To state
this algorithm, we need first to present some analytical results on ZF
coordination. In the light of these results, we present our low-complexity
algorithm for MMSE coordination.

##  IV ZF Coordination for OTA-FL

ZF coordination sets the first term of the aggregation error to zero while
keeping the transmit powers below $P$. This leads to a closed-form scaling
coefficients, c.f. (16), and an expression for the receiver in terms of a
quadratic programming problem, i.e., (15). The ZF scheme can be seen as a
mismatched version of MMSE coordination in which the PS postulates noise to be
zero-variance. In this section, we invoke this interpretation and extend the
analytic results of Section III to ZF coordination.

We start the analysis by deriving a genie-aided form of ZF coordination. To
this end, we partition the devices into subsets $\mathbb{D}^{\mathrm{zf}}$ and
$\bar{\mathbb{D}}^{\mathrm{zf}}$ with the former denoting those that transmit
with maximum power $P$ and the latter being its complement. Similar to
$\mathbb{D}$, the set ${\mathbb{D}^{{\mathrm{zf}}}}$ cannot be empty.

######  Lemma 4.

With ZF coordination in the network, there is at least one device that
transmits with the maximum power $P$.

###### Proof.

The proof is given by contradiction following identical steps as in the proof
of Lemma 1. ∎

We can further develop a similar result as in Lemma 3 for ZF coordination: if
one knows $\mathbb{D}^{\mathrm{zf}}$; then, the receiver $\mathbf{m}^{\rm zf}$
is given by the following lemma.

######  Lemma 5.

Given ${\mathbb{D}^{{\mathrm{zf}}}}$, the receiver $\mathbf{m}^{\rm zf}$ in
(15) is given by

$\displaystyle\mathbf{m}^{\rm
zf}=\frac{1}{\sqrt{P}}\mathbf{H}_{\mathbb{D}^{{\mathrm{zf}}}}^{*}\left(\mathbf{H}_{\mathbb{D}^{{\mathrm{zf}}}}^{\mathsf{T}}\mathbf{H}_{\mathbb{D}^{{\mathrm{zf}}}}^{*}\right)^{-1}\boldsymbol{\phi}_{\mathbb{D}^{{\mathrm{zf}}}},$
(27)

and the aggregation error is

$\displaystyle\epsilon\left(\mathbf{m}^{\rm zf},\mathbf{B}^{\rm
zf}\right)=\frac{\sigma^{2}}{P}\boldsymbol{\phi}_{\mathbb{D}^{{\mathrm{zf}}}}^{\mathsf{T}}\left(\mathbf{H}_{\mathbb{D}^{{\mathrm{zf}}}}^{\mathsf{T}}\mathbf{H}_{\mathbb{D}^{{\mathrm{zf}}}}^{*}\right)^{-1}\boldsymbol{\phi}_{\mathbb{D}^{{\mathrm{zf}}}}.$
(28)

###### Proof.

The ZF scheme is a mismatched MMSE coordination scheme in which $\sigma^{2}$
is postulated to be zero. This implies that Lemma 3 is also valid for the ZF
scheme by replacing $\mathbb{D}$ with ${\mathbb{D}^{{\mathrm{zf}}}}$.
Consequently, $\mathbf{m}^{\mathrm{zf}}$ is given in terms of
${\mathbb{D}^{{\mathrm{zf}}}}$ from (26) by replacing $\mathbb{D}$ with
${\mathbb{D}^{{\mathrm{zf}}}}$ and setting $\sigma^{2}$ to zero. The
aggregation error is then derived by substituting $\mathbf{m}^{\mathrm{zf}}$
into (14). ∎

Lemma 5 implies the same fact about ZF coordination: similar to the MMSE
scheme, the root problem in ZF coordination is to find those devices that
transmit with the maximum power. It is worth mentioning that $\mathbb{D}$ and
${\mathbb{D}^{{\mathrm{zf}}}}$ are in general not identical; nevertheless, the
problem of finding these discrete subsets also reduces to an integer
programming problem. For the sake of brevity, we refer to this root problem as
the subset selection problem in the remaining of this paper.

##  V Subset Selection for ZF Coordination

The computational complexity of the subset selection problem grows
exponentially with the number of devices: there are in total $2^{L}-1$
possible choices555Note that the empty set does not occur according to Lemmas
1 and 4. for the device subset. Thus, the complete search algorithm poses
exponential complexity to the system. We hence look for a low-complexity
approach to find a good choice for the device subset.

We start the derivations by defining the concept of a feasible setting for ZF
coordination:

######  Definition 1.

The receiver $\mathbf{m}$ and coefficients $\left\\{b_{\ell}\right\\}$
describe a feasible ZF setting, if $\left|b_{\ell}\right|^{2}\leq P$ and
$\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}b_{\ell}=\phi_{\ell}$ for
$\ell\in\left[L\right]$.

A feasible ZF setting only applies ZF on the received signal, i.e., it sets
the first term in the right hand side of (9) zero, and ignores the
optimization in (15) that minimizes the aggregation error. In this respect, we
can see the ZF coordination scheme as a feasible ZF setting with minimal
aggregation error. It is further easy to show that a feasible ZF setting is
uniquely specified by its set of devices transmitting with power $P$:

######  Lemma 6.

Let $\mathbb{S}$ denote the set of devices which transmit with power $P$ in a
feasible ZF setting with receiver $\mathbf{m}$ and scaling coefficients
$\left\\{b_{\ell}\right\\}$. Then, $\mathbf{m}$ is given by

$\displaystyle\mathbf{m}=\frac{1}{\sqrt{P}}\mathbf{H}_{\mathbb{S}}^{*}\left(\mathbf{H}_{\mathbb{S}}^{\mathsf{T}}\mathbf{H}_{\mathbb{S}}^{*}\right)^{-1}\boldsymbol{\phi}_{\mathbb{S}},$
(29)

and $b_{\ell}$ is determined from (13) for $\ell\in\left[L\right]$.

###### Proof.

The proof takes exactly the same steps as in Lemma 5. We hence skip the proof.
∎

Considering the definition, we now focus on the number of feasible ZF setting
for coordination $C^{\mathrm{zf}}$. Following Lemmas 1 and 4, it is readily
concluded that

$\displaystyle C^{\mathrm{zf}}\leq 2^{L}-1.$ (30)

It is further easy to show that $C^{\mathrm{zf}}$ can be considerably smaller
than $2^{L}-1$: for a non-empty subset $\mathbb{S}\subseteq\left[L\right]$,
determine ${\mathbf{m}}$ and $b_{\ell}$ from Lemma 6. The scaling coefficients
are however not guaranteed to satisfy the transmit power constraint. Thus, the
described setting is not necessarily feasible for ZF coordination. This
observation implies that not all the $2^{L}-1$ settings determined by applying
ZF over the choices of $\mathbb{S}$ describe a feasible ZF setting, and hence
$C^{\mathrm{zf}}$ can be in general considerably smaller than $2^{L}-1$.

Considering the above behavior, an algorithmic approach for approximating the
ZF scheme is to track down the feasible ZF settings (or at least a subset of
them). If there are only a few of them, i.e., $C^{\mathrm{zf}}$ is small;
then, the ZF coordination scheme is readily found by a finite-dimensional
search. The following theorem describes the conditions under which the
feasible ZF settings and the ZF scheme are explicitly found.

######  Theorem 1.

Let $s$ be index of the device whose channel norm is smallest, i.e.,

$\displaystyle
s=\operatorname*{argmin}_{\ell\in\left[L\right]}\left\|\mathbf{h}_{\ell}\right\|,$
(31)

and define
${\mathrm{g}}_{\ell}=\mathbf{h}_{s}^{\mathsf{H}}\mathbf{h}_{\ell}/\phi_{\ell}$
for $\ell\in\left[L\right]$. Assume that
$\left|{\mathrm{g}}_{s}\right|\leq\left|{\mathrm{g}}_{\ell}\right|$ for all
$\ell\in\left[L\right]$ with equality holding for devices in set
$\mathbb{S}\subseteq\left[L\right]$. Then,
${\mathbb{D}^{{\mathrm{zf}}}}=\mathbb{S}$, i.e., only the device in
$\mathbb{S}$ transmit with the maximum power $P$. The ZF coordination scheme
in this case is described with

$\displaystyle\mathbf{m}^{\mathrm{zf}}=\frac{\phi_{s}\mathbf{h}_{s}^{*}}{\sqrt{P}\left\|\mathbf{h}_{s}\right\|^{2}}.$
(32)

###### Proof.

We start the proof by showing that the given setting is feasible for ZF
coordination. To this end, let $\mathbf{m}=\mathbf{m}^{\mathrm{zf}}$ as given
in the theorem and $b_{s}=\sqrt{P}$. We first note that

$\displaystyle\mathbf{m}^{\mathsf{T}}\mathbf{h}_{s}b_{s}=\phi_{s},$ (33)

which satisfies the ZF constraint (13) for device $s$. For other devices, we
apply ZF by setting

$\displaystyle b_{\ell}$
$\displaystyle=\frac{\phi_{\ell}}{\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}}=\frac{\phi_{\ell}\left\|\mathbf{h}_{s}\right\|^{2}}{\phi_{s}\mathbf{h}_{s}^{\mathsf{H}}\mathbf{h}_{\ell}}\sqrt{P}=\frac{{\mathrm{g}}_{s}}{{\mathrm{g}}_{\ell}}\sqrt{P}.$
(34)

This is hence concluded that under the constraint
$\left|{\mathrm{g}}_{s}\right|\leq\left|{\mathrm{g}}_{\ell}\right|$, this ZF
setting is feasible. Moreover, it is concluded that in this case, all devices
with $\left|{\mathrm{g}}_{\ell}\right|=\left|{\mathrm{g}}_{s}\right|$ transmit
with power $P$.

We now show that the described feasible ZF setting is in fact the ZF scheme
with minimal aggregation error. To this end, let $\mathbf{m}^{\mathrm{zf}}$
and $\left\\{b_{\ell}^{\mathrm{zf}}\right\\}$ denote the receiver and scaling
coefficients of the ZF scheme, respectively. We decompose
$\mathbf{m}^{\mathrm{zf}}$ in terms of its projection on $\mathbf{h}_{s}^{*}$
and its component in the null space of $\mathbf{h}_{s}^{*}$, i.e.,

$\displaystyle\mathbf{m}^{\mathrm{zf}}=c\;\mathbf{h}_{s}^{*}+c_{\perp}\mathbf{h}_{s}^{\perp*}$
(35)

for some constants $c$ and $c_{\perp}$ and $\mathbf{h}_{s}^{\perp}$ being a
vector orthogonal to $\mathbf{h}_{s}$, i.e.,
$\mathbf{h}_{s}^{\mathsf{H}}\mathbf{h}_{s}^{\perp}=0$. To fulfill the ZF
condition for device $s$, we need to have
$\mathbf{m}^{{\mathrm{zf}}\mathsf{T}}\mathbf{h}_{s}=0$. This concludes that

$\displaystyle c=\frac{\phi_{s}}{\left\|\mathbf{h}_{s}\right\|^{2}b_{s}},$
(36)

and noting that $\left|b_{s}\right|^{2}\leq P$, we should set

$\displaystyle\left|c\right|\geq\frac{\phi_{s}}{\left\|\mathbf{h}_{s}\right\|^{2}\sqrt{P}}.$
(37)

Considering (14), we conclude that the aggregation error is

$\displaystyle\epsilon\left(\mathbf{m}^{\mathrm{zf}},\left\\{b_{\ell}^{\mathrm{zf}}\right\\}\right)=\sigma^{2}\left(\left|c\right|^{2}\;\left\|\mathbf{h}_{s}\right\|^{2}+\left|c_{\perp}\right|^{2}\left\|\mathbf{h}_{s}^{\perp}\right\|^{2}\right)$
(38)

that is minimized by setting $\left|c\right|$ to its lower bound in (37) and
$c_{\perp}=0$. This describes the feasible ZF setting with minimal aggregation
error. Hence, the proof is concluded. ∎

Theorem 1 describes a sufficient condition under which the ZF scheme is
determined closed-form. This condition is very likely to hold in practical
scenarios in which few devices have significantly larger path-losses as
compared with the others edge devices in the network. We consider an example
of such a scenario throughout the numerical investigations. It is worth
mentioning that in a homogeneous setting, i.e., $\phi_{\ell}=\phi$ for
$\ell\in\left[L\right]$, with a single-antenna PS, the sufficient condition in
Theorem 1 always hold. This is obvious, since in this case only the device
with weakest channel should transmit with the maximum power for ZF
coordination666Note that for MMSE coordination, this is in general not true,
as also shown for a mathematically-similar problem in [25]..

###  V-A ZF Coordination without Closed-Form Solution

If the sufficient condition in Theorem 1 does not hold, ZF coordination is
found by searching over all feasible settings. This search procedure is
exponentially hard. We hence develop a tractable algorithm which approximates
the solution by polynomial complexity. In this respect, the following lemma,
can be further useful to limit our search

######  Lemma 7.

If the condition in Theorem 1 does not hold; then, there are at least two
devices which transmit with the maximum power $P$ in ZF coordination.

###### Proof.

The proof is readily given by contradiction. We hence skip it here. ∎

Considering Lemma 7 and the earlier results on ZF coordination, we can have
the following statements about the optimal ZF scheme, when it is not given by
Theorem 1:

  * •

It is a feasible ZF setting.

  * •

There are at least two devices with transmit power $P$.

We further note that when all the devices transmit with power $P$, a feasible
ZF setting is always guaranteed to be determined: let $b_{\ell}=\sqrt{P}$ for
$\ell\in\left[L\right]$ and $\mathbf{m}$ to be the one given in Lemma 5 for
${\mathbb{D}^{{\mathrm{zf}}}}=\left[L\right]$. These findings leads to this
heuristic conclusion that a good approximate for the optimal ZF scheme is
given by finding a feasible ZF setting with minimal number of devices
transmitting with power $P$. This heuristic conclusion leads us to a tree-
based algorithm which is presented in the sequel.

######  Remark 1.

As mentioned in Section II, throughout the paper we assume $N\geq L$. This
however does not restrict the scope of analyses. In fact, the derivations are
further valid for settings with $N<L$ when we limit the subset selection
problem to be solved for subsets with $\left|\mathbb{S}\right|\leq N$.

###  V-B A Tree-Based Search Scheme

We now present a tree-based algorithm to find the optimal ZF scheme. Although
its core idea comes from our heuristic conclusions, it is shown that with full
complexity this algorithm is exact. Before we present the algorithm, we state
the following lemma which serves as the analytical foundation of the tree-
based algorithm:

######  Lemma 8.

Let $\left(\mathbf{m}_{1},\left\\{b_{1\ell}\right\\}\right)$ and
$\left(\mathbf{m}_{2},\left\\{b_{2\ell}\right\\}\right)$ describe two feasible
ZF setting for coordination. Denote the set of devices transmitting with power
$P$ in these two settings with $\mathbb{S}_{1}$ and $\mathbb{S}_{2}$,
respectively. If $\mathbb{S}_{1}\subseteq\mathbb{S}_{2}$; then,

$\displaystyle\epsilon\left(\mathbf{m}_{1},\left\\{b_{1\ell}\right\\}\right)\leq\epsilon\left(\mathbf{m}_{2},\left\\{b_{2\ell}\right\\}\right).$
(39)

###### Proof.

The proof is readily concluded by the fact that the feasible region of the
error minimization problem for subset $\mathbb{S}_{1}$ contains the feasible
region of the optimization problem defined with subset $\mathbb{S}_{2}$. This
implies that the error obtained by the former minimization is smaller than the
one in the latter. This concludes the proof. ∎

The above result implies that while searching for the optimal ZF coordination,
those feasible ZF settings whose corresponding subsets include other feasible
subsets can be further ignored777From Lemma 7, we further conclude that this
search is restricted to $\left|S\right|\geq 2$.. We hence can graphically
visualize the search for the optimal feasible setting via a tree: consider a
graph whose nodes denote those subsets of $\left[L\right]$ that describe
feasible ZF settings. The node corresponding to
$\mathbb{S}\subseteq\left[L\right]$ is connected to its children which are the
subsets of $\mathbb{S}$ describing feasible ZF settings. Any set
$\mathbb{S}\neq\left[L\right]$ is further connected to its parent which is the
feasible ZF set $\tilde{\mathbb{S}}$ containing $\mathbb{S}$, i.e.,
$\mathbb{S}\subset\tilde{\mathbb{S}}$. If there are multiple choices for the
parent of $\mathbb{S}$; then, the set with largest cardinality is
selected888If there are multiple nodes with largest cardinality, the we choose
the parent among them at random.. This way we built a tree whose root is
$\left[L\right]$ and whose cardinality of the sets corresponding to the nodes
decreases as we move towards the leaves.

######  Example 1.

Consider a network with $L=4$ edge devices and $N=5$ antennas at the PS. Let
$\phi_{\ell}=0.25$ for all devices and $P=1$. The channel matrix is further as
follows

$\displaystyle\mathbf{H}=\begin{bmatrix}0.30&0.46&0.39&0.19\\\
-0.55&0.32&-0.52&0.04\\\ 0.32&-0.14&-0.48&-0.11\\\ 0.72&0.13&-0.37&0.18\\\
0.21&-0.36&-1.32&-0.23\\\ \end{bmatrix}.$ (40)

The ZF tree for this network is shown in Fig. 1. As observed, the root is
$\left\\{1,2,3,4\right\\}$.

Figure 1: Tree representation of feasible ZF settings for Example 1.

Lemma 8 implies that the optimal ZF scheme with minimal aggregation error is
among the leaves of the tree representing ZF feasible settings. Therefore, the
problem of finding the optimal ZF scheme reduces to a search for the leaf with
minimal error, i.e., the leaf with minimal norm of the receiver. It is worth
mentioning that this search is still exponentially complex, since in general
construction of the tree requires $2^{L}-1$ feasibility checks. Its visual
representation however describes a tractable approximation approach: starting
from the root, we move towards the leaves in a step-wise fashion. In each
step, we go from a parent to the child whose aggregation error is minimum
among all the children. The search is finally over as we arrive at a leaf.
This leaf is taken as the approximate of the solution.

###  V-C Approximate ZF Coordination

The proposed tree-based search lead to an approximation of ZF coordination
which we refer to as approximate ZF (AZF). The details on this algorithm are
as follows:

  1. 1.

We initiate the search at the root of the tree by setting
$\mathbb{S}^{(0)}=\left[L\right]$. The initial receiver $\mathbf{m}^{(0)}$ and
scaling coefficients are further found via Lemma 6.

  2. 2.

At step $i$, we consider all subsets of $\mathbb{S}^{(i)}$ that differ with
$\mathbb{S}^{(i)}$ in only one element. For each subset, we determine the
receiver from $\mathbf{m}^{(i)}$ and the corresponding channel vectors via
rank-one update of matrix inverse; see [26]. We then calculate the scaling
coefficients and check if they satisfy the transmit power constraint. If the
power constraint is satisfied, we collect the subset as a feasible ZF subset
of $\mathbb{S}^{(i)}$.

  3. 3.

Among the feasible ZF subsets of $\mathbb{S}^{(i)}$, we set
$\mathbb{S}^{(i+1)}$ to be the one whose receiver has minimal norm.

The algorithm stops at step $i_{\rm T}$, where there is no feasible ZF subsets
for the set $\mathbb{S}^{(i_{\rm T})}$.

The AZF scheme needs to search among $L\left(L+1\right)/2$ subsets in the
worst-case scenario, and hence is computationally tractable. It can be further
extended by considering multiple dominant paths of the tree. Such an extension
can potentially lead to a more accurate approximation of the ZF scheme at the
expense of higher computational complexity.

##  VI Subset Selection for MMSE Coordination

We now get back to the MMSE scheme and utilize the framework developed for ZF
coordination to design a tractable algorithm for approximating the MMSE
scheme. We start the derivations by defining the less-intuitive concept of a
feasible MMSE setting. Before stating the definition, let us look back to the
key properties of the MMSE scheme: from Lemmas 1 and 2, we know that the
scaling coefficients in this scheme are either $\sqrt{P}$ or satisfy the ZF
constraint. We further note that given the set of devices transmitting with
power $P$, the receiver can be found via (26). These features are dual to
those satisfied by the ZF scheme. We hence invoke Definition 1 and define a
feasible setting for MMSE coordination as follows:

######  Definition 2.

Consider the subset of devices $\mathbb{S}\subseteq\left[L\right]$ whose
cardinality is $\left|\mathbb{S}\right|=S$. Let $\mathbf{m}$ be

$\displaystyle\mathbf{m}=\frac{1}{\sqrt{P}}\mathbf{H}_{\mathbb{S}}^{*}\left(\mathbf{H}_{\mathbb{S}}^{\mathsf{T}}\mathbf{H}_{\mathbb{S}}^{*}+\frac{\sigma^{2}}{P}\mathbf{I}_{S}\right)^{-1}\boldsymbol{\phi}_{\mathbb{S}}.$
(41)

Let $\left|b_{\ell}\right|=\sqrt{P}$ for $\ell\in\mathbb{S}$ and determine
$b_{\ell}$ for $\ell\notin\mathbb{S}$ from the equation
$\mathbf{m}^{\mathsf{T}}\mathbf{h}_{\ell}b_{\ell}=\phi_{\ell}$. The set
$\mathbb{S}$ is said to describe a feasible MMSE setting for coordination, if
$\left|b_{\ell}\right|^{2}<P$ for $\ell\notin\mathbb{S}$.

Lemmas 1 and 2 along with (26) imply that the subset of devices transmitting
with power $P$ in the MMSE scheme, i.e., $\mathbb{D}$, describes a feasible
MMSE setting. In other words, similar to ZF coordination, this definition
relaxes the MMSE scheme by dropping the optimality constraint. We next follow
the same steps as for ZF coordination to show that the MMSE scheme is given by
searching over the tree of feasible settings for the smallest subset.

###  VI-A Properties of Feasible MMSE Settings

Similar to Theorem 1, a sufficient condition can be derived for MMSE
coordination, under which the set $\mathbb{D}$, and thus the MMSE scheme, is
determined in closed-form.

######  Theorem 2.

Let $s$ be index of the device whose channel norm is smallest, i.e.,

$\displaystyle
s=\operatorname*{argmin}_{\ell\in\left[L\right]}\left\|\mathbf{h}_{\ell}\right\|.$
(42)

Define the vector $\mathbf{g}$ as

$\displaystyle\mathbf{g}=\boldsymbol{\Phi}^{-1}\left(\mathbf{H}^{\mathsf{H}}\mathbf{h}_{s}+\frac{\sigma^{2}}{P}\mathbf{o}_{s}\right),$
(43)

where $\boldsymbol{\Phi}=\mathrm{Diag}\left\\{\phi_{\ell}\right\\}$ and
$\mathbf{o}_{s}\in\left\\{0,1\right\\}^{L}$ is a vector with a single non-zero
entry at index $s$. Denote the entry $\ell$ of $\mathbf{g}$ with
${\mathrm{g}}_{\ell}$ and assume that
$\left|{\mathrm{g}}_{s}\right|\leq\left|{\mathrm{g}}_{\ell}\right|$ for all
$\ell\in\left[L\right]$ with equality holding for devices in set
$\mathbb{S}\subseteq\left[L\right]$. Then, $\mathbb{D}=\mathbb{S}$, i.e., only
the device in $\mathbb{S}$ transmit with the maximum power $P$. The MMSE
coordination scheme in this case is described with

$\displaystyle\mathbf{m}^{\star}=\frac{\sqrt{P}\phi_{s}\mathbf{h}_{s}^{*}}{P\left\|\mathbf{h}_{s}\right\|^{2}+\sigma^{2}}.$
(44)

###### Proof.

The proof follows similar steps as those taken for the proof of Theorem 1. We
hence skip the details. ∎

Theorem 1 describes the sufficient condition for tractable calculation of the
MMSE scheme. For networks which do not satisfy this condition, one can show
that similar findings, as those given in Sections V-A and V-B for ZF
coordination, are reported as well in this case. In particular, we can show
that feasible MMSE settings reduce in aggregation error as their corresponding
subset of devices with maximum transmit power shrinks.

######  Lemma 9.

Let $\left(\mathbf{m}_{1},\left\\{b_{1\ell}\right\\}\right)$ and
$\left(\mathbf{m}_{2},\left\\{b_{2\ell}\right\\}\right)$ describe two feasible
MMSE settings for coordination whose corresponding subsets are
$\mathbb{S}_{1}$ and $\mathbb{S}_{2}$, respectively. If
$\mathbb{S}_{1}\subseteq\mathbb{S}_{2}$; then,

$\displaystyle\epsilon\left(\mathbf{m}_{1},\left\\{b_{1\ell}\right\\}\right)\leq\epsilon\left(\mathbf{m}_{2},\left\\{b_{2\ell}\right\\}\right).$
(45)

###### Proof.

The proof is similar to the proof of Lemma 8. ∎

###  VI-B Approximate MMSE Coordination

Lemma 9 indicates that the MMSE scheme can be found by searching for the MMSE
feasible setting with smallest subset. We hence follow the same approach as in
Section V-B and build the tree of feasible MMSE schemes. Due to its
similarity, we skip the definition of the tree and refer the reader to Section
V-B. We now approximately find the MMSE scheme by moving step-wise from the
root towards the leaves while in each step we choose the child whose
aggregation error is minimum among all the children connected to the parent.

The proposed tree-based search algorithm for MMSE coordination can be
summarized as follows:

  1. 1.

We initiate the search at the root of the tree by setting
$\mathbb{S}^{(0)}=\left[L\right]$. The initial receiver $\mathbf{m}^{(0)}$ and
scaling coefficients are further found from Definition 2.

  2. 2.

At step $i$, we consider all subsets of $\mathbb{S}^{(i)}$ that differ with
$\mathbb{S}^{(i)}$ in only one element. For each subset, we determine the
receiver from $\mathbf{m}^{(i)}$ and the channel vectors via rank-one update.
We then calculate the scaling coefficients and check if they describe a
feasible MMSE setting.

  3. 3.

Among the feasible MMSE subsets of $\mathbb{S}^{(i)}$, we set
$\mathbb{S}^{(i+1)}$ to be the one whose aggregation error is minimum.

The algorithm stops, when no feasible MMSE subsets is found. We refer to this
algorithm in the sequel as approximate MMSE (AMMSE) scheme.

$-10$$-5$$0$$5$$10$$15$$20$$-20$$-10$$0$$10$$\log\mathrm{SNR}$ in
[dB]$\log\epsilon\left(\mathbf{m},\mathbf{B}\right)$ in [dB]Optimal ZFOptimal
MMSEAZFAMMSE Figure 2: Aggregation error against SNR for the ZF and MMSE
schemes with $N=8$ PS antennas and $L=4$ devices. The tree-based reduced
searches lie on the optimal schemes.
$-10$$-5$$0$$5$$10$$15$$20$$-25$$-15$$-5$$5$$15$$25$$\log\mathrm{SNR}$ in
[dB]$\log\epsilon\left(\mathbf{m},\mathbf{B}\right)$ in [dB]Optimal ZF - Equal
pathlossOptimal MMSE - Equal pathlossAZF - Equal pathlossAMMSE - Equal
pathlossOptimal ZF - Unequal pathlossOptimal MMSE - Unequal pathlossAZF -
Unequal pathlossAMMSE - Unequal pathloss Figure 3: Aggregation error against
SNR for the ZF and MMSE schemes with $N=8$ PS antennas and $L=4$ devices. ZF
shows less robustness against asymmetric device distribution.

##  VII Numerical results

In the section, we examine the efficiency of the proposed algorithms through
numerical experiments. To this end, we consider a simple network whose uplink
channels experience a standard i.i.d. Rayleigh fading process with fixed path-
loss. The channel coefficients are hence written as
$h_{\ell,n}=t_{\ell}f_{\ell,n}$, where $f_{\ell,n}\sim\mathcal{CN}(0,1/N)$
models small-scale fading, and $t_{\ell}$ captures the path-loss between the
PS and device $\ell$. We further assume an FL setting in which
$\phi_{\ell}=1/L$ for $\ell\in\left[L\right]$.

In this network, we coordinate the devices using the proposed scheme, i.e.,
AZF and AMMSE. For sake of comparison, we further evaluate the optimal ZF and
MMSE schemes by performing a complete search over the leaves of their
corresponding trees. To keep the simulations for the optimum case tractable,
we limit the number of devices in the network.

###  VII-A Coordination Performance

Fig. 2 shows the aggregation error against the signal-to-noise ratio (SNR) in
the network, defined as $\mathrm{SNR}={P}/{\sigma^{2}}$, for $L=4$ and $N=8$.
For this figure, the path-losses are set to $t_{\ell}=1$ for
$\ell\in\left[L\right]$. As the figure shows, for a small number of devices,
the approximate schemes, i.e., AZF and AMMSE, perform optimally.

We next investigate the impact of network asymmetry on both the coordination
approaches in Fig. 3, where we plot the same figure for two different
scenarios: the first scenario is as the one considered in Fig. 2, and the
other considers the setting in which the path-loss of one of the devices is
$10$ dB below the others. As shown in the figure, ZF coordination is more
sensitive to the non-uniformity of the path-losses as compared to the MMSE
scheme. This is in particular severe at low SNRs which is often the case in
current wireless networks.

$1$$2$$3$$4$$5$$6$$7$$8$$-16$$-14$$-12$load
$\xi=N/L$$\log\epsilon\left(\mathbf{m},\mathbf{B}\right)$ in [dB]Optimal
ZFOptimal MMSEAZFAMMSE Figure 4: Aggregation error against load for the ZF and
MMSE schemes with $\log\mathrm{SNR}=10$ dB and $L=4$ devices.

As the next experiment, we plot the aggregation error against the load of the
system that is defined as $\xi=N/L$ in Fig. 4. For numerical tractability of
the optimal schemes, we set $L=4$. The SNR is further set to
$\log\mathrm{SNR}=12$ dB, and the path-loss is set to $t_{\ell}=1$ for
$\ell\in\left[L\right]$. As observed, the tree-base approximates closely track
the optimal schemes. Furthermore, the gap between the optimal and approximated
schemes shrinks as the load grows.

###  VII-B Complexity of the Proposed Schemes

As a metric of complexity, we define the check time to be the number of
subsets being checked in the tree-based search of the algorithm. Fig. 5 and
Fig. 6 show the average check time for AZF or AMMSE algorithms against the SNR
and load, respectively. Here, $L=4$ and $N=8$, and the check time is averaged
over multiple channel realizations. The devices are assumed to be uniformly
distributed in the network, i.e., the path-loss is assumed to the same for all
the devices. As the figures depict, the complexity of the AZF scheme only
varies against the load, while the complexity of the AMMSE scheme scales with
both the load and channel quality. The figures further demonstrate that the
check time for AMMSE is always less than AZF. This is a favorable behavior,
since AMMSE leads to less aggregation error, as well. Fig. 6 further implies
that the average check time of both the algorithms reduces by growth of $N$
and converges to $L+1$. This follows the fact that at high system loads, the
channel vectors become statistically orthogonal, and hence all the devices
transmit with the maximum power. As the result, both the algorithms stop at
the root, after checking the feasibility of their $L$ children.

$-10$$0$$10$$20$$30$$5$$6$$7$$\log\mathrm{SNR}$ in [dB]average check
timeAZFAMMSE Figure 5: Average check time against SNR for the ZF and MMSE
schemes with $N=8$ PS antennas and $L=4$ devices.
$1$$2$$3$$4$$5$$6$$7$$8$$5$$6$$7$$8$$9$load $\xi=N/L$average check
timeAZFAMMSE Figure 6: Average check time against load for the ZF and MMSE
schemes with $\log\mathrm{SNR}=10$ dB and $L=4$ devices.

As the last experiment, we investigate the impacts of a non-uniform
distribution of the device in the network on tree-based search complexity.
Fig. 7 shows the average check time for the same setting as in Fig. 6, when
one of the devices is located, such that its path-loss is $10$ dB below the
path-losses of the other devices. As the figure shows, this asymmetry
increases even further the gap between the complexity of AZF and AMMSE leading
to this conclusion that AMMSE proposes a more robust behavior as compared with
the AZF.

$1$$2$$3$$4$$5$$6$$7$$8$$5$$7$$9$$11$load $\xi=N/L$average check timeAZFAMMSE
Figure 7: Average check time against load for the ZF and MMSE schemes with
$\log\mathrm{SNR}=10$ dB and $L=4$ devices in a network with asymmetric device
distribution.

##  VIII Conclusions

Low-complexity algorithms have been proposed for MMSE and ZF coordination in
OTA-FL. The algorithms find efficient approximation of the optimal MMSE and ZF
schemes using a tree-based search algorithm which solves the equivalent subset
selection problem. Our numerical investigations depict that the proposed
algorithms track closely the optimal schemes.

The analytical results of this study indicate that both the MMSE and ZF
coordination schemes deal with the same level of hardness, while the former
leads to a lower aggregation error. The numerical investigations further
reveal that the tree-based approximation of MMSE coordination results in less
computational complexity and more robustness as compared to the approximated
ZF scheme. Considering the favorable behavior of the MMSE scheme with respect
to performance and complexity, one concludes that MMSE is a better approach
for device coordination in OTA-FL.

## References

  * [1] T. Li, A. K. Sahu, A. Talwalkar, and V. Smith, “Federated learning: Challenges, methods, and future directions,” _IEEE Signal Processing Magazine_ , vol. 37, no. 3, pp. 50–60, 2020.
  * [2] J. Konečnỳ, H. B. McMahan, D. Ramage, and P. Richtárik, “Federated optimization: Distributed machine learning for on-device intelligence,” _arXiv preprint arXiv:1610.02527_ , 2016.
  * [3] K. Bonawitz, H. Eichner, W. Grieskamp, D. Huba, A. Ingerman, V. Ivanov, C. Kiddon, J. Konečnỳ, S. Mazzocchi, B. McMahan _et al._ , “Towards federated learning at scale: System sesign,” _Proceedings of Machine Learning and Systems_ , vol. 1, pp. 374–388, 2019.
  * [4] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, A. N. Bhagoji, K. Bonawitz, Z. Charles, G. Cormode, R. Cummings _et al._ , “Advances and open problems in federated learning,” _Foundations and Trends® in Machine Learning_ , vol. 14, no. 1–2, pp. 1–210, 2021\.
  * [5] M. Aledhari, R. Razzak, R. M. Parizi, and F. Saeed, “Federated learning: A survey on enabling technologies, protocols, and applications,” _IEEE Access_ , vol. 8, pp. 140 699–140 725, 2020.
  * [6] J. Ding, E. Tramel, A. K. Sahu, S. Wu, S. Avestimehr, and T. Zhang, “Federated learning challenges and opportunities: An outlook,” in _International Conference on Acoustics, Speech and Signal Processing (ICASSP)_. IEEE, 2022, pp. 8752–8756.
  * [7] K. Wei, J. Li, M. Ding, C. Ma, H. H. Yang, F. Farokhi, S. Jin, T. Q. Quek, and H. V. Poor, “Federated learning with differential privacy: Algorithms and performance analysis,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 3454–3469, 2020.
  * [8] M. Fredrikson, S. Jha, and T. Ristenpart, “Model inversion attacks that exploit confidence information and basic countermeasures,” in _Proceedings of the 22nd ACM SIGSAC conference on computer and communications security_ , 2015, pp. 1322–1333.
  * [9] J. So, B. Güler, and A. S. Avestimehr, “Byzantine-resilient secure federated learning,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 7, pp. 2168–2181, 2020.
  * [10] H. Zhu, J. Xu, S. Liu, and Y. Jin, “Federated learning on non-iid data: A survey,” _Neurocomputing_ , vol. 465, pp. 371–390, 2021.
  * [11] F. Sattler, S. Wiedemann, K.-R. Müller, and W. Samek, “Robust and communication-efficient federated learning from non-iid data,” _IEEE transactions on neural networks and learning systems_ , vol. 31, no. 9, pp. 3400–3413, 2019.
  * [12] Y. Shi, K. Yang, T. Jiang, J. Zhang, and K. B. Letaief, “Communication-eefficient edge ai: Algorithms and systems,” _IEEE Communications Surveys & Tutorials_, vol. 22, no. 4, pp. 2167–2191, 2020.
  * [13] M. Duan, D. Liu, X. Chen, Y. Tan, J. Ren, L. Qiao, and L. Liang, “Astraea: Self-balancing federated learning for improving classification accuracy of mobile deep learning applications,” in _2019 IEEE 37th international conference on computer design (ICCD)_. IEEE, 2019, pp. 246–254.
  * [14] J. Mills, J. Hu, and G. Min, “Communication-efficient federated learning for wireless edge intelligence in IoT,” _IEEE Internet of Things Journal_ , vol. 7, no. 7, pp. 5986–5994, 2019.
  * [15] M. M. Amiri and D. Gündüz, “Machine learning at the wireless edge: Distributed stochastic gradient descent over-the-air,” _IEEE Transactions on Signal Processing_ , vol. 68, pp. 2155–2169, 2020.
  * [16] H. Hellström, V. Fodor, and C. Fischione, “Over-the-air federated learning with retransmissions,” in _2021 IEEE 22nd International Workshop on Signal Processing Advances in Wireless Communications (SPAWC)_. IEEE, 2021, pp. 291–295.
  * [17] K. Yang, T. Jiang, Y. Shi, and Z. Ding, “Federated learning via over-the-air computation,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 3, pp. 2022–2035, 2020.
  * [18] B. Nazer and M. Gastpar, “Computation over multiple-access channels,” _IEEE Transactions on information theory_ , vol. 53, no. 10, pp. 3498–3516, 2007.
  * [19] C. Xu, S. Liu, Z. Yang, Y. Huang, and K.-K. Wong, “Learning rate optimization for federated learning exploiting over-the-air computation,” _IEEE Journal on Selected Areas in Communications_ , vol. 39, no. 12, pp. 3742–3756, 2021.
  * [20] X. Cao, G. Zhu, J. Xu, Z. Wang, and S. Cui, “Optimized power control design for over-the-air federated edge learning,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 1, pp. 342–358, 2021.
  * [21] X. Fan, Y. Wang, Y. Huo, and Z. Tian, “1-bit compressive sensing for efficient federated learning over the air,” _IEEE Transactions on Wireless Communications_ , 2022.
  * [22] X. Cao, G. Zhu, J. Xu, and S. Cui, “Transmission power control for over-the-air federated averaging at network edge,” _IEEE Journal on Selected Areas in Communications_ , vol. 40, no. 5, pp. 1571–1586, 2022.
  * [23] S. Lee, C. Park, S.-N. Hong, Y. C. Eldar, and N. Lee, “Bayesian federated learning over wireless networks,” _arXiv preprint arXiv:2012.15486_ , 2020\.
  * [24] A. Bereyhi, A. Vagollari, S. Asaad, R. R. Müller, W. Gerstacker, and H. V. Poor, “Matching pursuit based scheduling for over-the-air federated learning,” _arXiv preprint arXiv:2206.06679_ , 2022.
  * [25] W. Liu, X. Zang, Y. Li, and B. Vucetic, “Over-the-air computation cystems: Optimization, analysis and scaling laws,” _IEEE Transactions on Wireless Communications_ , vol. 19, no. 8, pp. 5488–5502, 2020.
  * [26] W. W. Hager, “Updating the inverse of a matrix,” _SIAM review_ , vol. 31, no. 2, pp. 221–239, 1989.