# Distributed Beamforming for Agents with Localization Errors

Erfaun Noorani 1 , Yagiz Savas 2 , Alec Koppel 3, John Baras 1, Ufuk Topcu 2,
and Brian M. Sadler 3  E. Noorani and Y. Savas contributed equally to this
work. This work is supported by the grant ARL DCIST CRA W911NF-17-2-0181. E.
Noorani is a Clark Doctoral Fellow at the Clark School of Engineering.
1Department of Electrical and Computer Engineering and Institute for Systems
Research at University of Maryland, College Park 20742, USA. E-mails:
<EMAIL_ADDRESS>2Department of Aerospace Engineering and Engineering
Mechanics, University of Texas, Austin, TX 78712, USA. E-mails: {yagiz.savas,
<EMAIL_ADDRESS>3U.S. Army Research Laboratory, Adelphi, MD 20783, USA.
E-mails: {alec.e.koppel.civ<EMAIL_ADDRESS>
###### Abstract

We consider a scenario in which a group of agents aim to collectively transmit
a message signal to a client through beamforming. In such a scenario, we
investigate the effects of uncertainty in the agents’ local positions on the
quality of the communication link formed between the agents and the client. We
measure the quality of the communication link by the magnitude of the
beamforming gain which is a random variable due to the agents’ localization
errors. To ensure the existence of a reliable communication link despite the
agents’ localization errors, we formulate a subset selection problem which is
to select a subset of agents that minimizes the variance of the beamforming
gain while ensuring that the expected beamforming gain exceeds a desired
threshold. We first develop two greedy algorithms, greedy and double-loop-
greedy, each of which returns a globally optimal solution to the subset
selection problem under certain sufficient conditions on the maximum
localization error. Then using the functional properties of the variance and
expected value of the beamforming gain, we develop a third algorithm,
difference-of-submodular, which returns a locally optimal solution to a
certain relaxation of the subset selection problem regardless of the maximum
localization error. Finally, we present numerical simulations to illustrate
the performance of the proposed algorithms as a function of the total number
of agents, maximum localization error, and the expected beamforming gain
threshold.

##  I Introduction

Beamforming is a technique for wireless communication in which the phases of
antenna array elements are selected to induce constructive or destructive
interference in desired directions [1]. The theory of beamforming is well-
developed [2], and its applications are ubiquitous [3]. Distributed
beamforming refers to a beamforming scheme where the antenna elements, e.g.,
mobile robots equipped with small-size antennas [4], are distributed over a
wireless network and cooperatively organize to a virtual array. In this paper,
we study the effect of uncertainty in the positions of the antenna elements,
to which we refer to as the agents, on the quality of the communication link
formed between the agents and a client.

In distributed beamforming, the main objective is to set the phases of the
signals transmitted by the agents such that the beamforming gain, i.e., a
quantity proportional to the signal-to-noise-ratio of the signal received by
the client, is maximized [2]. When the related system parameters are perfectly
known, one can attain the maximum beamforming gain by including all the agents
to beamforming array and setting their phases appropriately [5]. The presence
of uncertainties in the system parameters, on the other hand, significantly
affects the applicability of the classical theory. For instance, the effects
of phase estimation errors in linear arrays [6] and phase jitters [7] cause
possible antennae misalignment, and thus, result in interference patterns
which preclude forming a reliable communications link.

In the presence of localization errors, even though including all the agents
to beamforming array still maximizes the expected beamforming gain, it may
deteriorate the quality of the communication link by decreasing the
probability that the actual beamforming gain is above a certain threshold.
Therefore, in order to ensure the existence of a reliable communication link
between the agents and the client, it may sometimes be desirable to include
only a subset of the agents to the beamforming array. Assuming that the
agents’ local positions follow a Gaussian distribution with known mean and
variance, we consider the variance of the beamforming gain as a risk measure
and develop algorithms to select a subset of agents that minimizes the
variance of the beamforming gain while ensuring that the expected beamforming
gain is above a desired threshold.

We first show that, when all the agents’ localization errors are below a
certain threshold, a simple greedy selection algorithm returns a globally
optimal solution to the formulated subset selection problem. We then
illustrate with a numerical example that the greedy selection does not always
minimize the considered risk measure. By slightly modifying the greedy
algorithm to improve its empirical performance when the agents’ localization
errors violate the aforementioned threshold, we obtain the double-loop-greedy
algorithm which has the same theoretical optimality guarantees with the greedy
algorithm.

We also develop another algorithm, which we refer to as the difference-of-
submodular algorithm, which utilizes the functional properties of the mean and
variance of the beamforming gain and returns a locally optimal solution to a
certain relaxation of the subset selection problem regardless of the magnitude
of the agents’ localization errors. Specifically, we show that both the mean
and variance of the beamforming gain are supermodular set functions. Then,
considering the expected beamforming gain as a regularization term instead of
a constraint in the subset selection problem, we utilize the submodular-
supermodular procedure developed in [8] to find a locally optimal solution to
the resulting optimization problem.

Notation: We denote the set $(-\infty,\infty)$ of real numbers and the set
$\\{1,2,3,\ldots\\}$ of natural numbers, respectively, by $\mathbb{R}$ and
$\mathbb{N}$. The set $\\{1,2,3,\ldots,N\\}$ where $N$$\in$$\mathbb{N}$ is
denoted by $[N]$. The size of a set $S$ is denoted by $\lvert S\rvert$.
Finally, the expectation and the covariance of a $k$-dimensional random vector
$X\in\mathbb{R}^{k}$ are denoted by $\mathbb{E}[X]$ and $\mathrm{Var}(X)$,
respectively.

##  II System Model

In this section, we define some contextual details required to formalize the
notion of distributed beamforming. In particular, we state our assumptions
regarding the communication channel between the agents and the client, and
introduce the distributed model through which the agents transmit signals.

###  II-A Communication Channel

We consider a group of $N$ agents each of which is equipped with a single
ideal isotropic antenna with a constant transmit power $P$. The agents aim to
transmit a common message $m(t)$$\in$$\mathbb{R}$, a continuous time signal,
to a stationary client. The content of the message could represent raw
measurements or a waveform encoding digital data. The assumptions regarding
the communication channels of the agents are listed as follows.

  1. 1.

The transmitted message $m(t)$ propagates in free space with no reflection or
scattering, i.e., no multipath fading or shadowing, and the incident wave can
be assumed to be a plane wave.

  2. 2.

The client is located at the far-field region. Formally, for an agent
$i$$\in$$[N]$, let $\rho_{i,c}$ be the Euclidean distance between the agent
$i$ and the client. We assume that

$\displaystyle\min_{i\in[N]}\rho_{i,c}\geq 2\lambda_{c}$

where $\lambda_{c}$ is the carrier wavelength.

  3. 3.

The distance between the agents are long enough that the mutual coupling among
their antennae are negligible.

  4. 4.

The agents communicate with the client over a narrow-band wireless channel at
some carrier frequency $f_{c}$. Therefore, each agent $i$$\in$$[N]$ has a
flat-fading channel to the client, which can be represented by a complex
scalar gain $h_{i}$$:=$$a_{i}e^{j\eta_{i}}$ where $a_{i}$ is the known channel
gain, and $\eta_{i}$ is the known phase response of the channel.

  5. 5.

The channel gains satisfy $a_{i}$$=$$a_{j}$ for all $i,j\in[N]$.

  6. 6.

Each agent has a local oscillator synchronized to the same carrier frequency
$f_{c}$. Furthermore, all local oscillators are time-synchronized.

The first three assumptions as well as the last two are typical in the study
of phased arrays [7, 5]. From a practical point of view, it has been shown
that, when the agents operate in low very high frequency (VHF) band, e.g.,
around $40$ Mega-hertz (MHZ), the communication channel has improved
penetration, long-range propagation, and significantly reduced multi-path [9].
As for the fourth assumption, for an agent with known relative position with
respect to the client, one can characterize the frequency response of a
channel up to a certain accuracy above which improvements will have a
negligible effect on the output. The synchronization problem in distributed
beamforming is a well studied subject [3]. In this work, we abstract away the
synchronization problem by our last assumption and focus solely on the effects
of localization error on beamforming.

###  II-B Distributed Transmission Model

Due to the power constraints of the antennas carried by the agents, a subset
$\mathcal{S}$$\subseteq$$[N]$ of agents collectively form a virtual array to
transmit the message signal $m(t)$ to the stationary client. Specifically,
each agent $i$$\in$$\mathcal{S}$ transmits the signal
$s_{i}(t)$$:=$$\sqrt{P}e^{j\delta_{i}}m(t)$ where $\sqrt{P}$ is the amplitude
of the transmission, and $\delta_{i}$ is a phase adjustment performed by the
agent. Then, the signal received by the client is

$\displaystyle r(t|\mathcal{S})$
$\displaystyle:=\sum_{i\in\mathcal{S}}h_{i}s_{i}(t)e^{j\zeta_{i}}+n(t)$ (1)
$\displaystyle=\sqrt{P}\sum_{i\in\mathcal{S}}a_{i}e^{j(\delta_{i}+\zeta_{i}+\eta_{i})}m(t)+n(t)$
(2)

where $n(t)$ is additive Gaussian noise with zero mean, and $\zeta_{i}$ is the
relative phase offset resulting from the relative positions of the agents and
the client. In particular, under the assumption that the local oscillators are
time-synchronized, the phase offset $\zeta_{i}$ of the signal $s_{i}$ at the
location of the client relative to a signal transmitted by an agent located at
$\vec{r}_{i}$$\in$$\mathbb{R}^{3}$ is

$\displaystyle\zeta_{i}:=-\frac{2\pi}{\lambda_{c}}\Big{\langle}\vec{r}_{i},\frac{\vec{r}_{c}}{\left\lVert\vec{r}_{c}\right\rVert}\Big{\rangle}\mod
2\pi$ (3)

where $\vec{r}_{c}$$\in$$\mathbb{R}^{3}$ is the client’s known position,
$\lambda_{c}$ is the wavelength, $\langle\cdot,\cdot\rangle$ denotes the inner
product of two vectors, $\left\lVert\cdot\right\rVert$ denotes the Euclidean
norm of a vector, and $\mod$ is the standard modulo operation.

In this paper, we assume that, the agents’ local positions
$\\{\vec{r}_{i}$$\in$$\mathbb{R}^{3}:i\in[N]\\}$ are not exactly known. In
particular, for a given $i$$\in$$[N]$, we assume that
$\vec{r}_{i}$$\sim$$\mathcal{N}({\boldsymbol{\mu}}_{i},\Sigma_{i})$ where
${\boldsymbol{\mu}_{i}}$$\in$$\mathbb{R}^{3}$ and
$\Sigma_{i}$$\in$$\mathbb{R}^{3\times 3}$ are, respectively, the known mean
and the known covariance of the Gaussian distribution. This assumption is
reasonable in practice because the first and second-order statistics of pose
within an unknown environment are easy to obtain through, e.g., LIDAR scans.
Moreover, we assume that $\vec{r}_{i}$ and $\vec{r}_{j}$ are independent for
$i,j$$\in$$[N]$ such that $i$$\neq$$j$.

In the setting described above, we investigate the effects of the agents’
localization errors on the quality of the beam formed by the agents and
develop algorithms for choosing a subset of agents that collectively forms a
beam with an acceptable quality of service despite the agents’ localization
errors. To that end, a few definitions are required. Specifically, for a given
subset $\mathcal{S}$$\subseteq$$[N]$ and phase adjustment parameters
$\delta_{i}$ for all $i$$\in$$[N]$, the array factor is defined as

$\displaystyle
F(\mathcal{S},\delta):=\sum_{i\in\mathcal{S}}e^{j(\delta_{i}+\zeta_{i}+\eta_{i})}$
(4)

where $\delta$$=$$[\delta_{i}|i$$\in$$\mathcal{S}]$ is the vector of phase
adjustments. Under the assumption that the agents’ channel gains satisfy
$a_{i}$$=$$a_{j}$ for all $i,j$$\in$$[N]$, the magnitude of the array factor
is proportional to the square root of the received signal-to-noise-ratio (SNR)
by the client [5]. Let the total phase be

$\displaystyle\Phi_{i}:=\delta_{i}+\zeta_{i}+\eta_{i}.$ (5)

Taking the square of the magnitude of the array factor, we obtain the
beamforming gain $G(\mathcal{S},\delta)$ which is proportional to the received
SNR and given by

$\displaystyle
G(\mathcal{S},\delta):=\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S}}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}.$
(6)

The beamforming gain (6) is a fundamental quantifier of the quality of a
communications link, which we seek to optimize as a function of the agents
that transmit the message signal.

##  III Problem Statement

A canonical quantifier of performance in communication systems is the signal-
to-noise-ratio (SNR) of the signal received by the client, which measures the
quality of the communication link from a virtual antenna array. As previously
mentioned, SNR is proportional to the beamforming gain (6). Thus, when the
relative phase offset $\zeta_{i}$, resulting from the relative positions of
the agent $i$ and the client, is known, one may seek a reliable communication
link by maximizing the beamforming gain, i.e., selecting a pair
$(\mathcal{S}^{\star},\delta^{\star})$ such that

$\displaystyle(\mathcal{S}^{\star},\delta^{\star})\in\operatornamewithlimits{argmax}_{\begin{subarray}{c}\mathcal{S}\subseteq[N],\\\
\delta\in[0,2\pi)^{N}\end{subarray}}G(\mathcal{S},\delta).$ (7)

The beamforming gain can be maximized by choosing
$\mathcal{S}^{\star}$$=$$[N]$ and setting
$\delta_{i}^{\star}$$=$$-(\zeta_{i}+\eta_{i}),$ for all $i$$\in$$\mathcal{S}$.
To see this, recall that the total phase
$\Phi_{i}$$=$$\delta_{i}+\zeta_{i}+\eta_{i}$, and note that

$\displaystyle
G(\mathcal{S},\delta)=\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S}}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}\leq
N^{2}.$ (8)

The upper bound in (8) is attained if and only if $\mathcal{S}$$=$$[N]$ and
$\Phi_{i}$$=$$\Phi_{j}$ for all $i,j$$\in$$\mathcal{S}$, i.e., the total
phases of all agents are aligned. In other words, for a fully known system,
the set of all agents achieves the highest SNR since all the phases of the
agents can be precisely set such that the message signals from all agents
interfere constructively at the location of the client.

In this paper, we focus on a scenario where the exact value of the relative
phase offsets $\zeta_{i}$ are not known to the system designer due to the
agents’ localization errors. This situation arises, e.g., in complex urban
terrains or GPS-denied environments. Consequently, in the considered model,
the beamforming gain $G(\mathcal{S},\delta)$ is a random variable. We are
interested in finding a subset of agents that, with high probability, forms a
reliable communication link with the client through beamforming. The formal
problem statement is as follows.

Problem 1: (Subset selection) For a constant $\Gamma$$\in$$\mathbb{R}$, and
the fixed phase adjustment parameters $\delta$$=$$\widetilde{\delta}$ where,
for all $i$$\in$$[N]$,
$\widetilde{\delta}_{i}$$:=$$-\Big{(}\mathbb{E}[\zeta_{i}]+\eta_{i}\Big{)}$,
find a subset $\mathcal{S}^{\star}$ such that

$\displaystyle\mathcal{S}^{\star}\in\ $
$\displaystyle\operatornamewithlimits{argmin}_{\mathcal{S}\subseteq[N]}\quad\
\ \mathrm{Var}\Big{(}G(\mathcal{S},\widetilde{\delta})\Big{)}$ (9a)
$\displaystyle\text{subject
to:}\quad\mathbb{E}\Big{[}G(\mathcal{S},\widetilde{\delta})\Big{]}\geq\Gamma.$
(9b)

Note that the vector
$\delta$$=$$[\delta_{1},\delta_{2},\ldots,\delta_{|\mathcal{S}|}]$ of phase
adjustment parameters is not a design variable in the subset selection
problem. The rationale behind the choice of $\delta$ is that for any given
subset $\mathcal{S}$$\subseteq$$[N]$, it can be shown that
$\mathbb{E}[G(\mathcal{S},\delta)]$ is maximized by choosing
$\delta$$=$$\widetilde{\delta}$. Since $\delta$ is not a variable in the
considered problem, for simplicity, we define the notation

$\displaystyle\overline{G}(\mathcal{S}):=G(\mathcal{S},\widetilde{\delta}).$

Remark: One can argue that, when $G(\mathcal{S},\delta)$ is a random variable,
a reasonable objective for the designer may be to maximize the expected
beamforming gain, i.e., selecting a pair
$(\overline{\mathcal{S}},\overline{\delta})$ such that

$\displaystyle(\overline{\mathcal{S}},\overline{\delta})\in\operatornamewithlimits{argmax}_{\begin{subarray}{c}\mathcal{S}\subseteq[N],\\\
\delta\in[0,2\pi)^{N}\end{subarray}}\mathbb{E}\Big{[}G(\mathcal{S},\delta)\Big{]}.$
(10)

It can be shown that $\mathbb{E}[G(\mathcal{S},\delta)]$ is maximized by
choosing $\overline{\mathcal{S}}$$=$$[N]$ and
$\overline{\delta}$$=$$\widetilde{\delta}$. In other words, the expected
beamforming gain is maximized by including all the agents to the beamforming
and aligning their total phases $\Phi_{i}$ in expectation.

Although including all the agents to the beamforming, i.e., choosing
$\overline{\mathcal{S}}$$=$$[N]$, maximizes the expected beamforming gain, it
may decrease the probability that the beamforming gain exceeds a certain
threshold, which in turn reduces the reliability of the link. In the subset
selection problem, considering the variance of the beamforming gain as a risk
measure, we aim to find a subset of agents that achieves a desired level of
gain while increasing the reliability of the link. Such a formulation is
widely used in risk-sensitive optimization models that arise in econometrics
[10, 11].

##  IV Statistical Properties of Beamforming Gains

To solve the subset selection problem, we first derive the explicit forms of
the expected value $\mathbb{E}[\overline{G}(\mathcal{S})]$ and the variance
$\mathrm{Var}(\overline{G}(\mathcal{S}))$ of the beamforming gain
$\overline{G}(\mathcal{S})$. We do so by deriving the probability distribution
of the total phase offset $\Phi_{i}$ which is defined in (5).

Recall that in the subset selection problem, we fix the phase adjustment
parameters $\delta_{i}$ by setting
$\delta_{i}$$=$$-(\mathbb{E}[\zeta_{i}]+\eta_{i})$. Therefore, we have
$\Phi_{i}$$=$$\zeta_{i}$$-$$\mathbb{E}[\zeta_{i}]$, which implies that the
distribution of $\Phi_{i}$ is just a shifted version of the distribution of
$\zeta_{i}$. Recall also that
$\zeta_{i}$$=$$(\overline{\zeta}_{i}$$\mod$$2\pi)$ where
$\overline{\zeta}_{i}$$:=$$-\frac{2\pi}{\lambda_{c}}\
\Big{\langle}\vec{r}_{i},\frac{\vec{r}_{c}}{\left\lVert\vec{r}_{c}\right\rVert}\Big{\rangle}$
and that the $i$th agent’s local position $\vec{r}_{i}$ has the Gaussian
distribution $\mathcal{N}(\boldsymbol{\mu}_{i},\Sigma_{i})$, where the phase
offset $\zeta_{i}$ is defined in (3). Then, using simple algebraic
manipulations, it can be shown that
$\overline{\zeta}_{i}$$\sim$$\mathcal{N}(\varrho_{i},\gamma_{i})$ where

$\displaystyle\varrho_{i}:=-\frac{2\pi}{\lambda_{c}}\Big{\langle}{\boldsymbol{\mu}_{i}},\frac{\vec{r}_{c}}{\left\lVert\vec{r}_{c}\right\rVert}\Big{\rangle},\
\text{and}\
\gamma_{i}:=\frac{4\pi^{2}}{\left\lVert\vec{r}_{c}\right\rVert^{2}\lambda_{c}^{2}}\Big{\langle}\vec{r}_{c},\Sigma_{i}\vec{r}_{c}\Big{\rangle}.$
(11)

We refer to $\gamma_{i}$ as the effective error in the localization of the
$i$th agent. We now need to map the probability density function (pdf) of
$\overline{\zeta}_{i}$ to the interval $[0,2\pi)$. To perform the mapping, we
use the so-called wrapped distributions[12, 13].

###### Definition 1

[12] For a given random variable $X$ on $\mathbb{R}$ with the pdf $f(x)$, let
$Y$$:=$$(X$$\mod$$2\pi)$ be the induced wrapped variable of period $2\pi$. The
wrapped pdf $g(y)$ of the variable $Y$ is given by

$\displaystyle g(y)=\sum_{m=-\infty}^{\infty}f(y+2m\pi)\ \ 0\leq y<2\pi.$

Applying the above definition to $\overline{\zeta}_{i}$ and using the fact
that $\Phi_{i}$$=$$\zeta_{i}$$-$$\mathbb{E}[\zeta_{i}]$, we obtain the wrapped
normal distribution $f_{\Phi_{i}}(y)$ of $\Phi_{i}$ as

$\displaystyle
f_{\Phi_{i}(t)}(y)=\frac{1}{\sqrt{2\pi\gamma_{i}}}\sum_{m=-\infty}^{\infty}\exp\Bigg{[}\frac{-(y+2m\pi)^{2}}{2\gamma_{i}}\Bigg{]}$
(12)

for all $0\leq y<2\pi$.

We now state a remarkable property of wrapped distributions, which allows us
to derive the explicit forms of the expected value and the variance of the
beamforming gain.

###### Proposition 1

[12] Let $X$ be a random variable on $\mathbb{R}$, and
$Y$$:=$$(X$$\mod$$2\pi)$ be the induced wrapped variable of period $2\pi$. For
any $p$$\in$$\mathbb{N}$, we have

$\displaystyle\mathbb{E}[e^{j(pX)}]=\mathbb{E}[e^{j(pY)}].$ (13)

Proposition 1 states that the wrapped distribution has identical moments to
the unwrapped distribution, which permits us to derive explicit forms of
$\mathbb{E}[\overline{G}(\mathcal{S})]$ and
$\mathrm{Var}(\overline{G}(\mathcal{S}))$, as stated in the following lemma.

###### Lemma 1

Let $v_{i}$$:=$$\exp(-\gamma_{i})$. The expected value and the variance of the
beamforming gain $\overline{G}(\mathcal{S})$ are, respectively,

$\displaystyle\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}=$
$\displaystyle\big{\lvert}\mathcal{S}\big{\rvert}+\sum_{i\in\mathcal{S}}\sum_{\begin{subarray}{c}j\in\mathcal{S}\\\
j\neq i\end{subarray}}\sqrt{v_{i}v_{j}},$ (14)
$\displaystyle\mathrm{Var}\Big{(}\overline{G}(\mathcal{S})\Big{)}=$
$\displaystyle\sum_{i\in\mathcal{S}}\sum_{\begin{subarray}{c}j\in\mathcal{S}\\\
j\neq i\end{subarray}}\Big{(}1-v_{i}v_{j}\Big{)}^{2}$
$\displaystyle+2\sum_{i\in\mathcal{S}}\sum_{\begin{subarray}{c}j\in\mathcal{S}\\\
j\neq i\end{subarray}}\sum_{\begin{subarray}{c}k\in\mathcal{S}\\\ k\neq i\\\
k\neq j\end{subarray}}\Big{(}1-v_{i}\Big{)}^{2}\sqrt{v_{j}v_{k}}.$ (15)

Proof for the above result, as well as proofs for all the results presented in
this paper, can be found in Appendix. These properties of the mean and
variance of the beamforming gain, built upon properties of wrapped
distributions, motivate the algorithm development in the next section. In
particular, through their explicit forms, we derive conditions on the
localization error for which monotonicity and supermodularity properties may
be established.

##  V Agent Selection under Localization Errors

In this section, we propose three algorithms to solve the subset selection
problem and discuss their optimality. The key point is that when localization
errors are below a certain threshold, we are able to establish that a greedy
subset selection scheme attains optimal performance directly. Then, for the
case that the localization errors exceeds the aforementioned threshold, we
provide a counterexample that demonstrates that the greedy algorithm may yield
suboptimal solution. Inspired by the numerical examples generated by the
”greedy” approach, we propose a modified “double” greedy scheme with the same
optimality guarantees as our “greedy” scheme and better performance at the
cost of higher computation. For the case that these sufficient optimality
conditions break down, we derive monotonicity and supermodularity properties
of the expressions in (9a)-(9b). By taking advantage of these conditions, we
propose an algorithm that exploits their structure based on the difference of
submodular functions and discuss its local optimality.

For the rest of the paper, we assume that the optimization problem in
(9a)-(9b) has a feasible solution. For a given problem instance, the validity
of such an assumption can be easily verified by checking whether
$\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$ for
$\mathcal{S}$$=$$[N]$ due to the following result.

###### Proposition 2

For any $\mathcal{S},\mathcal{S}^{\prime}$$\subseteq$$[N]$ such that
$\mathcal{S}$$\subseteq$$\mathcal{S}^{\prime}$, we have

$\displaystyle\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}\leq\mathbb{E}\Big{[}\overline{G}(\mathcal{S}^{\prime})\Big{]}.$
(16)

The above result follows immediately from the monotonicity of
$\mathbb{E}[\overline{G}(\mathcal{S})]$. Specifically, since
$\mathbb{E}[\overline{G}(\mathcal{S})]$, given in (14), is a sum of
nonnegative terms, adding an element to the subset can only increase the sum.

###  V-A Greedy Algorithm for Small Localization Errors

The first algorithm, shown in Algorithm 1, that we propose to solve the subset
selection problem (9a)-(9b) is based on a simple greedy approach. The Greedy
algorithm first sorts the agents’ effective errors $\gamma_{i}$ in ascending
order. Initializing the output set $\mathcal{S}$ to the empty set, it then
iteratively adds the agent with the next lowest effective error to the output
set until the constraint $\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$
is satisfied. This procedure is summarized in Algorithm 1.

Algorithm 1 Greedy

1:Input: $\gamma_{i}$ for all $i$$\in$$[N]$, $\Gamma$$\in$$\mathbb{R}$.

2:Sort $\gamma_{i}$ such that
$\gamma_{i_{1}}$$\leq$$\gamma_{i_{2}}$$\leq$$\ldots$$\leq$$\gamma_{i_{N}}$.

3:$\mathcal{S}$$:=$$\emptyset$, $k$$:=$$1$

4:while $\mathbb{E}[\overline{G}(\mathcal{S})]$$<$$\Gamma$ do

5: $\mathcal{S}$$:=$$\mathcal{S}\cup\\{i_{k}\\}$, $k$$:=$$k+1$

6:return $\mathcal{S}$.

The time complexity of the Greedy algorithm is the same (up to a certain
constant) with the time complexity of the sorting algorithm used as a
subprocedure. The sorting of an array of length $N$ can be performed
efficiently by a variety of algorithms including merge sort [14] and quick
sort [15].

Optimality of the Greedy algorithm We now present sufficient conditions on the
set $\\{\gamma_{i}:i$$\in$$[N]\\}$ of effective localization errors under
which the Greedy algorithm returns an optimal solution to the problem in
(9a)-(9b).

Recall from (12) that the effective localization error $\gamma_{i}$ is the
variance of the total phase $\Phi_{i}$. Hence, it can be seen as a
representative of the uncertainty in the total phase $\Phi_{i}$. In
particular, in two extremes, when $\gamma_{i}$$=$$0$, $\Phi_{i}$$=$$0$ with
probability 1, and when $\gamma_{i}$$=$$\infty$, $\Phi_{i}$ is uniformly
distributed over the interval $[0,2\pi)$. We measure the total effective error
of a subset $\mathcal{S}$$\subseteq$$[N]$ by the function
$V$$:$$2^{[N]}$$\rightarrow$$\mathbb{R}$ such that

$\displaystyle V(\mathcal{S}):=\sum_{i\in\mathcal{S}}\gamma_{i}.$ (17)

One can intuitively think that a solution to the subset selection problem can
be obtained by choosing a subset $\mathcal{S}^{\prime}$ of agents that satisfy
the constraint (9b) and have the minimum total effective error (17), i.e.,

$\displaystyle\mathcal{S}^{\prime}\in\ $
$\displaystyle\arg\min_{\mathcal{S}\subseteq[N]}\quad\ V(\mathcal{S})$ (18a)
$\displaystyle\text{subject to:}\quad\
\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}\geq\Gamma.$ (18b)

The following result, together with Proposition 2, implies that Algorithm 1
returns a globally optimal solution to the problem in (18a)-(18b).

###### Proposition 3

For any $K$$\in$$\mathbb{N}$ such that $K$$\leq$$N$, we have

$\displaystyle\arg\min_{\begin{subarray}{c}\mathcal{S}\subseteq[N]:\\\
\lvert\mathcal{S}\rvert=K\end{subarray}}V(\mathcal{S})=\arg\max_{\begin{subarray}{c}\mathcal{S}\subseteq[N]:\\\
\lvert\mathcal{S}\rvert=K\end{subarray}}\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}.$

Unfortunately, the optimization problems in (9a)-(9b) and (18a)-(18b) are not
equivalent in general. However, there are certain sufficient conditions under
which these problems become equivalent, which are formalized in the following
theorem.

###### Theorem 1

For a given set $\\{\gamma_{i}:i$$\in$$[N]\\}$ of effective localization
errors, let
$\gamma_{i_{1}}$$\leq$$\gamma_{i_{2}}$$\leq$$...$$\leq$$\gamma_{i_{N}}$ where
$i_{k}$$\in$$[N]$ for all $k$$\in$$[N]$. A solution to the problem in
(18a)-(18b) is also a solution to the problem in (9a)-(9b) if either one of
the following conditions hold:

  * •

$\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$ where
$\mathcal{S}$$=$$\\{i_{1},i_{2}\\}$,

  * •

$\gamma_{i_{N}}(t)$$\leq$$0.83$.

Proof for the above result is provided in Appendix. Theorem 1 establishes that
if the two agents with the lowest effective localization errors exceed the
desired expected beamforming gain threshold $\Gamma$, or if all the agents
have “small” effective localization errors, i.e., $\gamma_{i}$$\leq$$0.83$ for
all $i$$\in$$[N]$, then the Greedy algorithm returns an optimal solution to
the original subset selection problem (9a)-(9b).

We emphasize that the Greedy algorithm returns an optimal solution to the
subset selection problem if a given problem instance satisfies either one of
the sufficient conditions in Theorem 1. The following numerical example
illustrates that for problem instances that violates the sufficient
conditions, the Greedy algorithm may result in a suboptimal subset selection.

###### Example 1

We construct a problem instance for which the optimization problems in
(9a)-(9b) and (18a)-(18b) are not equivalent. Let the total number of agents
be $N$$=$$4$, and the expected gain threshold be $\Gamma$$=$$3.3$.
Furthermore, let the ordered set
$(\gamma_{1},\gamma_{2},\gamma_{3},\gamma_{4})$ of effective errors be
$(0.4,0.6,3,5)$. It is clear that the problem instance does not satisfy the
second sufficient condition in Theorem 1. Moreover, by direct calculation, one
can observe that $\mathbb{E}[\overline{G}(\mathcal{S})]$$=$$3.2131$ for
$\mathcal{S}$$=$$\\{1,2\\}$. Hence, the instance does not satisfy the first
sufficient condition in Theorem 1 as well. Using Proposition 3, one can
conclude that, for this problem instance, at least three agents should be
included in the beamforming. Let $\mathcal{S}_{1}$$:=$$\\{1,2,3\\}$,
$\mathcal{S}_{2}$$:=$$\\{1,2,4\\}$, $\mathcal{S}_{3}$$:=$$\\{1,3,4\\}$, and
$\mathcal{S}_{4}$$:=$$\\{2,3,4\\}$ be all possible subsets of $\\{1,2,3,4\\}$
containing three elements. In Fig. 1, we provide the expected value and the
variance of the beamforming gain $\overline{G}(\mathcal{S}_{k})$ as well as
the total effective error $V(\mathcal{S}_{k})$ for each $\mathcal{S}_{k}$. All
subsets $\mathcal{S}_{k}$ satisfy
$\mathbb{E}[\overline{G}(\mathcal{S}_{k})]$$\geq$$\Gamma$. Observe that the
optimal solution for this problem instance is the subset $\mathcal{S}_{4}$
which has the maximum total effective error $V(\mathcal{S}_{4})$ instead of
the minimum one $V(\mathcal{S}_{1})$. Therefore, for this instance, the Greedy
algorithm does not yield the optimal solution to the subset selection problem.

Figure 1: Expected value and the variance of the beamforming gain
$\overline{G}(\mathcal{S}_{k})$ as a function of subsets
$\mathcal{S}_{k}$$\subseteq$$[4]$ satisfying
$\lvert\mathcal{S}_{k}\rvert$$=$$3$. The maximum expected value is attained by
the subset $\mathcal{S}_{1}$ which has the minimum total effective error
$V(\mathcal{S}_{1})$. The variance of the beamforming gain is minimized by the
subset $\mathcal{S}_{4}$ which has the maximum total effective error
$V(\mathcal{S}_{4})$.

The above numerical example illustrates a counterintuitive fact: for some
problem instances, the optimal subset consists of the agents with the highest
effective localization errors. This phenomenon arises due to the physical
interaction effects of constructive/destructive interference of the sinusoids
in (6). Next, we develop a modified algorithm that accounts for the fact that
for some instances the agents with the highest effective localization errors
provides an optimal solution to the subset selection problem.

###  V-B Double-Loop-Greedy for Improved Empirical Performance

Inspired by the numerical example given in the previous section, as the second
approach, we propose the Double-Loop-Greedy (DLP) algorithm, shown in
Algorithm 2, to solve the subset selection problem. Similar to the Greedy
algorithm, the DLG algorithm first sorts the agents’ effective errors
$\gamma_{i}$ in ascending order. It then initializes two sets, namely,
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$, to the empty set. Starting from the
agent with the lowest effective error, at each iteration, the agent with the
next lowest effective error is iteratively added to the set $\mathcal{S}_{1}$
until the constraint $\mathbb{E}[\overline{G}(\mathcal{S}_{1})]$$>$$\Gamma$ is
satisfied. Note that $\mathcal{S}_{1}$ is the same with the output of the
Greedy algorithm. Similarly, starting from the agent with the highest
effective error, at each iteration, the agent with the next highest effective
error is iteratively added to the set $\mathcal{S}_{2}$ until the constraint
$\mathbb{E}[\overline{G}(\mathcal{S}_{2})]$$>$$\Gamma$ is satisfied. Finally,
the DLG algorithm compares the variance of the beamforming gain for the sets
$\mathcal{S}_{1}$ and $\mathcal{S}_{2}$, and outputs the one with smaller
value.

Algorithm 2 Double-Loop-Greedy (DLG)

1:Input: $\gamma_{i}$ for all $i$$\in$$[N]$, $\Gamma$$\in$$\mathbb{R}$.

2:Sort $\gamma_{i}$ such that
$\gamma_{i_{1}}$$\leq$$\gamma_{i_{2}}$$\leq$$\ldots$$\leq$$\gamma_{i_{N}}$.

3:$\mathcal{S}_{1}$$:=$$\emptyset$, $\mathcal{S}_{2}$$:=$$\emptyset$,
$k$$:=$$1$, $l$$:=$$N$

4:while $\mathbb{E}[\overline{G}(\mathcal{S}_{1})]$$<$$\Gamma$ do

5: $\mathcal{S}_{1}$$:=$$\mathcal{S}_{1}\cup\\{i_{k}\\}$, $k$$:=$$k+1$

6:while $\mathbb{E}[\overline{G}(\mathcal{S}_{2})]$$<$$\Gamma$ do

7: $\mathcal{S}_{2}$$:=$$\mathcal{S}_{2}\cup\\{i_{l}\\}$, $l$$:=$$l-1$

8:if
$\mathrm{Var}(\overline{G}(\mathcal{S}_{1}))$$<$$\mathrm{Var}(\overline{G}(\mathcal{S}_{2}))$
then $\mathcal{S}:=\mathcal{S}_{1}$

9:else$\ \mathcal{S}:=\mathcal{S}_{2}$

10:return $\mathcal{S}$.

We note that the time complexity of the DLG algorithm is the same (up to a
certain constant) as the time complexity of the Greedy algorithm.

Optimality of the DLG algorithm For a given problem instance, the subset
$\mathcal{S}$$\subseteq$$[N]$ returned by the DLG algorithm is guaranteed to
satisfy
$\mathrm{Var}(\overline{G}(\mathcal{S}))$$\leq$$\mathrm{Var}(\overline{G}(\mathcal{S}^{\prime}))$
where $\mathcal{S}^{\prime}$$\subseteq$$[N]$ is the subset returned by the
Greedy algorithm. Hence, the DLG algorithm also provides a globally optimal
solution to the problem in (18a)-(18b) under the sufficient conditions stated
in Theorem 1. Moreover, as can be seen from the numerical example given in the
previous section, the DLG algorithm may also return a globally optimal
solution to problem instances on which the Greedy algorithm performs poorly.

###  V-C Difference-of-Submodular (DS) algorithm

Both the Greedy (Algorithm 1) and DLG (Algorithm 2) are guaranteed to return
globally optimal solutions to the subset selection problem only under the
sufficient conditions stated in Theorem 1. In this section, we propose a third
approach to solve the subset selection problem, which utilizes the functional
properties of the expected value and the variance of the beamforming gain, and
always returns a locally optimal solution to a certain relaxation of the
subset selection problem.

Before presenting the Difference-of-Submodular (DS) algorithm, we first
provide a definition of submodularity and show that both the expected value
and the variance of the beamforming gain are supermodular set functions.

###### Definition 2

A set function $f$$:$$2^{\Omega}$$\rightarrow$$\mathbb{R}$ is submodular if
for every $X,Y$$\subseteq$$\Omega$ with $X$$\subseteq$$Y$ and every
$e$$\in$$\Omega\backslash Y$, we have $f(X$$\cup$$\\{e\\})-f(X)\geq
f(Y\cup\\{e\\})-f(Y)$.

A set function $f$$:$$2^{\Omega}$$\rightarrow$$\mathbb{R}$ is said to be
supermodular if the set function $-f$ is submodular. Next, we formalize that
the objective and constraints in (9a) - (9a) satisfy the definition of
supermodularity.

###### Theorem 2

Both the expected value, $\mathbb{E}[\overline{G}(\mathcal{S})]$, and the
variance, $\mathrm{Var}(\overline{G}(\mathcal{S}))$, of the beamforming gain
$G(\mathcal{S})$ are supermodular set functions.

Proof of Theorem 2 can be found in Appendix. Let
$f$$:$$2^{\Omega}$$\rightarrow$$\mathbb{R}$ and
$g$$:$$2^{\Omega}$$\rightarrow$$\mathbb{R}$ be submodular set functions. In
[8], the authors present an algorithm, called Submodular-Supermodular-
Procedure (SSP), that returns a local optimal solution to the following
problem

$\displaystyle\min_{S\subseteq\Omega}\quad\ f(S)-g(S).$ (19)

To be precise in our statements, we also provide a definition of local
optimality for set functions.

###### Definition 3

[8] For a set function $\phi$$:$$2^{\Omega}$$\rightarrow$$\mathbb{R}$, a
sequence $\\{S_{t}\subseteq\Omega:t\in\mathbb{N}\\}$ is said to converge to a
local minimum if there exists a constant $M$$\in$$\mathbb{N}$ such that
$\phi(S_{m})$$=$$\phi(S_{n})$ for all $m,n$$\geq$$M$, and for any
$k$$\in$$\mathbb{N}$, $\phi(S_{k})$$\leq$$\phi(S_{l})$ for all $l$$\leq$$k$.

The DS algorithm, shown in Algorithm 3, utilizes the SSP as a subprocedure to
return a locally optimal solution to a certain relaxation of the subset
selection problem. In particular, it takes two parameters $\lambda_{0}$$>$$0$
and $\alpha$$>$$1$ as inputs as well as the agents’ effective localization
errors $\gamma_{i}$ and the expected gain threshold $\Gamma$. At the $k$th
iteration, where $k$$\in$$\mathbb{N}$, using the SSP as a subprocedure, the DS
algorithm finds a locally optimal solution to the following problem

$\displaystyle\min_{\mathcal{S}\subseteq[N]}\quad\
\mathrm{Var}\Big{(}\overline{G}(\mathcal{S})\Big{)}-\lambda_{k}\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}$
(20)

where $\lambda_{k}$ is iteratively defined as
$\lambda_{k}$$=$$\alpha\lambda_{k-1}$. The algorithm terminates when the
solution returned by the SSP satisfies
$\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$.

Algorithm 3 Difference-of-Submodular (DS)

1:Input: $\gamma_{i}$ for all $i$$\in$$[N]$, $\Gamma$$\in$$\mathbb{R}$,
$\lambda_{0}$$>$$0$, $\alpha$$>$$1$.

2:$\mathcal{S}$$:=$$\emptyset$, $k$$:=$$0$.

3:while $\mathbb{E}[\overline{G}(\mathcal{S})]$$<$$\Gamma$ do

4: $f(\cdot)$$:=$$-\lambda_{k}\mathbb{E}[\overline{G}(\cdot)]$,
$g(\cdot)$$:=$$-\mathrm{Var}(\overline{G}(\cdot))$

5: $\mathcal{S}$$:=$$\text{SSP}(f(\cdot),g(\cdot))$

6: $k$$:=$$k+1$, $\lambda_{k}$$:=$$\alpha\lambda_{k-1}$.

7:return $\mathcal{S}$.

Convergence of the DS algorithm For the DS algorithm to terminate, SSP outputs
a subset $\mathcal{S}$$\subseteq$$[N]$ such that
$\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$. At the $k$th iteration,
the SSP finds a locally optimal solution to the problem in (20) by computing
successive modular approximations of the function
$\mathrm{Var}(\overline{G}(\mathcal{S}))$ and finding a globally optimal
solution to each of the resulting approximation problems. Since
$\lambda_{0}$$>$$0$ and $\alpha$$>$$1$, the parameter $\lambda_{k}$ increases
at each iteration. Hence, in terms of the objective value, the globally
optimal solution of the approximate problems become closer to the globally
optimal solution of $\max_{\mathcal{S}}\mathbb{E}[\overline{G}(\mathcal{S})]$
which is $\mathcal{S}$$=$$[N]$. Since we assumed at the beginning that there
exists a feasible solution to the subset selection problem, the DS algorithm
is guaranteed to terminate for some finite $k$$\in$$[N]$.

Optimality of the DS algorithm As mentioned earlier, at each iteration, the DS
algorithm computes a locally optimal solution to the problem in (20). Hence,
the subset returned by the DS algorithm is a locally optimal solution the
following relaxation of the subset selection problem

$\displaystyle\min_{\mathcal{S}\subseteq[N]}\quad\
\mathrm{Var}\Big{(}\overline{G}(\mathcal{S})\Big{)}-\lambda_{k^{\star}}\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}$
(21)

where $k^{\star}$ is the number of iterations until the convergence of the DS
algorithm. We also note that the above problem formulation is sometimes
referred to as “regularized version” of the original constrained optimization
problem [16]. Such regularization approaches to solve the original problems
are also quite common in portfolio management [17] and reinforcement learning
[18, 19, 20], among many others.

##  VI Numerical Simulations

In this section, we present numerical simulation results that demonstrate the
performance of the proposed algorithms on randomly generated subset selection
problem instances. The possible heterogeneity of agents and their capability
in accurate localization requires algorithms that can offer acceptable
performance for a mixture of agents in a range of localization accuracies. In
addition, the scalability of the algorithms and their performance for small to
mid-size swarms is of special interest in robotic applications. To these
points, we have provided simulation results that show the scalability and
average performance of our proposed algorithms for a variety of collections of
randomly generated agents.

For a given problem instance, we measure the performance of an algorithm by
the suboptimality ratio of its output. Specifically, let $\mathcal{S}^{\star}$
be an optimal solution to the given subset selection problem instance
(9a)-(9b), and $\overline{\mathcal{S}}$ be the output of a given algorithm. We
define the suboptimality ratio (SR) of the algorithm on the given problem
instance as

$\displaystyle\text{SR}:=\frac{\mathrm{Var}\Big{(}\overline{G}(\overline{\mathcal{S}})\Big{)}}{\mathrm{Var}\Big{(}\overline{G}(\mathcal{S}^{\star})\Big{)}}.$

Note that all the proposed algorithms, i.e., Greedy, Double Loop Greedy (DLG),
and Difference Submodular (DS), have $SR$$\geq$$1$ since they are guaranteed
to output a subset $\overline{\mathcal{S}}$ such that
$\mathbb{E}[\overline{G}(\overline{\mathcal{S}})]$$\geq$$\Gamma$.

Figure 2: Average suboptimality ratios of the proposed methods over randomly
generated 1000 problem instances. (Top) The suboptimality ratios of the
Greedy, double loop greedy (DLG), and Difference Submodular (DS) algorithms
for varying total number of agents $(N)$ and maximum localization errors
($\gamma_{\max}$). (Bottom) A closer look on the average suboptimality ratios
of the greedy algorithms.

We compare the performance of the Greedy, DLG, and DS algorithms with respect
to three parameters: the total number of agents $N$, the maximum localization
error $\gamma_{\max}$$:=$$\min\\{\gamma:\gamma$$\geq$$\gamma_{i},\text{for
all}\ i$$\in$$[N]\\}$, and the expected beamforming gain threshold
$\Gamma$$=$$\beta\Gamma_{\max}$ where $0$$<$$\beta$$\leq$$1$. Recall that, for
a given problem instance, $\Gamma_{\max}$ is defined as the maximum expected
beamforming gain that can be achieved by the agents.

In the first experiment, we investigate the relationship between the
algorithms’ average suboptimality ratios, the total number of agents $N$, and
the bound $\gamma_{\max}$ on the agents’ localization errors. For a given $N$
and $\gamma_{\max}$, a problem instance consists of localization errors
$\\{\gamma_{i}$$:$ $i$ $\in$$[N]\\}$ where each $\gamma_{i}$ is uniformly
randomly generated from the interval $[0,\gamma_{\max}]$ and the expected
beamforming gain threshold $\Gamma$$=$$0.6\Gamma_{\max}$. The threshold
$\Gamma$ is set to $0.6\Gamma_{\max}$ for allowing the algorithms to output
subsets of different sizes if it is optimal to do so. For the DS algorithm, we
initialize the Lagrangian parameter with $\lambda_{0}$$=$$1$ and set the
multiplying factor to $\alpha$$=$$2$. For each $N$$\in$$\\{4,5,\ldots,10\\}$
and each $\gamma_{\max}$$\in$$\\{1,11,21,\ldots,51\\}$, we generate 1000
problem instances and illustrate the average suboptimality ratios of all
algorithms in Fig. 2.

As can be seen from the Fig. 2, on average, both the Greedy and DLG algorithms
performs better than the DS algorithm for all ($N$,$\gamma_{max}$) pairs.
Moreover, the DLG algorithm always performs better than the Greedy algorithm
as it is theoretically guaranteed to do so. Since the average suboptimality
ratios of all three algorithms are less than 2 over the randomly generated
instances, we believe that they are all good candidates to solve the subset
selection problem for practical purposes. However, considering the relative
simplicity of Greedy and DLG algorithms with respect to the DS algorithm, a
designer may find the Greedy and DLG algorithms more appealing.

In the second experiment, we investigate the relationship between the
algorithms’ worst-case suboptimality ratios, the total number of agents $N$,
and the threshold $\Gamma$$=$$\beta\Gamma_{\max}$ on the expected beamforming
gain. For given $N$ and $\beta$, a problem instance consists of localization
errors $\\{\gamma_{i}:i$$\in$$[N]\\}$ where each $\gamma_{i}$ is generated
uniformly randomly from the interval $[0,30]$ and the expected beamforming
gain threshold $\Gamma$$=$$\beta\Gamma_{\max}$. We initialize the Lagrangian
parameter with $\lambda_{0}$$=$$1$ and set $\alpha$$=$$2$ for the DS
algorithm. For each $N$$\in$$\\{4,5,\ldots,10\\}$ and each
$\beta$$\in$$\\{0.5,0.6,\ldots,1\\}$, we generate 1000 problem instances. The
maximum suboptimality ratios of the algorithms over the generated instances is
shown in Fig. 3.

Figure 3: The maximum suboptimality ratio of the proposed methods over
randomly generated 1000 problem instances. Suboptimality ratios are shown for
varying total number of agents $N$ and thresholds
$\Gamma$$=$$\beta\Gamma_{\max}$.

As can be seen from the Fig. 3 that both Greedy and DLG algorithms perform
better than the DS algorithm over all randomly generated instances. In
particular, the maximum suboptimality ratio of the greedy algorithms are
always less than 1.5 whereas the DS algorithm has large suptiomality ratios,
e.g., $SR$$>$$3$, for large total number of agents $N$ and small expected
beamforming gain thresholds $\Gamma$. Finally we note that, in general, the
suboptimality ratio of all algorithms increase with decreasing threshold
$\Gamma$.

We observe in our experiments that the optimal subset $\mathcal{S}^{\star}$
usually consists of the agents with similar localization errors instead of the
agents with small localization errors. For example, suppose that $N$$=$$5$ and
the localization errors are $\\{1,2,11,12,13\\}$. If we set $\Gamma$$=$$2.4$,
the optimal set is $\mathcal{S}^{\star}$$=$$\\{1,2\\}$. On the other hand, if
we set $\Gamma$$=$$2.5$, then the optimal set is
$\mathcal{S}^{\star}$$=$$\\{11,12,13\\}$. Unfortunately, we have no
theoretical explanations for such a counter-intuitive phenomenon due to the
complicated functional form of the variance
$\mathrm{Var}(\overline{G}(\mathcal{S}))$.

##  VII Conclusion

We have formulated a subset selection problem that aims to find a subset of
agents, each of which is equipped with an ideal isotropic antenna, that forms
a reliable communication link with a client through beamforming. We have
presented three algorithms for solving the subset selection problem, and have
discussed their computational complexity and optimality. The presented
theoretical analysis, together with the conducted numerical experiments,
suggests that simple greedy approaches provide reasonably good performance
with low computational cost, although such approaches may not be optimal
unless the given problem instance satisfies certain sufficient conditions on
the maximum localization error. On the other hand, for general problem
instances, one can obtain local optimal solutions to the formulated subset
selection problem by using an algorithm that utilizes the supermodularity of
the variance and the expected value of the beamforming gain. All the proposed
algorithms can be thought of as attempts towards approximate trade-off
analysis and attempts towards finding a desirable Pareto points.

## References

  * [1] B. D. Van Veen and K. M. Buckley, “Beamforming: A Versatile Approach to Spatial Filtering,” _IEEE ASSP Magazine_ , 1988.
  * [2] H. L. Van Trees and K. L. Bell, _Detection estimation and modulation theory_. Wiley, 2013.
  * [3] S. Jayaprakasam, S. K. A. Rahim, and C. Y. Leow, “Distributed and Collaborative Beamforming in Wireless Sensor Networks: Classifications, Trends, and Research Directions,” _IEEE Communications Surveys and Tutorials_ , 2017.
  * [4] J. Oh, J. Choi, F. T. Dagefu, and K. Sarabandi, “Extremely small two-element monopole antenna for HF band applications,” _IEEE Transactions on Antennas and Propagation_ , 2013.
  * [5] R. Mudumbai, J. Hespanha, U. Madhow, and G. Barriac, “Distributed transmit beamforming using feedback control,” _IEEE Transactions on Information Theory_ , vol. 56, no. 1, pp. 411–426, 2009.
  * [6] B. D. Steinberg, _Principles of aperture and array system design: Including random and adaptive arrays_. John Wiley & Sons, 1976.
  * [7] H. Ochiai, P. Mitran, H. V. Poor, and V. Tarokh, “Collaborative beamforming for distributed wireless ad hoc sensor networks,” _IEEE Transactions on Signal Processing_ , 2005.
  * [8] M. Narasimhan and J. Bilmes, “A submodular-supermodular procedure with applications to discriminative structure learning,” in _Conference on Uncertainty in Artificial Intelligence_ , 2005, pp. 404–412.
  * [9] F. Dagefu et al., “Short-Range Low-VHF channel characterization in cluttered environments,” _IEEE Transactions on Antennas and Propagation_ , 2015.
  * [10] H. Levy and H. M. Markowitz, “Approximating expected utility by a function of mean and variance,” _The American Economic Review_ , vol. 69, no. 3, pp. 308–317, 1979.
  * [11] H. M. Markowitz and G. P. Todd, _Mean-variance analysis in portfolio choice and capital markets_. John Wiley & Sons, 2000, vol. 66.
  * [12] S. R. Jammalamadaka and A. Sengupta, _Topics in circular statistics_. World Scientific, 2001, vol. 5.
  * [13] G. Jona-Lasinio, A. Gelfand, M. Jona-Lasinio _et al._ , “Spatial analysis of wave direction data using wrapped Gaussian processes,” _The Annals of Applied Statistics_ , vol. 6, no. 4, pp. 1478–1498, 2012.
  * [14] R. Cole, “Parallel merge sort,” _SIAM Journal on Computing_ , vol. 17, no. 4, pp. 770–785, 1988.
  * [15] C. A. Hoare, “Quicksort,” _The Computer Journal_ , vol. 5, no. 1, pp. 10–16, 1962.
  * [16] S. Boyd, S. P. Boyd, and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [17] G. Neu, A. Jonsson, and V. Gómez, “A unified view of entropy-regularized Markov decision processes,” _arXiv:1705.07798_ , 2017.
  * [18] M. C. Steinbach, “Markowitz revisited: Mean-variance models in financial portfolio analysis,” _SIAM review_ , vol. 43, no. 1, pp. 31–85, 2001.
  * [19] A. Koppel, G. Warnell, E. Stump, P. Stone, and A. Ribeiro, “Breaking Bellman’s curse of dimensionality: Efficient kernel gradient temporal difference,” _arXiv preprint arXiv:1709.04221_ , 2017.
  * [20] A. Koppel, E. Tolstaya, E. Stump, and A. Ribeiro, “Nonparametric stochastic compositional gradient descent for Q-learning in continuous Markov decision problems,” _arXiv:1804.07323_ , 2018.

In this appendix, we provide proofs for all results presented in this paper.
We first provide a simple technical lemma which allows us to prove the main
results.

###### Lemma 2

For a given set $\\{x_{i}\in\mathbb{R}:i$$\in$$[N]\\}$ of real numbers, the
following equality holds:

$\displaystyle\Bigg{(}\sum_{i=1}^{N}\sum_{j\neq i}x_{i}x_{j}\Bigg{)}^{2}=$
$\displaystyle 2\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}^{2}x_{j}^{2}+4\sum_{i=1}^{N}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}x_{i}^{2}x_{j}x_{k}$ $\displaystyle+\sum_{i=1}^{N}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}x_{i}x_{j}x_{k}x_{l}$ (22)

Proof of Lemma 2: We prove the claim by induction on $N$.

Base case: For the base case, i.e., $N=1$, all terms on both right and left
hand sides are equal to zero since the set is a singleton. Therefore, the
claim holds.

Inductive step: Assume that the claim holds for $N$. We now show that the
equality holds also for $N+1$. We have

$\displaystyle\Bigg{(}\sum_{i=1}^{N+1}\sum_{j\neq i}x_{i}x_{j}\Bigg{)}^{2}=$
$\displaystyle\Bigg{(}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}+2x_{N+1}\sum_{i=1}^{N}x_{i}\Bigg{)}^{2}$ $\displaystyle=$
$\displaystyle\Bigg{(}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}\Bigg{)}^{2}+4x^{2}_{N+1}\Bigg{(}\sum_{i=1}^{N}x_{i}\Bigg{)}^{2}$
$\displaystyle+4x_{N+1}\Bigg{(}\sum_{i=1}^{N}x_{i}\Bigg{)}\Bigg{(}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}\Bigg{)}$ $\displaystyle=$ $\displaystyle
2\sum_{i=1}^{N}\sum_{j\neq i}x_{i}^{2}x_{j}^{2}+4\sum_{i=1}^{N}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}x_{i}^{2}x_{j}x_{k}$ $\displaystyle+\sum_{i=1}^{N}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}x_{i}x_{j}x_{k}x_{l}$
$\displaystyle+4x^{2}_{N+1}\Big{(}\sum_{i=1}^{N}x_{i}\Big{)}^{2}$
$\displaystyle+4x_{N+1}\Big{(}\sum_{i=1}^{N}x_{i}\Big{)}\Big{(}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}\Big{)}$ (23)

where the first equality follows from $(a+b)^{2}=a^{2}+b^{2}+2ab$, and the
second equality follows from the induction hypothesis.

From the summation of the first and the fourth terms on the right hand side of
(23), we have

$\displaystyle 2\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}^{2}x_{j}^{2}+4x^{2}_{N+1}\Bigg{(}\sum_{i=1}^{N}x_{i}\Bigg{)}^{2}=$
$\displaystyle\definecolor{cb@saved}{rgb}{0,0,0}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}2\sum_{i=1}^{N+1}\sum_{j\neq
i}x_{i}^{2}x_{j}^{2}}$
$\displaystyle+\definecolor{cb@saved}{rgb}{0,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\boxed{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}4x^{2}_{N+1}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}}$

where the term boxed in blue is the first term in (22). Moreover, the last
term on the right hand side of (23) satisfies

$\displaystyle
4x_{N+1}\Bigg{(}\sum_{i=1}^{N}x_{i}\Bigg{)}\Bigg{(}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}\Bigg{)}=$
$\displaystyle\definecolor{cb@saved}{rgb}{0,0,0}\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\boxed{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}8x_{N+1}\sum_{i=1}^{N}x^{2}_{i}\sum_{j\neq
i}x_{j}}$ $\displaystyle+4x_{N+1}\sum_{i=1}^{N}x_{i}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq j\end{subarray}}x_{j}x_{k}.$

Summing up the second term on the right hand side of (23) with the terms
including a single $x_{i}^{2}$ (boxed in red), we obtain

$\displaystyle 4\sum_{i=1}^{N}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq
i\\\ k\neq
j\end{subarray}}x_{i}^{2}x_{j}x_{k}+4x^{2}_{N+1}\sum_{i=1}^{N}\sum_{j\neq
i}x_{i}x_{j}$ $\displaystyle+8x_{N+1}\sum_{i=1}^{N}x^{2}_{i}\sum_{j\neq
i}x_{j}=\definecolor{cb@saved}{rgb}{0,0,0}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}4\sum_{i=1}^{N+1}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}x_{i}^{2}x_{j}x_{k}}$

where the term boxed in blue is the second term in (22). Finally, since

$\displaystyle\sum_{i=1}^{N}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq i\\\
k\neq j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}x_{i}x_{j}x_{k}x_{l}+4x_{N+1}\sum_{i=1}^{N}x_{i}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq j\end{subarray}}x_{j}x_{k}$
$\displaystyle=\definecolor{cb@saved}{rgb}{0,0,0}\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\boxed{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\sum_{i=1}^{N+1}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}x_{i}x_{j}x_{k}x_{l}},$

where the term boxed in blue is the last term in (22), we conclude the result.
$\Box$

Proof of Lemma 1: We first derive the explicit form of
$\mathbb{E}[\overline{G}(\mathcal{S})]$. Recall that
$\overline{G}(\mathcal{S})=\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S}}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}$.
By taking the expectation of the both sides, we have

$\displaystyle\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}=$
$\displaystyle\mathbb{E}\Bigg{[}\sum_{i\in S}\sum_{j\in
S}\cos(\Phi_{i}-\Phi_{j})\Bigg{]}$ (24) $\displaystyle=$
$\displaystyle\mathbb{E}\Bigg{[}\lvert S\rvert+\sum_{i\in S}\sum_{j\neq
i}\cos(\Phi_{i}-\Phi_{j})\Bigg{]}$ (25) $\displaystyle=$ $\displaystyle\lvert
S\rvert+\sum_{i\in S}\sum_{j\neq
i}\mathbb{E}\Big{[}\cos(\Phi_{i}-\Phi_{j})\Big{]}$ (26) $\displaystyle=$
$\displaystyle\lvert S\rvert+\sum_{i\in S}\sum_{j\neq
i}\mathbb{E}[\cos(\Phi_{i})\cos(\Phi_{j})+\sin(\Phi_{i})\sin(\Phi_{j})]$ (27)
$\displaystyle=$ $\displaystyle\lvert S\rvert+\sum_{i\in S}\sum_{j\neq
i}\Big{(}\mathbb{E}[\cos(\Phi_{i})]\mathbb{E}[\cos(\Phi_{j})]$
$\displaystyle\qquad\qquad\qquad+\mathbb{E}[\sin(\Phi_{i})]\mathbb{E}[\sin(\Phi_{j})]\Big{)}$
(28) $\displaystyle=$ $\displaystyle\lvert S\rvert+\sum_{i\in S}\sum_{j\neq
i}e^{-\frac{\gamma_{i}}{2}}e^{-\frac{\gamma_{j}}{2}}$ (29) $\displaystyle=$
$\displaystyle\lvert S\rvert+\sum_{i\in S}\sum_{j\neq i}\sqrt{v_{i}v_{j}}.$
(30)

The equality in (25) follows directly from the observation that
$\cos(\Phi_{i}-\Phi_{i})$$=$$\cos(0)$$=$$1$. Using the linearity of
expectation, we obtain (26). Equality in (27) is a straightforward use of the
trigonometric identity $\cos(x-y)=\cos(x)\cos(y)+\sin(x)\sin(y)$. Under the
assumption that $\Phi_{i}$ and $\Phi_{j}$ are independent for $i$$\neq$$j$, we
obtain (28). The equality in (29) follows from Proposition 1, i.e.,
$\mathbb{E}[\sin(\Phi_{i})]=0$ and
$\mathbb{E}[\cos(\Phi_{i})]=e^{-\frac{\gamma_{i}}{2}}$. Finally, the equality
in (30) follows from the definition $v_{i}:=e^{-\gamma_{i}}$.

We now derive the explicit form of the variance of the beamforming gain.
Recall that
$\mathrm{Var}(\overline{G}(\mathcal{S}))$$=$$\mathbb{E}[\overline{G}(\mathcal{S})^{2}]$$-$$\mathbb{E}[\overline{G}(\mathcal{S})]^{2}$.
For $\mathbb{E}[\overline{G}(\mathcal{S})^{2}]$, we have

$\displaystyle\mathbb{E}\Big{[}\overline{G}(\mathcal{S})^{2}\Big{]}$
$\displaystyle=\mathbb{E}\Bigg{[}(\sum_{i\in\mathcal{S}}\sum_{j\in\mathcal{S}}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)})^{2}\Bigg{]}$
(31) $\displaystyle=\mathbb{E}\Bigg{[}\Bigg{(}\lvert
S\rvert+\sum_{i\in\mathcal{S}}\sum_{j\neq
i}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}\Bigg{)}^{2}\Bigg{]}$ (32)
$\displaystyle=\lvert S\rvert^{2}+2\lvert S\rvert\
\mathbb{E}\Bigg{[}\sum_{i\in S}\sum_{j\neq
i}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}\Bigg{]}$
$\displaystyle\quad+\mathbb{E}\Bigg{[}\Bigg{(}\sum_{i\in S}\sum_{j\neq
i}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}\Bigg{)}^{2}\Bigg{]}.$ (33)
$\displaystyle=\lvert S\rvert^{2}+2\lvert S\rvert\sum_{i\in S}\sum_{j\neq
i}\sqrt{v_{i}v_{j}}$ $\displaystyle\quad+\mathbb{E}\Bigg{[}\Bigg{(}\sum_{i\in
S}\sum_{j\neq i}\cos\Big{(}\Phi_{i}-\Phi_{j}\Big{)}\Bigg{)}^{2}\Bigg{]}.$ (34)

Using the trigonometric identity $2\sin(x)\cos(x)$$=$$\sin(2x)$, together with
the fact that $\mathbb{E}[\sin\lambda X]$$=$$0$ for
$\lambda$$\in$$\mathbb{N}$, it can be shown that the last term in (34) can be
expanded as

$\displaystyle\mathbb{E}\Bigg{[}\Bigg{(}\sum_{i\in S}\sum_{j\neq
i}\Big{(}\cos(\Phi_{i})\cos(\Phi_{j})+\sin(\Phi_{i})\sin(\Phi_{j})\Big{)}\Bigg{)}^{2}\Bigg{]}$
$\displaystyle=\mathbb{E}\Bigg{[}\Bigg{(}\sum_{i\in S}\sum_{j\neq
i}\cos(\Phi_{i})\cos(\Phi_{j})\Bigg{)}^{2}\Bigg{]}$
$\displaystyle\quad+\mathbb{E}\Bigg{[}\Bigg{(}\sum_{i\in S}\sum_{j\neq
i}\sin(\Phi_{i})\sin(\Phi_{j})\Bigg{)}^{2}\Bigg{]}.$

Furthermore, using Proposition 1, together with the identity
$2\cos^{2}(x)-1$$=$$1-2\sin^{2}(x)$$=$$\cos(2x)$ and Lemma 2, the terms on the
right hand side of the above equality can be written as

$\displaystyle\mathbb{E}\Big{[}\Big{(}\sum_{i\in S}\sum_{j\neq
i}\cos(\Phi_{i})\cos(\Phi_{j})\Big{)}^{2}\Big{]}=\frac{1}{2}\sum_{i\in
S}\sum_{j\neq i}(1+v_{i}^{2})(1+v_{j}^{2})$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+2\sum_{i\in
S}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}(1+v_{i}^{2})\sqrt{v_{j}v_{k}}$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad+\sum_{i\in
S}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}\sqrt{v_{i}v_{j}v_{k}v_{l}},$
$\displaystyle\mathbb{E}\Big{[}\Big{(}\sum_{i\in S}\sum_{j\neq
i}\sin(\Phi_{i})\sin(\Phi_{j})\Big{)}^{2}\Big{]}=\frac{1}{2}\sum_{i\in
S}\sum_{j\neq i}(1-v_{i}^{2})(1-v_{j}^{2}).$

As a result,

$\displaystyle\mathbb{E}\Big{[}\overline{G}(\mathcal{S})^{2}\Big{]}=$
$\displaystyle\lvert S\rvert^{2}+2\lvert S\rvert\sum_{i\in S}\sum_{j\neq
i}\sqrt{v_{i}v_{j}}+\sum_{i\in S}\sum_{j\neq i}(1+v_{i}^{2}v_{j}^{2})$
$\displaystyle+2\sum_{i\in S}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq i\\\
k\neq j\end{subarray}}(1+v_{i}^{2})\sqrt{v_{j}v_{k}}$
$\displaystyle+\sum_{i\in S}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq i\\\
k\neq j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}\sqrt{v_{i}v_{j}v_{k}v_{l}}.$

Similarly, for $\mathbb{E}[\overline{G}(\mathcal{S})]^{2}$, using Proposition
1, together with Lemma 2, we have

$\displaystyle\mathbb{E}\Big{[}\overline{G}(\mathcal{S})\Big{]}^{2}$
$\displaystyle=\Big{(}\lvert S\rvert+\sum_{i\in S}\sum_{j\neq
i}\sqrt{v_{i}v_{j}}\Big{)}^{2}$ $\displaystyle=\lvert S\rvert^{2}+2\lvert
S\rvert\sum_{i\in S}\sum_{j\neq i}\sqrt{v_{i}v_{j}}+\Big{(}\sum_{i\in
S}\sum_{j\neq i}\sqrt{v_{i}v_{j}}\Big{)}^{2}$ $\displaystyle=\lvert
S\rvert^{2}+2\lvert S\rvert\sum_{i\in S}\sum_{j\neq
i}\sqrt{v_{i}v_{j}}+2\sum_{i\in S}\sum_{j\neq i}v_{i}v_{j}$
$\displaystyle\quad+4\sum_{i\in S}\sum_{j\neq i}\sum_{\begin{subarray}{c}k\neq
i\\\ k\neq j\end{subarray}}v_{i}\sqrt{v_{j}v_{k}}+\sum_{i\in S}\sum_{j\neq
i}\sum_{\begin{subarray}{c}k\neq i\\\ k\neq
j\end{subarray}}\sum_{\begin{subarray}{c}l\neq i\\\ l\neq j\\\ l\neq
k\end{subarray}}\sqrt{v_{i}v_{j}v_{k}v_{l}}.$

Since
$\mathrm{Var}[\overline{G}(\mathcal{S})]$$=$$\mathbb{E}[\overline{G}(\mathcal{S})^{2}]$$-$$\mathbb{E}[\overline{G}(\mathcal{S})]^{2}$,
we obtain the result. $\Box$

Proof of Proposition 3: Recall that $v_{i}$$=$$\exp(-\gamma_{i})$ by
definition. By taking the derivative of (14) with respect to $\gamma_{k}$ for
an arbitrary $k$$\in$$\mathcal{S}$, we obtain

$\displaystyle\frac{\partial\mathbb{E}[\overline{G}(\mathcal{S})]}{\partial\gamma_{k}}=-\sum_{\begin{subarray}{c}j\in\mathcal{S}\\\
j\neq k\end{subarray}}\exp\Bigg{(}-\frac{\gamma_{k}+\gamma_{j}}{2}\Bigg{)}\leq
0.$

The above inequality implies that decreasing the value of the maximum
$\gamma_{k}$ increases the value of the expected beamforming gain. The result
then follows from the definition of $V(\mathcal{S})$. $\Box$

Proof of Theorem 1: We first show that if
$\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$ for
$\mathcal{S}$$=$$\\{i_{1},i_{2}\\}$, then a solution to the problem in
(18a)-(18b) is a solution to the subset selection problem. Recall that
$\gamma_{i_{1}}$$\leq$$\gamma_{i_{2}}$$\leq$$\ldots$$\leq$$\gamma_{i_{N}}$.
Then, when $\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$ for
$\mathcal{S}$$=$$\\{i_{1},i_{2}\\}$, the subset $\mathcal{S}$ is a solution to
the problem in (18a)-(18b). Now, observe from (15) that among the subsets
$\mathcal{S}^{\prime}$$\subseteq$$[N]$ that satisfy
$\lvert\mathcal{S}^{\prime}\rvert$$=$$2$, the subset
$\mathcal{S}$$=$$\\{i_{1},i_{2}\\}$ is the one that minimizes
$\mathrm{Var}(\overline{G}(\mathcal{S}^{\prime}))$. Moreover, since all the
terms in the right hand side of (15) are nonnegative, adding a new element to
a subset $\mathcal{S}^{\prime}$$\subseteq$$[N]$ that satisfy
$\lvert\mathcal{S}^{\prime}\rvert$$=$$2$ can only increase the value of
$\mathrm{Var}(\overline{G}(\mathcal{S}^{\prime}))$. Consequently, the subset
$\mathcal{S}$$=$$\\{i_{1},i_{2}\\}$ is the subset that satisfies the
constraint $\mathbb{E}[\overline{G}(\mathcal{S})]$$\geq$$\Gamma$ and minimizes
the variance of the beamforming gain. Hence, the claim holds.

We will now show that the second condition in the statement of the theorem is
also a sufficient condition for the equivalence of the problems in (18a)-(18b)
and (9a)-(9b) in terms of optimal solutions. Without loss of generality, let

$\displaystyle 0.83\geq\gamma_{1}\geq\gamma_{2}\geq\ldots\geq\gamma_{N}\geq
0.$ (35)

We take the derivative of $\mathrm{Var}(\overline{G}(\mathcal{S}))$ with
respect to $\gamma_{1}$ and show that the derivative is always nonnegative.
Equivalently, we show that the variance decreases as the maximum effective
error $\gamma_{i}$ decreases.

Recall that $v_{i}$$=$$\exp(-\gamma_{i})$. After some algebra, we obtain

$\displaystyle\frac{\partial\mathrm{Var}(\overline{G}(\mathcal{S}))}{\partial\gamma_{1}}=$
$\displaystyle 4\sum_{j\neq 1}v_{1}v_{j}(1-v_{1}v_{j})$
$\displaystyle+4v_{1}\Big{(}1-v_{1}\Big{)}\sum_{j\neq
1}\sum_{\begin{subarray}{c}k\neq 1\\\ k\neq j\end{subarray}}\sqrt{v_{j}v_{k}}$
$\displaystyle-2\sum_{j\neq 1}(1-v_{j})^{2}\sum_{\begin{subarray}{c}k\neq 1\\\
k\neq j\end{subarray}}\sqrt{v_{1}v_{k}}.$ (36)

Using (35), we obtain the following three inequalities which will be used to
bound each term on the right hand side of (Distributed Beamforming for Agents
with Localization Errors):

1) $\displaystyle\sum_{\begin{subarray}{c}j\in S\\\ j\neq
1\end{subarray}}v_{1}v_{j}(1-v_{1}v_{j})\geq(\lvert
S\rvert-1)v_{1}^{2}(1-v_{1})$ 2) $\displaystyle\sum_{\begin{subarray}{c}j\in
S\\\ j\neq 1\end{subarray}}\sum_{\begin{subarray}{c}k\neq 1\\\ k\neq
j\end{subarray}}\sqrt{v_{j}v_{k}}\geq 2\binom{\lvert S\rvert-1}{2}v_{1}$ 3)
$\displaystyle\sum_{\begin{subarray}{c}j\in S\\\ j\neq
1\end{subarray}}\sum_{\begin{subarray}{c}k\neq 1\\\ k\neq
j\end{subarray}}(1-v_{1})^{2}\sqrt{v_{1}v_{k}}\leq 2\binom{\lvert
S\rvert-1}{2}(1-v_{1})^{2}\sqrt{v_{1}}$

Consequently, we have

$\displaystyle\frac{\partial\mathrm{Var}(\overline{G}(\mathcal{S}))}{\partial\gamma_{1}}\geq$
$\displaystyle 4(\lvert S\rvert-1)v_{1}^{2}(1-v_{1})+8\binom{\lvert
S\rvert-1}{2}v_{1}^{2}(1-v_{1})$ $\displaystyle-4\binom{\lvert
S\rvert-1}{2}(1-v_{1})^{2}\sqrt{v_{1}}.$ (37)

By rearranging the terms and using that $\gamma_{1}$$\leq$$0.83$, we obtain

$\displaystyle\frac{\partial\mathrm{Var}(\overline{G}(\mathcal{S}))}{\partial\gamma_{1}^{2}}\geq$
$\displaystyle 2(\lvert S\rvert-1)\sqrt{v_{1}}(1-v_{1})\times$
$\displaystyle\Bigg{[}2(\lvert S\rvert-1)(v_{1})^{3/2}-(\lvert
S\rvert-2)(1-v_{1})\Bigg{]}\geq 0.$

Finally, since the above inequality implies that the variance can be decreased
by decreasing the maximum effective error $\gamma_{1}$, an optimal solution to
the problem in (18a)-(18b) is an optimal solution to the subset selection
problem when $\gamma_{1}$$\leq$$0.83$. $\Box$

Proof of Theorem 2: We start with establishing supermodularity of
$\mathbb{E}[\overline{G}(\mathcal{S})]$. For $X,Y$$\subseteq$$[N]$ such that
$X$$\subseteq$$Y$, let $X^{\prime}$$=$$X\cup\\{e\\}$ and
$Y^{\prime}$$=$$Y\cup\\{e\\}$ where $e$$\in$$[N]$$\backslash$$Y$. We have,

$\displaystyle
X_{\text{diff}}:=\mathbb{E}[\overline{G}(X^{\prime})]-\mathbb{E}[\overline{G}(X)]=1+2\sqrt{v_{e}}\sum_{i\in
X}\sqrt{v_{i}},$ $\displaystyle
Y_{\text{diff}}:=\mathbb{E}[\overline{G}(Y^{\prime})]-\mathbb{E}[\overline{G}(Y)]=1+2\sqrt{v_{e}}\sum_{i\in
Y}\sqrt{v_{i}}.$

Using the fact that $v_{i}\geq 0$ and $X$$\subseteq$$Y$, we obtain

$\displaystyle X_{\text{diff}}-Y_{\text{diff}}=-2\sqrt{v_{e}}\sum_{i\in
Y\backslash X}\sqrt{v_{i}}\leq 0.$

Hence, we conclude that $\mathbb{E}[\overline{G}(\mathcal{S})]$ is
supermodular.

We now show the supermodularity of $\mathrm{Var}(\overline{G}(\mathcal{S}))$.
For $X,Y$$\subseteq$$[N]$ such that $X$$\subseteq$$Y$, let
$X^{\prime}$$=$$X\cup\\{e\\}$ and $Y^{\prime}$$=$$Y\cup\\{e\\}$ where
$e$$\in$$[N]$$\backslash$$Y$. Then, we have

$\displaystyle\overline{X}_{\text{diff}}:$
$\displaystyle=\mathrm{Var}\Big{(}\overline{G}(X^{\prime})\Big{)}-\mathrm{Var}\Big{(}\overline{G}(X)\Big{)}$
$\displaystyle=2\sum_{i\in X}(1-v_{e}v_{i})^{2}+2(1-v_{e})^{2}\sum_{i\in
X}\sum_{j\neq i}\sqrt{v_{i}v_{j}}$ $\displaystyle\quad+4\sqrt{v_{e}}\sum_{i\in
X}\sum_{j\neq i}(1-v_{i})^{2}\sqrt{v_{j}},$
$\displaystyle\overline{Y}_{\text{diff}}:$
$\displaystyle=\mathrm{Var}\Big{(}\overline{G}(Y^{\prime})\Big{)}-\mathrm{Var}\Big{(}\overline{G}(Y)\Big{)}$
$\displaystyle=2\sum_{i\in Y}(1-v_{e}v_{i})^{2}+2(1-v_{e})^{2}\sum_{i\in
Y}\sum_{j\neq i}\sqrt{v_{i}v_{j}}$ $\displaystyle\quad+4\sqrt{v_{e}}\sum_{i\in
Y}\sum_{j\neq i}(1-v_{i})^{2}\sqrt{v_{j}}.$

Using the fact that $v_{i}\geq 0$ and $X$$\subseteq$$Y$, it is then
straightforward to show that $X_{\text{diff}}-Y_{\text{diff}}$$\leq$$0$. This
concludes the proof. $\Box$