Collaborative Beamforming Under Localization Errors: A Discrete Optimization Approach
Erfaun Noorani Yagiz Savas Alec Koppel John Baras Ufuk Topcu Brian M. Sadler
eess.SP cs.IT math.IT

Meteoroid Bombardment of Lunar Poles
    Erwan Mazarico
    December 30, 2023
====================================


We consider a network of agents that locate themselves in an environment through sensor measurements and aim to transmit a message signal to a base station via collaborative beamforming. The agents' sensor measurements result in localization errors, which degrade the quality of service at the base station due to unknown phase offsets that arise in the agents' communication channels. Assuming that each agent's localization error follows a Gaussian distribution, we study the problem of forming a reliable communication link between the agents and the base station despite the localization errors. In particular, we formulate a discrete optimization problem to choose only a subset of agents to transmit the message signal so that the variance of the signal-to-noise ratio (SNR) received by the base station is minimized while the expected SNR exceeds a desired threshold. When the variances of the localization errors are below a certain threshold characterized in terms of the carrier frequency, we show that greedy algorithms can be used to globally minimize the variance of the received SNR. On the other hand, when some agents have localization errors with large variances, we show that the variance of the received SNR can be locally minimized by exploiting the supermodularity of the mean and variance of the received SNR. In numerical simulations, we demonstrate that the proposed algorithms have the potential to synthesize beamformers orders of magnitude faster than convex optimization-based approaches while achieving comparable performances using less number of agents. 


collaborative beamforming, localization error, discrete optimization




§ INTRODUCTION

Collaborative beamforming is a wireless communication technique in which a network of agents collectively transmit a common message signal to a base station <cit.>. Compared to single-agent transmission, collaborative beamforming has the potential to increase the range and rate of communication, to improve the directivity of the beam pattern, or to decrease the agents' individual power consumption while achieving the same quality of service (QoS) at the base station <cit.>. For example, in a network of N agents, if each agent transmits the message signal with a fixed power, collaborative beamforming can lead to a factor of N^2 increase in the signal-to-noise ratio (SNR) received by the base station.

When the agents are distributed in an environment, which is the case in most multi-agent planning scenarios, e.g.,  <cit.>, realizing the full potential of collaborative beamforming proves itself to be a challenge due to the unknown phase offsets that arise in the agents' communication channels <cit.>. The unknown phase offsets, which degrade the QoS at the base station, has mainly two sources: synchronization errors between the agents' local oscillators and the agents' localization errors. The former source has been extensively studied in the literature, and there are now a number of decentralized algorithms that can be used to mitigate the undesired effects of synchronization errors between the agents <cit.>. The latter source commonly arises in practice since the agents typically estimate their positions using sensor measurements resulting in an error associated with position <cit.>. The objective of this paper is to develop efficient beamforming methods that optimize the QoS at the base station despite the agents' localization errors. 




From the analysis perspective, prior work focuses on understanding the effects of localization errors in collaborative beamforming. The agents' localization errors are associated with the topology of the network and translate to phasing errors in the transmission <cit.>. The beam pattern characteristics for randomly generated network topologies is analyzed using the random array theory <cit.>. Specifically, the authors in <cit.> consider a setting in which each agent's location in the environment is sampled from the same Gaussian distribution. They prove that, in this setting, the expected SNR received by the base station decays exponentially with a rate proportional to the variance of the Gaussian distribution. In <cit.>, the authors show that, when the agents have fixed transmission powers and their phasing errors are identically distributed, the expected SNR increases quadratically with the number of agents so long as the expected cosine of the phasing errors is close to one. 

In many multi-agent planning scenarios, the agents' position estimates follow non-identical distributions, in which case the aforementioned results cannot be used to synthesize effective beamformers. Accordingly, in this paper, we consider a setting in which the agents' localization errors follow Gaussian distributions with potentially different mean and covariance. We derive the first- and second-order statistics of the received SNR as a function of the subset of agents that transmit the message signal. We then utilize the derived statistics to develop algorithms that include only a subset of agents in beamforming to optimize the QoS at the base station. 

From the algorithmic perspective, different approaches are proposed to synthesize beamformers that mitigate the undesired effects of phasing errors in the transmission. Ideally, with no localization and synchronization errors, the topology of the network may be used to derive the optimal beamformer, and we refer to this as the perfect channel state information (CSI) case. The work <cit.> considers a case in which no CSI is available at the agents, i.e., the agents have no statistical information regarding their localization errors. The authors propose an iterative algorithm that maximizes the SNR at the base station by receiving feedback from the base station at each iteration. Subsequent work further investigates how the received feedback can be utilized to improve the reliability and security of communication <cit.>. Although feedback-based approaches successfully improve the QoS at the base station, such approaches are iterative in nature. Therefore, their convergence to desired QoS levels may, in general, require a considerable number of iterations depending on network topology.
In the case of imperfect CSI, i.e., when a statistical information of the channel is available at the agents, algorithms based on semi-definite programs (SDPs) are proposed to ensure that the received SNR is above a threshold with desired probability <cit.>. Similar conic optimization-based formulations are also common in the robust beamforming literature <cit.>. While SDP formulations provide a powerful method to improve the QoS without requiring feedback from the base station, they are computationally expensive and do not scale well with the number of agents.





In this paper, we approach the beamformer design problem from a discrete optimization perspective and develop three algorithms to choose a subset of agents to transmit the message signal to the base station. Given a network of agents with associated Gaussian localization errors, we seek a subset of agents to form a beam that achieves the desired QoS requirements without receiving feedback from the base station. To the best of our knowledge, this paper is the first one to employ discrete optimization techniques for mitigating the effects of localization errors in collaborative beamforming with provable performance guarantees. The main contributions of this paper are as follows:

    
  * First, under the assumption that each agent has a Gaussian localization error, we derive explicit forms of the expected value and the variance of the received SNR as a function of the agents that are included in beamforming. Using the derived expressions, we formulate a novel risk-sensitive discrete optimization problem: find a subset of agents to transmit the message signal such that the variance of the SNR at the base station is minimized while the expected SNR exceeds a desired threshold.
    
  * Second, we propose two efficient sorting-based algorithms, Greedy and Double-Loop-Greedy (DLG), to solve the formulated discrete optimization problem and present sufficient conditions for their optimality. In particular, we show that the proposed algorithms return an optimal subset if the variance of the agents' localization errors is below a certain threshold which is characterized in terms of the carrier frequency. 
    
  * Third, we prove that the expected value and the variance of the received SNR are supermodular set functions. Using this property, we develop a third algorithm, Difference-of-Submodular (DoS), which returns a subset that is locally optimal for a certain relaxation of the formulated discrete optimization problem. The DoS algorithm utilizes the so-called submodular-supermodular procedure <cit.> as a subprocedure, and its local optimality guarantee is independent of the carrier frequency.
 

The results presented in this paper show that, in the presence of localization errors, we may achieve the full potential of collaborative beamforming with minimum variability by including only a subset of the agents in beamforming. In particular, when the agents have small localization errors characterized in terms of the carrier frequency, we can globally minimize the variance of the SNR received by the base station using sorting-based algorithms. On the other hand, if some of the agents violate the small localization error condition, we can locally minimize the variance of the received SNR by exploiting the supermodularity of the mean and variance of the SNR. 



In numerical simulations, we compare the performance of the proposed algorithms with an SDP-based beamformer and demonstrate that all three algorithms, i.e., Greedy, DLG, and DoS, exhibit similar performances to that of the SDP-based beamformer while using less number of agents in beamforming. Moreover, for problem instances with large number of agents, Greedy and DLG algorithms compute the agent subset orders of magnitude faster than the SDP-based beamformer. 

Related work: 
A preliminary version of this paper appeared in <cit.>, where we present the Greedy algorithm to solve the subset selection problem formulated in this paper. The major differences of this considerably extended version from the preliminary version are the following. First, we provide a numerical example illustrating the potential suboptimality of the Greedy algorithm and present the DLG algorithm, which improves the empirical performance over the Greedy algorithm. Second, we prove the supermodularity of the mean and variance of the received SNR as a function of the selected agent subsets and present the DoS algorithm to locally minimize the variance of the received SNR. Third, we provide numerical simulations to compare the performance of the Greedy, DLG, and DoS algorithms. Finally, we provide detailed proofs for all technical results. 

In addition to the aforementioned references, the subject of this paper is also related to the beamformer design when the agents have only local position information. Specifically, in <cit.>, the authors consider a setting in which the global location information is not available at the agents and design an antenna array that approximates the performance of a linear antenna array using only the information of exact inter-agent distances. Here, we consider a setting in which the statistics of the global location information is available at the agents. Hence, both the problem formulation and the proposed solution approaches are considerably different from the ones presented in <cit.>.

The idea of using only a subset of available agents in beamforming is previously investigated in the literature for various purposes. In <cit.>, the authors choose a subset of sensor nodes to control the maximum sidelobe level. The work <cit.> develops a discete-optimization based algorithm to design a sensor array for spatial sensing applications. Finally, the reference <cit.> studies the antenna selection problem in multicast beamforming. Unlike the above references, we consider the problem of achieving the desired SNR level at the base station with minimum variability despite localization errors and design discrete optimization-based algorithms that have provable performance guarantees.




§ SYSTEM MODEL
  


We consider a group of N∈ℕ agents that are distributed in an environment. Each agent is equipped with a single ideal isotropic antenna with a constant transmit power P>0. The agents' objective is to transmit a common message signal m(t)∈ℝ to a base station equipped with a single antenna. 




 §.§ Communication Channel


Regarding the communication channel between the agents and the base station, we make the following assumptions.

    
  * The transmitted signal m(t) propagates in free space with no reflection or scattering.
    
  * There is no mutual coupling effects between the agents' antennas.
    
  * The local oscillators of all agents are time- and frequency-synchronized.
    
  * The base station is located in the far-field region.
    
  * The agent i∈[N] transmits the signal m(t) over a narrowband wireless channel h_i∈ℂ.
    
  * All channels attenuate the signal m(t) at the same level, i.e., | h_i|=| h_j| for all i,j∈[N].


The assumption that the signal propagates in free space may hold in cluttered environments when the agents communicate with the base station at low VHF frequencies <cit.>. Similarly, mutual coupling effects may be avoided when the agents are sufficiently separated from each other. To achieve the frequency and time synchronizations, the agents may follow a separate short-range radio protocol <cit.>. Finally, the signal attenuation for all channels may be similar in scenarios in which the distance between the agents and the base station is significantly larger than inter-agent distances.

  


 §.§ Collaborative Transmission Model

 
We consider a subset 𝒮⊆[N] of agents that collectively transmit the message signal m(t) to the base station. All agents modulate m(t) with the carrier signal Re{e^j2π f_c t}, where f_c is the carrier frequency. Each agent i∈𝒮 adjusts the phase of the transmission with the complex gain w_i∈ℂ where | w_i|=√(P), i.e., the transmit power is P. Then, the signal received by the base station is 

    y_𝒮(t)   :=Re{e^j2π f_c tm(t)∑_i∈𝒮 w_i h_i }+n(t)


where n(t) is additive white Gaussian noise. Without loss of generality, we let w_i=√(P)e^jδ_i and h_i=a_i e^jη_i for each i∈[N]. The angle δ_i∈[0,2π) denotes the phase of the gain w_i, and it is a design parameter. The magnitude a_i>0 and the phase η_i∈[0,2π) characterize the channel h_i between the base station and the agent i∈[N]. Recall that the agents' local oscillators are time-synchronized. Then, the phase offset η_i of a signal at the base station relative to a signal transmitted by an agent located at r⃗_i∈ℝ^3 (in Cartesian coordinates) is <cit.>


    η_i = -2π f_c/C⟨r⃗_i, r⃗_c  ⟩.


In (<ref>), r⃗_c∈ℝ^3 is the unit vector pointing in the known direction of the base station, C is the speed of light, and ⟨·,·⟩ is the inner product of two vectors. 

We assume that the agents' local positions {r⃗_i : i∈[N]} are not exactly known. In particular, for i∈[N], we assume that r⃗_i∼𝒩(μ_i,Σ_i) where μ_i∈ℝ^3 and Σ_i∈ℝ^3× 3 are, respectively, the known mean and the known covariance of the Gaussian distribution. We note that the first and second order statistics of position estimates are typically easy to obtain in practice <cit.>. Finally, we assume that r⃗_i and r⃗_j are independent for i,j∈[N] such that i≠j. 

For a given subset 𝒮⊆[N] and the corresponding phase parameters δ_i for each i∈𝒮, let the array factor be


    F(𝒮,δ):=|∑_i∈𝒮 e^j (δ_i+η_i)|

where δ:=[δ_i | i∈𝒮] is the vector of phase parameters. Assuming that | h_i|=| h_j| for all i,j∈[N], the magnitude of the array factor is proportional to the square root of the SNR received by the base station <cit.>. Let the total phase be Φ_i:=δ_i+η_i. The square of the the array factor yields the beamforming gain G(𝒮,δ) that is proportional to the received SNR and given by


    G(𝒮,δ):= F^2(𝒮,δ)=∑_i∈𝒮∑_j∈𝒮cos(Φ_i-Φ_j).






§ PROBLEM STATEMENT
  

The beamforming gain G(𝒮,δ) is a fundamental quantifier of the quality of a communication link with the base station as it is proportional to the received SNR. Hence, to establish a reliable communication link, we want the beamforming gain to be high with minimum variability. 

When the relative phase offsets η_i are known, one can maximize G(𝒮,δ) by selecting a pair (𝒮,δ) such that


    (𝒮,δ)∈_𝒮⊆[N],
    δ∈ [0,2π)^NG(𝒮,δ).

An optimal solution to the above optimization problem can be obtained by choosing 𝒮=[N] and δ_i=-η_i for all i∈𝒮. To see this, recall that the total phase Φ_i=δ_i+η_i, and note that

    G(𝒮,δ)=∑_i∈𝒮∑_j∈𝒮cos(Φ_i-Φ_j)≤ N^2.

The upper bound in (<ref>) is attained if and only if 𝒮=[N] and Φ_i=Φ_j for all i,j∈𝒮, i.e., the total phases are aligned. 

In this paper, we focus on a scenario in which G(𝒮,δ) is a random variable since the agents' local positions {r⃗_i:i∈[N]} are such that r⃗_i∼𝒩(μ_i,Σ_i). In such a scenario, a reasonable objective might be to maximize the expected beamforming gain by selecting a pair (𝒮,δ) such that

    (𝒮,δ)∈_𝒮⊆[N],
    δ∈ [0,2π)^N𝔼[G(𝒮,δ)].


In Section <ref>, we show that the pair (𝒮,δ)=([N],δ̂), where δ̂=[δ̂_i | i∈[N]] such that

    δ̂_i:=-𝔼[η_i]   for all   i∈[N],

constitutes a solution to the problem in (<ref>). In other words, 𝔼[G(𝒮,δ)] is maximized by including all the agents in beamforming and aligning their total phases Φ_i in expectation. 

Although including all the agents in beamforming maximizes the expected beamforming gain, due to the random phase errors, this approach may actually decrease the probability with which the beamforming gain exceeds a certain threshold. To overcome this undesirable effect, we consider the variance of the beamforming gain as a risk measure and formulate a discrete optimization problem that includes only a subset of the agents in beamforming. In particular, we first fix the vector δ of phase parameters such that the expected beamforming gain is maximized, i.e., δ=δ̂. Then, we aim to choose a subset 𝒮⊆[N] of agents that minimizes the variance of the beamforming gain while ensuring that the expected beamforming gain exceeds the desired threshold. The formal problem statement is as follows. 

Problem 1: (Subset selection) For a constant Γ>0, and the fixed vector of phase parameters δ=δ̂, find 𝒮^⋆⊆[N] such that 


    𝒮^⋆∈    _𝒮⊆ [N]    Var(G (𝒮,δ̂))
       subject to:  𝔼[G (𝒮,δ̂)]≥Γ.



Formulations that are similar to the subset selection problem are widely used in risk-sensitive optimization models <cit.>. By formulating a discrete optimization problem, we aim to design algorithms that improve the reliability of the communication link by minimizing the variability of received SNR and utilizing only a subset of the agents in beamforming. Finally, we remark that, in the subset selection problem, each agent i∈[N] needs only its own position information, i.e., distribution of η_i, to set δ=δ̂. Hence, in the considered setting, the agents adjust their phases in a distributed manner. 










§ STATISTICAL PROPERTIES OF THE BEAMFORMING GAIN 


In this section, we first derive the explicit form of the expected beamforming gain 𝔼[G(𝒮,δ)] and show that the pair (𝒮,δ)=([N],δ̂) is a solution to the problem in (<ref>). We then set δ=δ̂ and derive the explicit form of Var(G(𝒮,δ̂)). The derived explicit forms are utilized to develop subset selection algorithms in the following sections.

Consider the definition of G(𝒮,δ), given in (<ref>), and recall that, for all i∈[N], Φ_i=η_i+δ_i where η_i=2π f_c ⟨r⃗_i, r⃗_c ⟩/ C and r⃗_i∼𝒩(μ_i,Σ_i). Then, for a given vector δ∈[0,2π)^N of phase parameters, we have Φ_i∼𝒩(θ_i,γ_i) where
 
    θ_i:= 2πf_c/C ⟨μ_i, r⃗_c⟩+δ_i   and    γ_i:= 4π^2 f_c^2/C^2 ⟨r⃗_c, Σ_i r⃗_c⟩. 19pt

We refer to γ_i as the effective error variance in the localization of the ith agent. Using the fact that Φ_i∼𝒩(θ_i,γ_i), we obtain the explicit form of 𝔼[G(𝒮,δ)] as follows.

Let v_i:=exp(-γ_i). We have


    𝔼[G(𝒮,δ)]=|𝒮| +∑_i∈𝒮∑_j∈𝒮
     j≠ i√(v_i v_j)cos(θ_i-θ_j).



The following result shows that we can maximize the expected beamforming gain by including all the agents in beamforming and aligning their phases in expectation.

A pair (𝒮,δ) solves the problem in (<ref>) if and only if 𝒮=[N] and, for all i,j∈[N], we have

    ((δ_i+𝔼[η_i])- (δ_i+𝔼[η_i])) 2 π = 0.



We provide proofs for the above propositions in Appendix <ref>. The condition S=[N] indicates that all the agents should be included in beamforming to maximize the expected beamforming gain. On the other hand, the condition in (<ref>) implies that the agents' total phases should be aligned in expectation. Note that the vector δ̂, where δ̂_i=-𝔼[η_i] for all i∈[N], satisfies the condition in (<ref>). In the subset selection problem, we set δ=δ̂ and aim to find a subset 𝒮⊆[N] that solves the risk-sensitive optimization problem given in (<ref>)-(<ref>).

When δ=δ̂, we have θ_i=θ_j for all i,j∈[N], implying that

    𝔼[G(𝒮,δ̂)]=|𝒮| +∑_i∈𝒮∑_j∈𝒮
     j≠ i√(v_i v_j).

Next, we derive the variance of G(𝒮,δ̂) as follows.

Let v_i:=exp(-γ_i). We have




    Var(G(𝒮,δ̂))=   ∑_i∈𝒮∑_j∈𝒮
     j≠ i(1-v_iv_j)^2
        +2∑_i∈𝒮∑_j∈𝒮
     j≠ i∑_k∈𝒮
     k≠ i
     k ≠ j(1-v_i)^2√(v_j v_k).



We provide a proof for the above result in Appendix <ref>. The proof exploits the equivalence 𝔼[exp(tX)]=exp(jμ t-σ^2t^2/2) where X∼𝒩(μ,σ) and the independence of r⃗_i and r⃗_j for i≠j to obtain the explicit form.





§ AGENT SELECTION UNDER LOCALIZATION ERRORS
 
In this section, we propose three algorithms to solve the subset selection problem and analyze their optimality guarantees. Throughout this section, we assume that the problem in (<ref>)-(<ref>) has a feasible solution. For a given problem instance, the validity of this assumption can be easily verified by checking whether 𝔼[G([N],δ̂)]≥Γ due to the following result.

For any 𝒮⊆𝒮'⊆[N], 𝔼[G (𝒮,δ̂)]≤𝔼[G (𝒮',δ̂)].

The above result follows immediately from the fact that 𝔼[G(𝒮,δ̂)] is a sum of nonnegative terms; hence, adding an element to the subset can only increase the sum.



 §.§ Greedy Algorithm

In this section, we consider a simple greedy algorithm to solve the subset selection problem and provide sufficient conditions for its optimality. The Greedy algorithm, shown in Algorithm <ref>, first sorts the agents' effective error variances γ_i, defined in (<ref>), in ascending order. We note that the sorting operation can be performed in 𝒪(Nlog (N)) for an array of length N <cit.>. Initializing the output set 𝒮 to the empty set, the algorithm then iteratively adds the agent with the next lowest effective error variance to the output set until the constraint 𝔼[G(𝒮,δ̂)]≥Γ is satisfied.

  
  


We now present sufficient conditions on the set {γ_i : i∈[N]} for which the Greedy algorithm returns an optimal solution to the problem in (<ref>)-(<ref>). Let the total effective error variance of a subset 𝒮⊆[N] be measured by the function V:2^[N]→ℝ where V(𝒮):=∑_i∈𝒮γ_i. Consider the problem of choosing a subset 𝒮'⊆[N] that satisfies the constraint in (<ref>) and has the minimum total effective error variance, i.e.,


    𝒮'∈    min_𝒮⊆ [N]   V(𝒮)
       subject to:   𝔼[G (𝒮,δ̂)]≥Γ.


The next result, together with Proposition <ref>, implies that the Greedy algorithm yields an optimal solution to the problem in (<ref>)-(<ref>).


For any K∈ℕ such that K≤N, we have

    min_𝒮⊆ [N]:
    |𝒮|=K  V(𝒮) =max_𝒮⊆ [N]:
    |𝒮|=K𝔼[G(𝒮,δ̂)].




The above result follows from the fact that the derivative of the expected beamforming gain 𝔼[G(𝒮,δ̂)] with respect to γ_i, where i∈𝒮, is always negative. It can be shown that the problems in (<ref>)-(<ref>) and (<ref>)-(<ref>) are not equivalent in general. Hence, the greedy approach is, in general, not optimal to solve the subset selection problem. However, there are certain sufficient conditions, which are formalized below, under which such an approach becomes optimal.
 For a given set {γ_i : i∈[N]} of effective error variances, let γ_i_1≤γ_i_2≤...≤γ_i_N where i_k∈[N]. A solution to the problem in (<ref>)-(<ref>) is also a solution to the problem in (<ref>)-(<ref>) if either one of the following conditions hold:

   
  (C1)  𝔼[G(𝒮,δ̂)]≥Γ where 𝒮={i_1,i_2},
   
  (C2) γ_i_N≤0.83.




We provide a proof for the above result in Appendix <ref>. The main idea in the proof is to show that the derivative of Var(G(𝒮,δ̂)) with respect to max_i∈𝒮γ_i is positive. Condition (C1) follows from the fact that, when |𝒮|≤2, the derivative is always positive. Condition (C2) follows from the fact that, when γ_i_N≤0.83, the derivative is positive regardless of the size of the set 𝒮. For such γ_i_N, the subset with minimum total effective error variance is the one that minimizes the variance of the beamforming gain; hence, the problems in (<ref>)-(<ref>) and  (<ref>)-(<ref>) become equivalent when (C1) or (C2) holds.

Theorem <ref> states that if all the agents have “small" effective error variances, then the Greedy algorithm returns an optimal solution to the subset selection problem. In particular, it follows from Theorem <ref> that a sufficient condition for optimality characterized by the carrier frequency is

    max_i∈ [N]⟨r⃗_c, Σ_i r⃗_c⟩≤0.83 C^2/4π^2 f_c^2.










For example, suppose that Σ_i=σ_i^2 I_3× 3, where I_3× 3 is the identity matrix, and let σ_max^2:=max_i σ_i^2. Then, we have σ_max^2≤0.83 C^2/4π^2 f_c^2 as the sufficient condition (C2). In Figure <ref>, we graphically illustrate the trade-off between the carrier frequency f_c and the maximum variance σ_max^2 under which the Greedy algorithm is optimal. Note that as f_c increases (resulting in shorter wavelength), condition (C2) requires smaller position error variance, whereas longer wavelengths increase the error tolerance. For example, at lower VHF frequencies, e.g., f_c=40 MHz for which the effective wavelength is λ_c=C/f_c≈7.5 meters, the agents are allowed to have localization error variance up to 1 square meter. Hence, for this frequency range, the position error tolerance can easily be achieved with existing localization algorithms <cit.>.






 §.§ Suboptimality of the Greedy Algorithm


In this section, we illustrate with a numerical example that the Greedy algorithm may fail to return an optimal solution to the subset selection problem instances that violate the sufficient conditions presented in Theorem <ref>.

Let the total number of agents be N=4, and the expected gain threshold be Γ=3.3. Furthermore, let the ordered set (γ_1,γ_2, γ_3, γ_4) of effective error variances be (0.4,0.6,3,5). It can be shown by direct calculations that this problem instance violates the sufficient conditions presented in Theorem <ref>. Moreover, using Proposition <ref> and the monotonocity of Var(G(𝒮,δ̂)) in 𝒮⊆[N], it can be shown that |𝒮^⋆|=3. Let 𝒮_1:={1,2,3}, 𝒮_2:={1,2,4}, 𝒮_3:={1,3,4}, and 𝒮_4:={2,3,4} be all possible subsets of {1, 2, 3, 4} containing three elements. In Figure <ref>, we provide the expected value and the variance of the beamforming gain G(𝒮_k,δ̂) as well as the total effective error V(𝒮_k) for each 𝒮_k. All subsets 𝒮_k satisfy 𝔼[G(𝒮_k,δ̂)]≥Γ. Observe that the optimal solution for this problem instance is the subset 𝒮_4 which has the maximum total effective error variance V(𝒮_4) instead of the minimum one V(𝒮_1). Therefore, for this problem instance, the Greedy algorithm does not yield the optimal solution to the subset selection problem.




The above numerical example illustrates a counterintuitive fact: for some problem instances, the optimal subset consists of the agents with the highest effective localization error variances. This phenomenon arises due to the constructive/destructive interference of the sinusoids in (<ref>). Next, we modify the Greedy algorithm to account for the fact that for some instances the agents with the highest effective localization error variances may provide an optimal solution to the subset selection problem.







 §.§ Double-Loop-Greedy for Improved Empirical Performance

Inspired by the numerical example given in the previous section, as the second approach to solve the subset selection problem, we propose the Double-Loop-Greedy (DLG) algorithm shown in Algorithm <ref>. Similar to the Greedy algorithm, the DLG algorithm first sorts the agents' effective error variances γ_i in ascending order.
It then initializes two sets, namely, 𝒮_1 and 𝒮_2, to the empty set. Starting from the agent with the lowest effective error variance, at each iteration, the agent with the next lowest effective error variance is iteratively added to the set 𝒮_1 until the constraint 𝔼[G(𝒮_1,δ̂)]>Γ is satisfied. Note that 𝒮_1 is the same as the Greedy algorithm. Similarly, starting from the agent with the highest effective error variance, at each iteration, the agent with the next highest effective error variance is iteratively added to the set 𝒮_2 until the constraint 𝔼[G(𝒮_2,δ̂)]>Γ is satisfied. Finally, the DLG algorithm compares the variance of the beamforming gain for 𝒮_1 and 𝒮_2, and outputs the one with smaller value. We note that the time complexity of the DLG algorithm is the same as the time complexity of the Greedy algorithm.




Optimality of the DLG algorithm:
For a given problem instance, the subset 𝒮⊆[N] returned by the DLG algorithm is guaranteed to satisfy Var(G(𝒮,δ̂))≤Var(G(𝒮',δ̂)) where 𝒮'⊆[N] is the subset returned by the Greedy algorithm. Hence, the DLG algorithm also provides an optimal solution to the problem in (<ref>)-(<ref>) under the sufficient conditions stated in Theorem <ref>. Moreover, as can be seen from the numerical example given in the previous section, the DLG algorithm may also return an optimal solution to instances on which the Greedy algorithm performs poorly.




 §.§ Difference-of-Submodular (DoS) Algorithm
 
Both the Greedy and DLG algorithms are guaranteed to return optimal solutions to the subset selection problem under the sufficient conditions stated in Theorem <ref>. In this section, we propose a third approach to solve the subset selection problem, which always returns a locally optimal solution to a certain relaxation of the subset selection problem. Although the proposed third approach is computationally more demanding, its local optimality guarantee is independent of the carrier frequency unlike the greedy approaches.

Before presenting the proposed approach, i.e., Difference-of-Submodular (DoS) algorithm, we first provide a definition of submodularity and show that both  𝔼[G (𝒮,δ̂)] and Var(G (𝒮,δ̂)) are supermodular set functions.
 A set function f:2^Ω→ℝ is submodular if for every X, Y⊆Ω with X⊆Y and every e∈Ω\ Y, we have f(X∪{e})- f(X) ≥ f(Y∪{e})- f(Y).

A set function f:2^Ω→ℝ is said to be supermodular if the set function -f is submodular.


Both 𝔼[G (𝒮,δ̂)] and Var(G (𝒮,δ̂)) are supermodular set functions.


A proof of Theorem <ref> is provided in Appendix <ref>. Next, we formalize the notion of local optimality for discrete optimization problems and introduce the DoS algorithm which utilizes the results of <cit.> as subprocedures.

<cit.> For a set function ϕ:2^Ω→ℝ, a sequence {S_t⊆Ω : t∈ℕ} is said to converge to a local minimum if there exists a constant M∈ℕ such that ϕ(S_m)=ϕ(S_n) for all m,n≥M, and for any k∈ℕ, ϕ(S_k)≤ϕ(S_l) for all l≤k.


Let f:2^Ω→ℝ and g:2^Ω→ℝ be submodular set functions. In <cit.>, the authors present an algorithm, called Submodular-Supermodular-Procedure (SSP), that returns a local optimal solution to the following problem

    min_ S⊆Ω   f(S) -  g(S).


The DoS algorithm, shown in Algorithm <ref>, 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 λ_0>0 and α>1 as inputs as well as the agents' effective localization error variances γ_i and the expected gain threshold Γ. At the kth iteration, where k∈ℕ, using the SSP as a subprocedure, the DoS algorithm finds a locally optimal solution to the following problem

    min_𝒮⊆ [N]   Var(G(𝒮,δ̂)) - λ_k  𝔼[G(𝒮,δ̂)]

where λ_k is iteratively defined as λ_k=αλ_k-1. The algorithm terminates when the solution returned by the SSP satisfies 𝔼[G(𝒮,δ̂)]≥Γ.



 Convergence of the DoS algorithm: For the DoS algorithm to terminate, the subprocedure SSP should output a subset 𝒮⊆[N] such that 𝔼[G (𝒮,δ̂)]≥Γ. At the kth iteration, the SSP finds a locally optimal solution to the problem in (<ref>) by computing successive modular approximations of the function Var(G(𝒮,δ̂)) and finding a globally optimal solution to each of the resulting approximation problems. Since λ_0>0 and α>1, the parameter λ_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_𝒮𝔼[G (𝒮,δ̂)], which is 𝒮=[N].
Since we assumed at the beginning that there exists a feasible solution to the subset selection problem, the DoS algorithm is guaranteed to terminate for some finite k∈ℕ.

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

    min_𝒮⊆ [N]   Var(G(𝒮,δ̂)) - λ_k^⋆𝔼[G(𝒮,δ̂)]

where k^⋆ is the number of iterations until the convergence of the DoS algorithm. We also note that the above problem formulation is sometimes referred to as a “regularized version" of the original constrained optimization problem <cit.>. Such regularization approaches to solve the original problems are also common in portfolio management <cit.> and reinforcement learning <cit.>, among many others.



§ NUMERICAL SIMULATIONS
 
We present numerical simulation results that demonstrate the performance of the proposed algorithms on randomly generated instances of the subset selection problem. All computations are run on a 3.1-GHz desktop with 32 GB RAM using the toolbox <cit.> for the implementation of the SSP (step 5 in the DoS algorithm).



 §.§ Suboptimality Ratio on Small-Scale Instances  







We compare the suboptimality of the proposed algorithms as a function of three problem parameters: the total number N of agents, the maximum localization error γ_max:=min{γ : γ≥γ_i, for all i∈[N]}, and the expected beamforming gain threshold Γ=βΓ_max where 0<β≤1 and Γ_max:=𝔼[G([N],δ̂)] is the maximum expected beamforming gain that can be achieved by the agents.

For a given problem instance, we measure the performance of an algorithm by the suboptimality ratio (SR) of its output. Specifically, let 𝒮^⋆ be an optimal solution to the given problem instance (<ref>)-(<ref>), which, for small N, can be computed by considering all subsets 𝒮⊆[N]. Moreover, let 𝒮 be the (possibly suboptimal) output of a given algorithm. We define the SR of the algorithm on the given instance as

    SR:= Var(G(𝒮,δ̂))/Var(G(𝒮^⋆,δ̂)).

All proposed algorithms, i.e., Greedy, DLG, and DoS, have SR≥1 since their output 𝒮 satisfies 𝔼[G(𝒮,δ̂)]≥Γ.


In the first set of experiments, we investigate the relationship between the algorithms' SR, the total number N of agents, and the bound γ_max on the agents' effective localization error variances. For a given N and γ_max, a problem instance consists of {γ_i: i ∈[N]} where each γ_i is uniformly randomly selected from the interval (0,γ_max). We set the expected beamforming gain threshold as Γ=0.6Γ_max to allow the algorithms to output subsets of different sizes if it is optimal to do so. Recall that the DoS algorithm has only local optimality guarantees. Hence, the SR of the algorithm's output depends on the initialization of the SSP. Accordingly, for each problem instance, we run the DoS algorithm 10 times using different initializations and report the performance of the best output. Finally, we set λ_0=1 and α=2.

For each N∈{6,8,10} and each γ_max∈{1,2,…,20}, we generate 100 problem instances and illustrate the average SRs of all algorithms in Figure <ref> (top). As can be seen from the figure, all algorithms show near-optimal performance (SR≤ 1.3) for all (N,γ_max) pairs. Recall from Theorem <ref> that, when γ_max≤0.83, both the Greedy and DLG algorithms are guaranteed to have SR=1. Moreover, the DLG algorithm is always guaranteed to have smaller SR than the Greedy algorithm. The results shown in Figure <ref> (top) empirically witness these theoretical guarantees. Moreover, as can be seen from the figure, both the Greedy and DLG algorithms perform well (SR ≤ 1.1) even when the sufficient optimality condition, γ_max≤0.83, is violated. The DoS algorithm shows comparable performance to that of the Greedy and DLG algorithms when γ_max≥10. However, for small effective localization error variances, the Greedy and DLG algorithms perform significantly better than the DoS algorithm. Finally, note that the SR of the DoS algorithm increases with increasing total number N of agents in general. On the other hand, the SR of the Greedy and DLG algorithms, in general, remain at the same level despite the increasing total number of agents.



In the second set of experiments, we investigate the relationship between the algorithms' SRs, the total number N of agents, and the normalized threshold β=Γ/Γ_max. For given N and β, a problem instance consists of {γ_i : i∈[N]} where each γ_i is selected uniformly randomly from the interval (0,10), i.e., γ_max=10. Finally, we set λ_0=1 and α=2, and run the DoS algorithm with 10 random initializations.


For each N∈{4,6,8} and each β∈{0.1,0.2,…,1}, we generate 100 problem instances. The average SRs of the algorithms over the generated instances are shown in Figure <ref> (bottom). As can be seen from the figure, all algorithms have average SR less than 1.6 for each (N,β) pair. Recall from Theorem <ref> that, for instances in which the threshold Γ can be attained using two agents, the Greedy and DLG algorithms have SR=1. For small β values, we observe that the Greedy and DLG algorithms achieve SR=1 since, in most problem instances, the threshold is attained by using two agents. Similar to the first set of experiments (Figure <ref> (top)), we observe that the SR of the DoS algorithm increases with increasing N in general. Moreover, the performance of the DoS algorithm, in general, improves with increasing β values.

The empirical performance evaluation of the proposed algorithms on small-scale instances show that all three algorithms, Greedy, DLG, and DoS, achieve near-optimal performance (SR≤ 1.6) for a range of N, β, and γ_max values. Although the Greedy and DLG algorithms have theoretical optimality guarantees only for small γ_max and β values, they perform considerably well (SR≤ 1.1) even for large γ_max and β values. On the other hand, although the local optimality guarantee of the DoS algorithm is independent of the problem parameters, the performance of the algorithm is, in general, comparable (SR ≤ 1.1) to that of the Greedy and DLG algorithms only for large γ_max and β values.








 §.§ Performance Comparison with an SDP-Based Beamformer

We compare the performance of the proposed algorithms with a semi-definite programming-based (SDP-based) beamforming algorithm. SDP-based methods are widely used in robust beamforming literature to mitigate the degrading effects of uncertain parameters on the beam pattern <cit.>. Accordingly, for comparison, we synthesize a beamforming vector w^⋆∈ℂ^N where


    w^⋆∈min_w∈ℂ^N     ‖w‖_2^2
    subject to:     𝔼[w^HHw]≥Γ
    ∀ i∈[N],     | w_i|^2 ≤ 1.


In (<ref>)-(<ref>), the matrix H∈ℂ^N× N is H=hh^H where h^H=[h_1,h_2,…,h_N], and w^H=[w_1,w_2,…,w_N]. The constraint in (<ref>) ensures that w_i=√(P)e^jδ_i for some P≤1.

A solution to the problem in (<ref>)-(<ref>) is a beamformer w^⋆ that attains the desired threshold Γ with minimum total power while respecting the individual power constraints in (<ref>). It can be shown that a solution to the problem in (<ref>)-(<ref>) can be computed exactly by solving an SDP <cit.>. To synthesize the beamformer w^⋆, we utilized the SDP solver of the CVX toolbox <cit.> with its nominal parameters. Note that the beamformer w^⋆ minimizes the total transmit power of the antenna array while ensuring that the expected beamforming gain exceeds the desired threshold Γ. Therefore, it represents a solution to a convex relaxation of the problem

    min_𝒮⊆[N],δ∈ℂ^N      |𝒮|
    subject to      𝔼[G(𝒮,δ)]≥Γ

which is a risk-neutral version of the subset selection problem. For given w^⋆=[w_1^⋆,w_2^⋆,…, w^⋆_N], we let the corresponding optimal subset be 𝒮^⋆={i∈[N] : | w^⋆_i| >ϵ} where ϵ=10^-2.


We generate 100 subset selection problem instances by setting N=40 and selecting the error variances {γ_i : i∈ [N]} uniformly randomly from the interval (0,10), i.e., γ_max=10. For the DoS algorithm, we set λ_0=1 and α=2, and run the algorithm with 10 random initializations. We compare the performance with respect to three metrics: the average variance of the beamforming gain, the average size of the selected subset, and the average computation time.

Figure <ref> (left) shows the normalized variance of the beamforming gain, i.e., κ=Var(G(𝒮^⋆,δ))/Var(G([N],δ̂)), versus the normalized threshold β=Γ/Γ_max. In the figure, we do not plot the results of the DLG algorithm since it is almost exactly the same as the Greedy algorithm. As can be seen from the figure, the proposed discrete-optimization-based algorithms achieve similar performance to that of the SDP-based beamformer. The variance of the SDP-based beamformer is, in general, smaller than the variance of the proposed algorithms since the problem in (<ref>)-(<ref>) is a convex relaxation of the subset selection problem.

Figure <ref> (middle) demonstrates the trade-off between the normalized threshold β and the average size of the optimal subset 𝒮^⋆. The plot for the DLG algorithm is omitted in the figure since the average size of the subsets selected by the DLG algorithm is almost exactly the same as the Greedy algorithm. As can be seen from the figure, for β<1, the proposed algorithms employ strict subsets of the agent network [N] where N=40. On the other hand, the SDP-based beamformer includes all the agents to beamforming for all β>0. Combined with the results shown in Figure <ref> (left), this result suggests that the proposed algorithms achieve similar performance to that of the SDP-based approach using less number of agents. Hence, in a sense, the proposed algorithms improve the capabilities of the agent network as they allow the utilization of the agents that are not part of beamforming for other purposes in general.

Finally, Figure <ref> (right) shows the computation times for all algorithms. As can be seen from the figure, the Greedy and DLG algorithms run orders of magnitude faster than the SDP-based beamformer. On the other hand, the DoS algorithm takes longer than the SDP-based beamformer to select a subset in general. The long computation time is partially due to the fact that we run the DoS algorithm with 10 random initializations to improve its performance. We observe in our experiments that the variance of the beamforming gain for the subset selected by the DoS algorithm decreases considerably as the number of random initializations used in the DoS algorithm increases. Therefore, there is a trade-off between the computation time of the DoS algorithm and the quality of the beamformer it synthesizes.

The empirical evaluations presented above suggests that the proposed discrete optimization-based approaches have the potential to synthesize beamformers with similar performances to that of the convex optimization-based beamformers using significantly less number of agents. Furthermore, when the Greedy and DLG algorithms are employed to synthesize beamformers, the required computation time for the synthesis can be significantly reduced with respect to SDP-based approaches.



§ CONCLUSIONS

We considered a network of agents that are distributed in an environment in which they locate themselves through sensor measurements and aim to transmit a message signal to a base station. Under the assumption that the agents have Gaussian localization errors, we developed three discrete optimization-based algorithms, Greedy, Double-Loop-Greedy (DLG), and Difference-of-Submodular (DoS), each of which chooses a subset of agents to optimize the quality-of-service at the base station. Specifically, the developed algorithms either globally or locally minimize the variance of the signal-to-noise ratio (SNR) received by the base station while guaranteeing that the expected SNR is above a desired threshold. We empirically showed that the proposed algorithms achieve similar performances with a convex optimization-based algorithm while using significantly less number of agents. Moreover, the Greedy and DLG algorithms run orders of magnitude faster than the convex optimization-based algorithm.

In this work, we proposed the DoS algorithm to locally minimize the variance of the received SNR when the agents' localization errors have large variances. Although the DLG algorithm achieves comparable performances to that of the convex optimization-based algorithm with less number of agents, its computational requirements may hinder its applicability to scenarios in which the size of the agent network is large. An interesting future direction might be to develop beamforming algorithms that have optimality guarantees and run fast even on large scale systems. 





IEEEtran



§ 


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.

 For a given set {x_i∈ℝ : i∈[N] } of real numbers, the following equality holds:

    (∑_i=1^N∑_j≠ i x_i x_j)^2=    2∑_i=1^N∑_j≠ i x_i^2 x_j^2+4∑_i=1^N∑_j≠ i∑_k≠ i
      k≠ j x_i^2 x_j x_k 
        +∑_i=1^N∑_j≠ i∑_k≠ i
     k≠ j∑_l≠ i
     l≠ j
     l≠ k x_ix_jx_kx_l



Proof of Lemma <ref>: 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. Using the simple formula (a+b)^2=a^2+2ab+b^2, we obtain

    (∑_i=1^N+1∑_j≠ i x_i x_j)^2=   (∑_i=1^N∑_j≠ i x_i x_j+ 2x_N+1∑_i=1^N x_i)^2
    
    =    A_1+ A_2 + A_3

where 

    A_1=   (∑_i=1^N∑_j≠ i x_i x_j)^2,
    
        A_2=   4x_N+1(∑_i=1^N x_i)(∑_i=1^N∑_j≠ i x_i x_j),
    
        A_3=   4x^2_N+1(∑_i=1^N x_i)^2.

By the induction hypothesis, we have
A_1=B_1+B_2+B_3 where 

    B_1=   2∑_i=1^N∑_j≠ i x_i^2 x_j^2,
      
    B_2=   4∑_i=1^N∑_j≠ i∑_k≠ i
      k≠ j x_i^2 x_j x_k,
    
    B_3=   ∑_i=1^N∑_j≠ i∑_k≠ i
     k≠ j∑_l≠ i
     l≠ j
     l≠ k x_i x_j x_k x_l.

Using simple algebraic manipulations, we obtain 

    A_3+B_1=2∑_i=1^N+1∑_j≠ i x_i^2 x_j^2+4x^2_N+1∑_i=1^N∑_j≠ i x_i x_j,
       A_2=8x_N+1∑_i=1^Nx^2_i∑_j≠ i x_j +4x_N+1∑_i=1^Nx_i∑_j≠ i∑_k≠ i
     k ≠ j x_j x_k.

Note that the first term on the right hand side of (<ref>) is the first term on the right hand side of (<ref>). Let

    C_1    = B_2+4x^2_N+1∑_i=1^N∑_j≠ i x_i x_j+8x_N+1∑_i=1^Nx^2_i∑_j≠ i x_j,
    
    C_2    = B_3+4x_N+1∑_i=1^Nx_i∑_j≠ i∑_k≠ i
     k ≠ j x_j x_k.

It can be shown that C_1 and C_2 are the second and third terms in the right hand side of (<ref>). As a result, we conclude that the claim holds. 











Proof of Proposition <ref>:
By taking the expectation of the both sides of (<ref>), we obtain 𝔼[G(𝒮,δ)]


    =   𝔼[∑_i∈ S∑_j∈ Scos(Φ_i-Φ_j)] 
    
     =   𝔼[| S | +∑_i∈ S∑_j≠ icos(Φ_i-Φ_j)] 
    
     =   | S |+ ∑_i∈ S∑_j≠ i𝔼[cos(Φ_i-Φ_j)] 
    
    =   | S | +∑_i∈ S∑_j≠ i(𝔼[cos(Φ_i)cos(Φ_j) + sin(Φ_i)sin(Φ_j)] )
    
    =   | S | +∑_i∈ S∑_j≠ ie^-γ_i+γ_j/2(cos(θ_i)cos(θ_j) + sin(θ_i)sin(θ_j)) 
    
    =   | S | +∑_i∈ S∑_j≠ i√(v_i v_j)cos(θ_i-θ_j).



The equality in (<ref>) follows directly from the observation that cos(Φ_i-Φ_i)=cos(0)=1.  We obtain (<ref>) by using the linearity of expectation. Equality in (<ref>) follows from the trigonometric identity cos(x-y) = cos(x)cos(y)+sin(x)sin(y). Under the assumption that Φ_i and Φ_j are independent for i≠j, we obtain (<ref>) using the characteristic function of Gaussian random variables. Finally, the equality in (<ref>) follows from the definition v_i := e^-γ_i and the above mentioned trigonometric identity.  

Proof of Proposition <ref>: For any given 𝒮⊆[N], 𝔼[G(𝒮,δ)] is maximized if and only if (θ_i-θ_j) 2 π=0 because cos(x)≤1 for any x∈ℝ and cos(x)=1 if and only if x  2π=0. Recalling that θ_i=𝔼[η_i]+δ_i, we conclude that, for any given 𝒮⊆[N], 𝔼[G(𝒮,δ)] is maximized if and only if the condition stated in the proposition holds for all i,j∈[N]. Finally, the result 𝒮=[N] follows since | S | +∑_i∈ S∑_j≠ i√(v_i v_j) monotonically increases with the size of 𝒮. 

Proof of Proposition <ref>: We now derive the explicit form of the variance of the beamforming gain. Recall that Var(G(𝒮,δ̂))=𝔼[G(𝒮,δ̂)^2]-𝔼[G(𝒮,δ̂)]^2. We have

    𝔼[G(𝒮,δ̂)^2]
       = 𝔼[(| S| + ∑_i∈𝒮∑_j≠ icos(Φ_i-Φ_j))^2] 
       =K_1+K_2+K_3

where K_1=| S|^2, K_2=2| S |∑_i∈ S∑_j≠ i√(v_i v_j), and 

    K_3=𝔼[(∑_i∈ S∑_j≠ icos(Φ_i-Φ_j))^2].


Using the trigonometric identity 2sin(x)cos(x)=sin(2x), together with the fact that 𝔼[sinλ X]=0 for λ∈ℕ and X∼𝒩(0,σ^2), it can be shown that K_3=K_31+K_32 where

    K_31   =𝔼[(∑_i∈ S∑_j≠ icos(Φ_i)cos(Φ_j))^2],
    
    K_32   =𝔼[(∑_i∈ S∑_j≠ isin(Φ_i)sin(Φ_j))^2].


Using the characteristic function of Gaussian random variables, the identity 2cos^2(x)-1=1-2sin^2(x)=cos(2x), and Lemma <ref>, it can further be shown that


    K_31=   1/2∑_i∈ S∑_j≠ i (1+v_i^2)(1+v_j^2)      
       +2∑_i∈ S∑_j≠ i∑_k≠ i 
     k ≠ j (1+v_i^2) √(v_j v_k)      
       +∑_i∈ S∑_j≠ i∑_k≠ i
     k≠ j∑_l≠ i
     l≠ j
     l≠ k√(v_iv_jv_kv_l),       
    
     K_32=   1/2∑_i∈ S∑_j≠ i (1-v_i^2)(1-v_j^2).

As a result, 

    𝔼[G(𝒮,δ̂)^2]=   K_1+K_2+∑_i∈ S∑_j≠ i (1+v_i^2 v_j^2)
       + 2∑_i ∈ S∑_j≠ i∑_k≠ i
     k≠ j(1+v_i^2)√(v_jv_k)
       +∑_i∈ S∑_j≠ i∑_k≠ i
     k≠ j∑_l≠ i
     l≠ j
     l≠ k√(v_iv_jv_kv_l).


Similarly, for 𝔼[G(𝒮,δ)]^2, using the characteristic function of Gaussian random variable, together with Lemma <ref>, we have 

    𝔼[G(𝒮,δ̂)]^2=   (| S | +∑_i∈ S∑_j≠ i√(v_iv_j))^2
    
        =   K_1+K_2+(∑_i∈ S∑_j≠ i√(v_iv_j))^2
    
        =    K_1+K_2+2∑_i∈ S∑_j≠ i v_iv_j
       +4∑_i ∈ S∑_j≠ i∑_k≠ i
     k≠ j v_i√(v_jv_k)
          +∑_i∈ S∑_j≠ i∑_k≠ i
     k≠ j∑_l≠ i
     l≠ j
     l≠ k√(v_iv_jv_kv_l).

Since Var[G(𝒮,δ̂)]=𝔼[G(𝒮,δ̂)^2]-𝔼[G(𝒮,δ̂)]^2, we conclude the result.  


Proof of Proposition <ref>: Recall that v_i=exp(-γ_i) by definition. By taking the derivative of (<ref>) with respect to γ_k for an arbitrary k∈𝒮, we obtain

    ∂𝔼[G(𝒮,δ̂)]/∂γ_k=-∑_j∈𝒮
     j≠ kexp(-γ_k+γ_j/2)≤ 0.

The above inequality implies that decreasing the value of the maximum γ_k increases the value of the expected beamforming gain. The result then follows from the definition of V(𝒮). 

















































































Proof of Theorem <ref>:
We first show that if 𝔼[G(𝒮,δ̂)]≥Γ for 𝒮={i_1,i_2}, then a solution to the problem in (<ref>)-(<ref>) is a solution to the subset selection problem. Recall that γ_i_1≤γ_i_2≤…≤γ_i_N. Then, when 𝔼[G(𝒮,δ̂)]≥Γ for 𝒮={i_1,i_2}, the subset 𝒮 is a solution to the problem in (<ref>)-(<ref>). Now, observe from (<ref>) that among the subsets 𝒮'⊆[N] that satisfy |𝒮' |=2, the subset 𝒮={i_1,i_2} is the one that minimizes Var(G(𝒮',δ̂)). Moreover, since all the terms in the right hand side of (<ref>) are nonnegative, adding a new element to a subset 𝒮'⊆[N] that satisfy |𝒮' |=2 can only increase the value of Var(G(𝒮',δ̂)). Consequently, the subset 𝒮={i_1,i_2} is the subset that satisfies the constraint 𝔼[G(𝒮,δ̂)]≥Γ 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 (<ref>)-(<ref>) and (<ref>)-(<ref>) in terms of optimal solutions.
Without loss of generality, let

    0.83≥γ_1≥γ_2≥…≥γ_N≥ 0.
 We take the derivative of Var(G(𝒮,δ̂)) with respect to γ_1 and show that the derivative is always nonnegative. Equivalently, we show that the variance decreases as the maximum effective error variance γ_i decreases. 

Recall that v_i=exp(-γ_i). After some algebra, we obtain 

    ∂Var(G(𝒮,δ̂))/∂γ_1 =     4∑_j≠ 1 v_1v_j (1-v_1v_j)
       +4v_1(1-v_1)∑_j≠ 1∑_k≠ 1 
     k ≠ j√(v_jv_k)
       -2∑_j≠ 1(1- v_j)^2∑_k≠ 1 
     k ≠ j√(v_1v_k).

Using (<ref>), we obtain the following three inequalities which will be used to bound each term on the right hand side of (<ref>):

    1)    ∑_j∈ S 
     j≠ 1 v_1v_j (1-v_1v_j ) ≥ (| S| -1) v_1^2(1-v_1)
    2)    ∑_j∈ S 
     j≠ 1∑_k≠ 1 
     k ≠ j√(v_jv_k)≥ 2 | S | -12 v_1
    3)    ∑_j∈ S 
     j≠ 1∑_k≠ 1 
     k ≠ j(1- v_1)^2 √(v_1v_k)≤2 | S | -12 (1-v_1)^2√(v_1)

Consequently, we have

    ∂Var(G(𝒮,δ))/∂γ_1≥    4(| S| -1) v_1^2(1-v_1) 
        +8| S | -12v_1^2(1-v_1)
        -4| S | -12(1-v_1)^2√(v_1).

By rearranging the terms and using that γ_1≤0.83, we obtain

    ∂Var(G(𝒮,δ̂))/∂γ_1^2≥    2(| S| -1)√(v_1) (1-v_1)×
       [2(| S| -1)(v_1)^3/2-(| S |-2)(1-v_1)] 
    ≥    0.

Finally, since the above inequality implies that the variance can be decreased by decreasing the value of γ_1, an optimal solution to the problem in (<ref>)-(<ref>) is an optimal solution to the subset selection problem when γ_1≤0.83.  





Proof of Theorem <ref>: We first establish the supermodularity of 𝔼[G(𝒮,δ̂)]. For notational simplicity, let G(𝒮):=G(𝒮, δ̂). For X,Y⊆[N] such that X⊆Y, let X'=X∪{e} and Y'=Y∪{e} where e∈[N]\Y.
We have,

    X_diff:=𝔼[G(X')]-𝔼[G(X)]=1+2√(v_e)∑_i∈ X√(v_i),
    
         Y_diff:=𝔼[G(Y')]-𝔼[G(Y)]=1+2√(v_e)∑_i∈ Y√(v_i).

Using the fact that v_i≥ 0 and X⊆Y, we obtain

    X_diff-Y_diff=-2√(v_e)∑_i∈ Y\ X√(v_i)≤ 0.

Hence, we conclude that 𝔼[G(𝒮,δ̂)] is supermodular.


We now show the supermodularity of Var(G(𝒮,δ̂)). For X,Y⊆[N] such that X⊆Y, let X'=X∪{e} and Y'=Y∪{e} where e∈[N]\Y. Then, we have

    X_diff:   =Var(G(X'))-Var(G(X))
       =2∑_i∈ X(1-v_e v_i)^2+2(1-v_e)^2∑_i∈ X∑_j≠ i√(v_i v_j)
          + 4√(v_e)∑_i∈ X∑_j≠ i (1-v_i)^2√(v_j),
    Y_diff:   =Var(G(Y'))-Var(G(Y))
       =2∑_i∈ Y(1-v_e v_i)^2+2(1-v_e)^2∑_i∈ Y∑_j≠ i√(v_i v_j)
          + 4√(v_e)∑_i∈ Y∑_j≠ i (1-v_i)^2√(v_j).

Using the fact that v_i≥ 0 and X⊆Y, it is then straightforward to show that X_diff-Y_diff≤0. This concludes the proof. 
















[
    < g r a p h i c s >
] Erfaun Noorani is a Ph.D. student and a Clark Doctoral Fellow in the Department of Electrical and Computer Engineering, and a member of the Institute for Systems Research at University of Maryland College Park, College Park, United States. He received his Bachelor of Science degree in Electrical Engineering with a minor in Computer Science from Drexel University, Philadelphia, United States. His research concerns developing robust-resilient-adaptive Multi-agent Reinforcement Learning systems.

[
    < g r a p h i c s >
]Yagiz Savas is a Ph.D. student in the Department of Aerospace Engineering at the University of Texas at Austin. He received his B.S. degree in Mechanical Engineering from Bogazici University in 2017. He is broadly interested in designing autonomous systems that operate in uncertain environments with provable safety and performance guarantees. His research focuses on developing theory and algorithms for sequential decision making under incomplete information through novel connections between controls, information theory, and formal methods.

[
    < g r a p h i c s >
] Alec Koppel is a Research Scientist at the U.S. Army Research Laboratory in the Computational and Information Sciences Directorate since September of 2017. He completed his Master’s degree in Statistics and Doctorate in Electrical and Systems Engineering, both at the University of Pennsylvania (Penn) in August of 2017. Before coming to Penn, he completed his Master’s degree in Systems Science and Mathematics and Bachelor’s Degree in Mathematics, both at Washington University in St. Louis (WashU), Missouri. He is a recipient of the 2016 UPenn ESE Dept. Award for Exceptional Service, an awardee of the Science, Mathematics, and Research for Transformation (SMART) Scholarship, a co-author of Best Paper Finalist at the 2017 IEEE Asilomar Conference on Signals, Systems, and Computers, and a finalist for the ARL Honorable Scientist Award 2019. His research interests are in optimization and machine learning. Currently, he focuses on scalable Bayesian learning, reinforcement learning, and decentralized optimization, with an emphasis on problems arising in robotics and autonomy.


[
    < g r a p h i c s >
]
John S. Baras is a Distinguished University Professor and holds the Lockheed Martin
Chair in Systems Engineering, with the Department of Electrical and Computer
Engineering and the Institute for Systems Research (ISR), at the University of Maryland
College Park. From 1985 to 1991, he was the Founding Director of the ISR. Since 1992,
he has been the Director of the Maryland Center for Hybrid Networks (HYNET), which
he co-founded. He received the Ph.D. degree in Applied Mathematics from Harvard
University.

He is a Fellow of IEEE (Life), SIAM, AAAS, NAI, IFAC, AMS, AIAA, Member of the National
Academy of Inventors and a Foreign Member of the Royal Swedish Academy of Engineering
Sciences. Major honors include the 1980 George Axelby Award from the IEEE Control Systems
Society, the 2006 Leonard Abraham Prize from the IEEE Communications Society, the 2017
IEEE Simon Ramo Medal, the 2017 AACC Richard E. Bellman Control Heritage Award, the
2018 AIAA Aerospace Communications Award. In 2016 he was inducted in the A. J. Clark
School of Engineering Innovation Hall of Fame. In 2018 he was awarded a Doctorate Honoris
Causa by his alma mater the National Technical University of Athens, Greece.

His research interests include systems and control, optimization, communication networks,
applied mathematics, machine learning, artificial intelligence, signal processing, robotics,
computing systems, security, trust, systems biology, healthcare systems, model-based systems
engineering.


[
    < g r a p h i c s >
]Ufuk Topcu joined the Department of Aerospace Engineering at the University of Texas at Austin as an assistant professor in Fall 2015. He received his Ph.D. degree from the University of California at Berkeley in 2008. He held research positions at the University of Pennsylvania and California Institute of Technology. His research focuses on the theoretical, algorithmic and computational aspects of design and verification of autonomous systems through novel connections between formal methods, learning theory and controls.

[
    < g r a p h i c s >
] Brian M. Sadler (Life Fellow, IEEE) received the B.S. and M.S. degrees from the University of Maryland, College Park, and the PhD degree from the University of Virginia, Charlottesville, all in electrical engineering.  He is the US Army Senior Scientist for Intelligent Systems, and a Fellow of the Army Research Laboratory (ARL) in Adelphi, MD.  He has been an IEEE Communications Society Distinguished Lecturer since 2020, was an IEEE Signal Processing Society Distinguished Lecturer for 2017-2018, and general co-chair of IEEE GlobalSIP’16.  He has been an Associate Editor of the IEEE Transactions on Signal Processing, IEEE Signal Processing Letters, and EURASIP Signal Processing, and a Guest Editor for several journals including the IEEE JSTSP, the IEEE JSAC, IEEE Transactions on Robotics, the IEEE SP Magazine, Autonomous Robots, and the International Journal of Robotics Research. He received Best Paper Awards from the IEEE Signal Processing Society in 2006 and 2010, several ARL and Army R&D awards, and a 2008 Outstanding Invention of the Year Award from the University of Maryland.  He has more than 400 publications in these areas with over 17,000 citations and h-index of 56. His research interests include information science, and networked collaborative autonomous intelligent systems.



