# Greedy Selection for Heterogeneous Sensors

Kaushani Majumder, , Sibi Raj B. Pillai, Satish Mulleti K. Majumder, S. R. B.
Pillai, and S. Mulleti are with the Department of Electrical Engineering,
Indian Institute of Technology Bombay, Mumbai, 400076, India. Emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Simultaneous operation of all sensors in a large-scale sensor network is
power-consuming and computationally expensive. Hence, it is desirable to
select fewer sensors. A greedy algorithm is widely used for sensor selection
in homogeneous networks with a theoretical worst-case performance of
$(1-1/e)\approx 63\%$ of the optimal performance when optimizing submodular
metrics. For heterogeneous sensor networks (HSNs) comprising multiple sets of
sensors, most of the existing sensor selection methods optimize the
performance constrained by a budget on the total value of the selected
sensors. However, in many applications, the number of sensors to select from
each set is known apriori and solutions are not well-explored. For this
problem, we propose a joint greedy heterogeneous sensor selection algorithm.
Theoretically, we show that the worst-case performance of the proposed
algorithm is bounded to $50\%$ of the optimum for submodular cost metrics. In
the special case of HSNs with two sensor networks, the performance guarantee
can be improved to $63\%$ when the number of sensors to select from one set is
much smaller than the other. To validate our results experimentally, we
propose a submodular metric based on the frame potential measure that
considers both the correlation among the sensor measurements and their
heterogeneity. We prove theoretical bounds for the mean squared error of the
solution when this performance metric is used. We validate our results through
simulation experiments considering both linear and non-linear measurement
models corrupted by additive noise and quantization errors. Our experiments
show that the proposed algorithm results in $4-10$ dB lower error than
existing methods.

###### Index Terms:

Sensor selection, heterogeneous sensor networks, submodular maximization,
greedy algorithm, frame potential.

##  I Introduction

In many applications such as medical imaging and healthcare [1, 2, 3], seismic
processing [4, 5, 6], environmental monitoring [7, 8], power networks [9, 10],
smart homes and internet of things (IoT) networks [11, 12], etc., a large
number of sensors are deployed. In these applications, the task is often to
estimate a low-dimensional parameter vector from the sensor measurements. The
accuracy of the estimation task increases with the number of sensors or
measurements. However, this results in high power requirements and higher
communication and storage costs. To reduce operational costs, one can deploy
fewer sensors. Such fixed deployment is inefficient and non-adaptive when the
measuring fields and their noise characteristics change over time.
Alternatively, deploying a larger number of sensors and then choosing the
desired numbers based on the information available apriori is advantageous.
Activating only a few sensors at a time also leads to a considerable reduction
in operating costs.

Figure 1:  An example of an HSN comprising three subnetworks of sensors. All
the sensors observe the same phenomenon.

The sensor networks could be either homogeneous, where all the sensors have
similar accuracies, or heterogeneous. In heterogeneous sensor networks (HSNs),
multiple sets of sensors observe the same or diverse phenomena [13, 14, 8].
When an HSN measures a common phenomenon, the sensors in different sets are
characterized by their accuracies or, equivalently, their noise levels. Such
an HSN is shown in Fig. 1 [14, 8]. For example, consider an environmental
monitoring task where multiple sets of sensors with different precisions or
noise characteristics are deployed to observe a phenomenon [7, 8]. Data fusion
is performed on the measurements from all these sets in order to obtain a more
robust estimate of the phenomenon under observation. To reduce the
communication and processing cost and extend each subnetwork’s lifetime, only
a small number of observations from each set needs to be selected to achieve
the best possible estimation accuracy.

The sensor selection problem in HSNs can also be used for sensor placement
problems when the locations for the different sensor sets are predefined. For
example, in weather monitoring networks [15], high-precision weather stations
can only be placed at sparse locations over a geographical region due to their
high cost of construction, unavailability of suitable installation locations,
or high power consumption. The estimation inaccuracy induced by the low
spatial density of these high-precision sensors is compensated by deploying in
bulk, low-powered, inexpensive, low-precision sensors. The question then
arises: given probable placement locations for the different sets of sensors,
which locations should be selected to ensure the best possible accuracy in
estimating weather conditions?

In both these examples and several such practical scenarios, the task is to
maximize a performance criterion constrained by the cardinality of sensors to
be selected from each subset. In a few other applications, the sensor
selection problem is formulated with a budget constraint, assigning each
sensor a predetermined value [16, 17, 18]. However, in the examples
considered, cardinality constraints describe the problem better, resulting in
a combinatorial optimization problem for which finding the optimal solution is
computationally expensive. Even in homogeneous sensor networks, selecting a
subset of sensors to reduce the operational cost is an NP-hard problem [19].
Various methods have been proposed to find an approximate solution to this
problem, such as convex relaxation [19, 20], different heuristics [21, 22, 23,
24, 25], and a greedy selection procedure [26, 27, 28]. While theoretical
performance bounds are available for the convex relaxation methods, they are
computationally expensive. Heuristics perform well in practice, although no
theoretical guarantee is available for their performance. The greedy
algorithm, on the other hand, is computationally faster than the convex
relaxation approach while achieving a worst-case performance of
$\left(1-1/e\right)\approx 63\%$ of the optimal performance when optimizing a
submodular cost metric [26], where $e$ is Euler’s constant.

On the other hand, limited results are available for the sensor selection
problem in HSNs. In [29, 16, 30, 18, 17, 31], the authors develop a modified
greedy algorithm that maximizes the performance while satisfying a budget
constraint on the total operating cost. These methods are shown to have
performance guarantees approaching the limit $\left(1-1/e\right)$. However,
they cannot be used when the number of sensors to choose from each subset is
specified. Zhang et al. [15] proposed a cross-entropy-based stochastic
optimization method for the HSN sensor selection problem where they considered
minimizing the total operational cost of the selected sensors while achieving
a specified mean squared error (MSE). In this approach, there is an
undesirable possibility that the algorithm may choose all the available
sensors to achieve a given MSE.

Kirchner et al. [32] consider the heterogeneous sensor selection problem in
vehicle tracking applications, where sets of sensors obtain multiple snapshots
of a common phenomenon. The task is to find the optimal number of snapshots
each sensor needs to communicate with a central data processing unit, with a
budget on the maximum bandwidth allocated to the sensor. Their approach is
indeed to independently and greedily select measurements from each sensor
without considering the inter-sensor correlations. Moreover, [32] does not
reduce the number of sensors.

The problem of sensor placement in HSNs has been considered in [33, 34]. In
[33], high or low-power sensor placement is considered at each available
location based on the feedback of successful transmission. On the other hand,
[34] considers sensor placement in IoT networks, optimizing the energy
harvesting capabilities of the diverse sensors according to their channel
gains and the required accuracy of the estimation task. These methods
fundamentally differ from the sensor selection task since the type of sensor
at each location is not fixed, and moreover, the number of sensors of each
type to select is also a design parameter in [33, 34].

All the state-of-the-art methods for sensor selection in HSNs suffer from the
drawback that they do not work under cardinality constraints. In this paper,
we propose an algorithm to select the optimal sensors when the number of
sensors to be selected from each set is specified. Each sensor measures a
spatial observation induced by a set of deterministic unknown parameters,
which are to be estimated. Different noise distributions characterize each set
of sensors. In such a scenario, finding the optimal subset from each set is
considered while achieving the maximum possible performance.

The main contributions of this paper are as follows.

  * •

This work introduces a greedy algorithm for selecting sensors in HSNs under
cardinality constraints specifying the number of sensors to select from each
subset.

  * •

Theoretically, the proposed algorithm is proved to achieve at least $50\%$ of
the optimal performance when optimizing a submodular cost metric. In the
special case of HSNs comprising two sets of sensors, the theoretical
performance guarantee can be improved to $(1-1/e)$ when the number of high-
precision sensors to be chosen is less than a fraction ($10\%$ or lower) of
the low-precision ones.

  * •

A metric called weighted frame potential (WFP) is introduced, which extends
the frame potential (FP) criterion for sensor selection to HSNs. It exploits
both the correlation between the measurements and their noise characteristics.
We prove optimality guarantees for WFP and related guarantees for the mean
squared error of the solution. A submodular performance metric called weighted
frame cost (WFC) based on WFP is proposed.

  * •

Extensive experiments are conducted to evaluate the proposed algorithm for
both linear as well as non-linear measurement models. We perform small-scale
experiments to compare the performance of the proposed method with the optimal
solution obtained through an exhaustive search. Large-scale sensor selection
problems are simulated and the proposed method is compared against other
greedy-based and random approaches. Our experiments consider the effect of
both additive Gaussian noise and quantization on the measurements. Finally, as
an application of the proposed algorithm in non-linear measurement models, we
consider the problem of selecting sensors for estimating the direction-of-
arrival of plane waves emitted by multiple sources.

  * •

The small-scale experiments show that the proposed algorithm achieves near-
optimal solutions (over $99\%$ of the optimal WFC), which is better than the
theoretical performance guarantees obtained. This is similar to the
performance of existing greedy methods for sensor selection in homogeneous
networks [26].

  * •

In all the experiments conducted, the proposed method consistently achieves a
mean squared error of $4$-$10$ dB less than the existing methods.

The rest of the paper is organized as follows. In Section II, we define the
problem. The greedy algorithm for homogeneous sensor selection is presented in
Section III. The proposed algorithm is introduced in Section IV, and its
theoretical performance guarantees are derived. The WFP metric and the related
optimality bounds are presented in Section V. Various experiments and
simulation results are presented in Section VI, and Section VII concludes the
paper.

Throughout the paper, vectors (matrices) are represented as bold-faced lower-
case (upper-case) letters such as $\mathbf{a}$ ($\mathbf{A}$). We use
$\mathbf{x}\in\mathbb{R}^{N}$ ($\mathbf{x}\in\mathbb{C}^{N}$) to denote a real
(complex) $N$-dimensional vector. The norm of a vector $\mathbf{x}$ belonging
to a normed space is denoted as $\|\mathbf{x}\|$, and the inner product
between two vectors $\mathbf{x}$ and $\mathbf{y}$ is denoted as
$\langle\mathbf{x},\mathbf{y}\rangle$. In particular, $\|\mathbf{x}\|_{2}$
denotes the Euclidean norm of $\mathbf{x}$. Sets are represented by upper-case
calligraphic letters like $\mathcal{S}$, with $|\mathcal{S}|$ denoting its
cardinality and $\mathcal{P}\left(\mathcal{S}\right)$ standing for the power
set of $\mathcal{S}$. A set function
$\mathcal{C}:\mathcal{P}\left(\mathcal{S}\right)\rightarrow\mathbb{R}$ is
defined as a function that acts on any subset
$\mathcal{T}\subseteq\mathcal{S}$, producing a real-valued output. For a
positive integer $N$, we use the following representation
$\mathcal{N}=\\{1,2,\ldots,N\\}$.

##  II Problem Definition

Consider the problem of recovering an unknown vector
$\mathbf{x}\in\mathbb{C}^{K}$ from its noisy measurements obtained by $N\geq
K$ sensors. The measurements are modeled as

$\displaystyle\mathbf{y}=\mathcal{A}(\mathbf{x})+\boldsymbol{\eta},$ (1)

where $\mathbf{y}\in\mathbb{C}^{N}$is the measurement vector with its $i$-th
element representing observation from the $i$-th sensor. The measurement
operator $\mathcal{A}:\mathbb{C}^{K}\rightarrow\mathbb{C}^{N}$ is a function
of the locations of the sensors and $\boldsymbol{\eta}\in\mathbb{C}^{N}$ is an
additive noise vector. The measurement operator could be linear or non-linear.
While $\mathcal{A}(\cdot)$ is represented as a measurement matrix
$\mathbf{A}\in\mathbb{C}^{N\times K}$ in the linear case, yielding

$\displaystyle\mathbf{y}=\mathbf{A}\mathbf{x}+\boldsymbol{\eta},$ (2)

more general non-linear models also come under our purview. For example, in
the direction-of-arrival (DoA) estimation problem, $\mathcal{A}(\mathbf{x})$
is given as $\mathbf{A}(\boldsymbol{\theta})\boldsymbol{\alpha}$ where
$\boldsymbol{\theta}$ and $\boldsymbol{\alpha}$ denote angles and amplitudes
of sources. In this case, the unknown parameters to be estimated are
$\mathbf{x}=[\boldsymbol{\theta}^{\mathrm{T}}\,\,\boldsymbol{\alpha}^{\mathrm{T}}]^{\mathrm{T}}$.
Here, since $\mathbf{A}(\boldsymbol{\theta})$ is a function of the parameters
$\boldsymbol{\theta}$, the observations $\mathbf{y}$ are not linear functions
of $\boldsymbol{\theta}$.

In our work, we consider a heterogeneous sensor network comprising $L$ sets of
sensors $\mathcal{S}_{1},\mathcal{S}_{2},\ldots,\mathcal{S}_{L}$, with
$\mathcal{S}_{i}\subseteq\mathcal{N}$, for $i=1,\ldots,L$, where
$\displaystyle\bigcup_{i=1}^{L}\mathcal{S}_{i}=\mathcal{N}$ and
$\displaystyle\bigcap_{i=1}^{L}\mathcal{S}_{i}=\varnothing$. We assume that
the sensors in the different sets have varying precision. To model the
precision, we assume that the elements of the noise vector $\boldsymbol{\eta}$
corresponding to the set $\mathcal{S}_{i}$ have standard deviation
$\sigma_{i}$, $i=1,\ldots,L$. We further assume that elements of
$\boldsymbol{\eta}$ for two different sensors are independent. Hence, the
covariance matrix of the noise vector is given as
$\boldsymbol{\Sigma}=\text{diag}\left(\sigma_{1}^{2},\sigma_{2}^{2},\ldots,\sigma_{N}^{2}\right)$,
with $\sigma_{j}^{2}=\sigma_{i}^{2}$ if $j\in\mathcal{S}_{i}$, $i=1,\ldots,L$.

Our objective is to select $M_{i}$ sensors from $\mathcal{S}_{i}$, for
$i=1,\ldots,L$, such that a given accuracy metric $\mathcal{C}$ is maximized.
This is captured in the following optimization problem.

$\displaystyle\begin{aligned}
\underset{\mathcal{T}_{i}\subseteq\mathcal{S}_{i},i=1,\ldots,L}{\arg\max}\quad&\mathcal{C}\left(\bigcup_{i=1}^{L}\mathcal{T}_{i}\right),\\\
\text{subject to }&\left|\mathcal{T}_{i}\right|=M_{i},\quad\text{for
}i=1,\ldots,L\end{aligned}$ (P1)

Notice that (P1) is a combinatorial optimization problem for which no
polynomial time algorithms are known to exist. Particularly, finding the
optimal solution requires a computationally expensive search over all possible
subsets of $\mathcal{S}_{1},\ldots,\mathcal{S}_{L}$, respecting the
cardinality constraints. Instead, we propose an algorithmic solution to (P1)
using a greedy approach and characterize its worst-case performance
theoretically. In order to lay the foundations for our algorithm, we first
present the well-known greedy selection (GS) algorithm for homogeneous sensor
networks [26].

##  III Greedy Selection For Homogeneous Sensors

The problem of sensor selection has been well explored in the case of
homogeneous sensor networks composed of sensors with similar noise levels [26,
19, 20, 21, 22, 23, 24, 25]. Consider the problem of selecting $M$ out of $N$
sensors to maximize a metric $\mathcal{C}$. The corresponding optimization
problem is formulated as

$\displaystyle\underset{\mathcal{T}\subseteq\mathcal{S}}{\arg\max}\quad\mathcal{C}\left(\mathcal{T}\right),\quad\text{subject
to }\left|\mathcal{T}\right|\leq M.$ (P2)

Here $\mathcal{S}$ denotes the set from which the required subset
$\mathcal{T}$ of size at most $M$ needs to be selected.

An iterative greedy selection algorithm to solve (P2) was proposed by
Nemhauser et al. [26]. This method starts with an empty set $\mathcal{T}$. At
each iteration, the algorithm chooses a new measurement/sensor from the
remaining ones, which maximizes the performance metric $\mathcal{C}$ (or
alternatively minimizes estimation error). This step is repeated $M$-times to
select those many measurements (See Algorithm 1).

Algorithm 1 Greedy Algorithm for Homogeneous Sensor Selection

1: Initialize: $\mathcal{T}=\varnothing$

2: for $m=1\text{ to }M$ do

3: $i^{*}=\underset{i\notin\mathcal{T}}{\arg\max\text{
}}\mathcal{C}\left(\mathcal{T}\cup\\{i\\}\right)$ {Greedy Search}

4: $\mathcal{T}\leftarrow\mathcal{T}\cup\\{i^{*}\\}$

5: end for

Nemhauser et al. [26] showed that when $\mathcal{C}$ is a normalized monotone
non-decreasing submodular function, then the worst case error in the
performance of the solution given by the GS algorithm is bounded as follows,

$\displaystyle\frac{\mathcal{C}(\mathcal{T}^{\ast})}{\mathcal{C}\left(\mathcal{T}_{OPT}\right)}\geq\left(1-\left(\frac{M-1}{M}\right)^{{}^{M}}\right)\geq\left(1-\frac{1}{e}\right),$
(3)

where $\mathcal{T}^{\ast}$ is the solution found by the greedy algorithm and
$\mathcal{T}_{OPT}$ is the optimal solution of (P2). Let
$\mathcal{P}\left(\mathcal{N}\right)$ denote the power set of $\mathcal{N}$.
Then a set function
$\mathcal{C}:\mathcal{P}\left(\mathcal{N}\right)\rightarrow\mathbb{R}$ is said
to be monotone increasing if
$\mathcal{C}(\mathcal{S})\geq\mathcal{C}(\mathcal{T})$,
$\forall\mathcal{T}\subseteq\mathcal{S}\subseteq\mathcal{N}$, and is said to
be normalized if $\mathcal{C}(\varnothing)=0$, where $\varnothing$ denotes the
empty set. A submodular function is a class of set functions that follows the
property of diminishing returns, mathematically stated as
$\mathcal{C}\left(\mathcal{S}\cup\\{j\\}\right)-\mathcal{C}\left(\mathcal{S}\right)\leq\mathcal{C}\left(\mathcal{T}\cup\\{j\\}\right)-\mathcal{C}\left(\mathcal{T}\right),\forall\mathcal{T}\subseteq\mathcal{S}$.
The performance guarantee stated in (3) theoretically bounds the GS
algorithm’s worst-case performance to $\left(1-1/e\right)\approx 63\%$ of the
optimal performance.

In the next section, we propose a modified version of the greedy algorithm to
make it suitable for selecting sensors in HSNs, as described in (P1), and
analyze its performance.

##  IV A Joint Greedy Selection Algorithm for Heterogeneous Sensor Networks

The problem of sensor selection in HSNs, as stated in (P1), has not been
explored much in the literature, to the best of our knowledge. A
straightforward method is to choose $M_{i}$ sensors from $\mathcal{S}_{i}$,
for $i=1,\ldots,L$, independently using the homogeneous greedy selection
algorithm. We call this the independent greedy selection (IGS) approach.
Another technique respecting the constraints is to independently and randomly
select (IRS) the required number of sensors from each set. Last but not least,
an exhaustive search can find the optimal answer but has prohibitive
computational complexity. For comparison, let $\mathcal{T}_{OPT}$ be an
optimal set identified by exhaustive search. While it is clear that the first
two approaches quickly identify feasible solutions, it will be unraveled later
that they fail to yield good performance. Therefore, as discussed next, we
turn to a joint greedy selection (JGS) approach.

###  IV-A Proposed Joint Greedy Selection Algorithm

The JGS algorithm simultaneously considers all the sets
$\mathcal{S}_{1},\ldots,\mathcal{S}_{L},$ to circumvent the shortcomings of
the independent selection approaches discussed. The algorithm adds one sample
at a time, starting from $L$ empty sets. Specifically, we start with
$\mathcal{T}_{i}=\varnothing,i=1,\ldots,L$. Let
$\displaystyle\mathcal{T}=\bigcup_{i=1}^{L}\mathcal{T}_{i}$ denote the set of
selected sensors. Then for $|\mathcal{T}_{i}|<M_{i}$, $i=1,\ldots,L$, at every
iteration, we select a new sample $t^{\ast}\notin\mathcal{T}$ such that the
cost $\mathcal{C}(\mathcal{T}\cup\\{t^{\ast}\\})$ is maximized. After the
selection, the set $\mathcal{T}_{i}$ is updated depending on whether the
sample $t^{\ast}$ belongs to $\mathcal{S}_{i}$ for $i=1,\ldots,L$. The
iterations continue until one of the sets is exhausted, that is, until
$\left|\mathcal{T}_{i}\right|=M_{i}$ condition is satisfied for
$i\in\\{1,\ldots,L\\}$. After this point, the search is restricted to the sets
where $\left|T_{i}\right|<M_{i}$. The iterations continue until we select the
desired number of sensors from each set, exhausting one set at a time. These
steps are summarized in Algorithm 2.

It is to be noted that in JGS, there is a change in the search space when the
algorithm exhausts one of the subsets, that is, when any of
$\left|\mathcal{T}_{i}\right|=M_{i}$ for $i=1,\ldots,L$ is satisfied. In the
first few iterations, JGS searches for the next candidate sensor from the
entire set of unselected sensors. However, once one of the sets is exhausted,
the algorithm can only search over the remaining subsets. This is the step
where the algorithm essentially differs from the vanilla GS algorithm. It is
unknown beforehand at which iteration this switch occurs, and as we discuss
later, the iteration at which the switch takes place plays a key role in the
performance analysis of the JGS algorithm.

Algorithm 2 Joint Greedy Selection (JGS) Algorithm for Heterogeneous Sensor
Networks with Submodular Cost

1: Initialize:
$\displaystyle\mathcal{T}=\varnothing,\mathcal{T}_{i}=\varnothing\text{ for
}i=1,\ldots,L,\mathcal{T}^{c}=\bigcup_{i=1}^{L}\mathcal{S}_{i}$

2: for $\displaystyle m=1\text{ to }\sum_{i=1}^{L}M_{i}$ do

3:
$t^{\ast}=\underset{t\in\mathcal{T}^{c}}{\arg\max}\quad\mathcal{C}\left(T\cup\\{t\\}\right)$
{Greedy Search} {Updating the currently selected sets}

4: if $t^{\ast}\in\mathcal{S}_{i}$, for $i\in\\{1,\ldots,L\\}$ then

5: $\mathcal{T}_{i}\leftarrow\mathcal{T}_{i}\cup\\{t^{\ast}\\}$

6: end if

7: $\displaystyle\mathcal{T}=\bigcup_{i=1}^{L}\mathcal{T}_{i}$ {Updating the
set to select from}

8: $\mathcal{T}^{c}=\varnothing$

9: for $i=1,\ldots,L$ do

10: if $\left|\mathcal{T}_{i}\right|<M_{i}$ then

11:
$\mathcal{T}^{c}\leftarrow\mathcal{T}^{c}\cup\left(\mathcal{S}_{i}-\mathcal{T}_{i}\right)$

12: end if

13: end for

14: end for

###  IV-B Performance Guarantee

The proposed JGS algorithm may generate a suboptimal solution for (P1). Hence,
to evaluate the algorithm, it is essential to determine its worst-case
performance. In this section, we prove a theoretical bound for the maximum
deviation of the achieved performance from the optimal performance. For the
rest of this section, we shall assume that the cost function $\mathcal{C}$
being maximized by the algorithm is a normalized, monotone, non-decreasing
submodular function.

Our main result, summarized in the following theorem, gives a bound on the
worst-case performance of the proposed JGS algorithm in terms of the cost
achieved by an optimal set $\mathcal{T}_{OPT}$ for (P1).

######  Theorem 1.

Consider the optimization problem in (P1) where $\mathcal{C}$ is assumed to be
a normalized, monotone, non-decreasing, submodular function. Then the cost of
the final set $\mathcal{T}^{\ast}$ selected by the algorithm is bounded as

$\mathcal{C}\left(\mathcal{T}^{\ast}\right)\geq\frac{1}{2}\mathcal{C}\left(\mathcal{T}_{OPT}\right)$
(4)

The proof of this theorem is presented in Appendix B. Although Theorem 1 gives
a constant lower bound of achieving at least $50\%$ of the optimal
performance, we can show tighter bounds when the number of sets is restricted
to two sets $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$, and the number of sensors
with low noise characteristics is vastly outnumbered by the number of low-
precision sensors with high noise. This result is presented in the next
theorem.

######  Theorem 2.

Consider the optimization problem in (P1) where $\mathcal{C}$ is assumed to be
a normalized monotone, non-decreasing, submodular function. Let the JGS
algorithm at the $m_{s}$-th iteration select $M_{i}$ elements from the set
$\mathcal{S}_{i}$, for $i\in\\{1,2\\}$. Let $\mathcal{S}_{i^{\prime}}$, where
$i^{\prime}\coloneqq\\{1,2\\}\backslash\\{i\\}$, denote the set complementary
to $\mathcal{S}_{i}$. Then the cost of the final set $\mathcal{T}^{\ast}$
selected by the JGS algorithm is bounded as

$\mathcal{C}\left(\mathcal{T}^{\ast}\right)\geq\left[1-\frac{M_{i}}{M_{i^{\prime}}}\sum_{j=0}^{M_{i}+M_{i^{\prime}}-m_{s}-1}\left(1-\frac{1+M_{i}}{M_{i^{\prime}}}\right)^{j}-\right.\\\
\left.\left(1-\frac{1+M_{i}}{M_{i^{\prime}}}\right)^{M_{i}+M_{i^{\prime}}-m_{s}}\left(1-\frac{1}{M_{i}+M_{i^{\prime}}}\right)^{m_{s}}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right).\\\
$ (5)

Proof of the theorem is deferred to Appendix C.

As seen from Theorem 2, The bounds in Theorem 2 depend on $M_{1}$, $M_{2}$,
and $m_{s}$. Thus, unlike the GS algorithm for homogeneous sensor networks, we
cannot give a single number that specifies the worst-case error. Next, we
discuss how the worst-case error varies with $M_{1}$, $M_{2}$, and $m_{s}$.

###  IV-C Analysis of Performance Guarantee

We assess the theoretical bounds in (LABEL:thrm_1_1) by fixing $m_{s}$ and
varying $M_{1}$ and $M_{2}$. For the sake of discussion, we assume that
$M_{1}$ is reached first by the algorithm. Otherwise, $M_{1}$ and $M_{2}$ will
be interchanged in the discussion and the following results. With $M_{1}$
samples selected first from set $\mathcal{S}_{1}$, we have that $M_{1}\leq
m_{s}\leq M_{1}+M_{2}-1$.

Figure 2: Plot of the theoretical worst case error for varying $M_{1}$ and
$M_{2}$, when $m_{s}=M_{1}+M_{2}-1$.

Figure 2 shows the performance guarantees when $M_{1}$ and $M_{2}$ vary, with
$m_{s}=M_{1}+M_{2}-1$. We observe that the worst case performance
asymptotically approaches the value $\left(1-1/e\right)\approx 63\%$ as
$M_{1}$ gets progressively smaller than $M_{2}$, with
$\frac{M_{1}}{M_{2}}\rightarrow 0$. Specifically, we observe that for
$\frac{M_{1}}{M_{2}}=O\left(10^{-2}\right)$ the worst case performance reaches
$\approx 63\%$ of the optimal performance. For relatively larger values of
$M_{1}$ compared to $M_{2}$, such as $\frac{M_{1}}{M_{2}}\approx 0.1$, the
selected set has a performance which is at worst $55\%$ of the optimal
performance.

Figure 3: Plots of the theoretical worst case error guarantee for the proposed
algorithm, when $m_{s}$ is varied from $M_{1}$ to
$\left(M_{1}+M_{2}-1\right)$, for different values of $M_{1}$ and $M_{2}$.

Figure 3 shows the variation of the performance guarantee when $M_{1}$ and
$M_{2}$ are kept constant and $m_{s}$ is varied. As the figure shows, the
worst-case performance error for lower values of $m_{s}$ is not very
encouraging. This is due to the approximations we make in deriving the bound
and it may be improved if these approximations can be improved. However, lower
values of $m_{s}$ are less likely since this scenario implies very little
correlation among the measurements in $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$.
It is observed from Fig. 3 that the performance remains flat for lower values
of $m_{s}$ (for $m_{s}=M_{1}$ till about $50-60\%$ of $M_{1}+M_{2}$), and then
the performance increases as $m_{s}$ increases beyond this value until it
reaches $(1-1/e)$ of the optimal performance. These results imply that the
algorithm performs better when the switch in the search space occurs later in
the algorithm. From Fig. 2 and Fig. 3, we conclude that the theoretical
performance guarantee obtained by the JGS algorithm is similar to the standard
greedy method when $m_{s}$ takes higher values. Higher values of $m_{s}$ mean
that JGS utilizes the correlation information between the two subsets for more
number of steps.

This analysis shows that while the JGS algorithm is guaranteed to produce a
performance which is at worst $50\%$ of the optimum, this guarantee can be
improved to $63\%$ under the special case when there are only two sets with
the number of sensors to select from one set much smaller than the other. This
situation practically arises when the two sets are composed of expensive high-
precision sensors and easily available inexpensive low-precision sensors,
respectively. In this case, the idea is to use a small number of high-
precision sensors and compensate for the low sample density with an adequate
number of low-precision sensors.

Next, we introduce a submodular performance metric for heterogeneous networks
based on the frame potential. We obtain related performance guarantees for
widely used error metrics such as the mean squared error.

##  V Performance Metrics and Submodular Surrogates

In typical estimation tasks, MSE is employed as the performance measure.
However, it is not submodular. Hence, theoretical guarantees derived in the
previous section for greedy algorithms are not applicable. In practice,
instead of MSE, its proxies such as Cramér-Rao lower bound (CRLB)-based
(defined as the inverse of the Fisher information matrix (FIM) [35]) or frame-
potential (FP)-based [36, 37] functions are used with greedy algorithms. These
functions have desired submodularity and monotonicity properties. However, a
natural question is whether minimizing these proxies results in lower MSE.
Additionally, which proxies are better suited for the sensor selection in an
HSN? We answer these questions in this section.

Since the CRLB gives a lower bound for MSE, different submodular functions of
the CRLB matrix, such as $\text{trace}(\text{CRLB})$,
$-\log\det(\text{CRLB})$, and the largest eigenvalue
$\lambda_{\text{max}}(\text{CRLB})$ are commonly used as surrogates for MSE
[37]. In the greedy algorithms such as Algorithms 1 and 2, where sensors are
sequentially selected starting from a null set, CRLB-based functions may not
result in meaningful costs in the first few interactions. For example,
consider the linear measurements as in (2) and let $\mathbf{y}_{\mathcal{S}}$
be the subset of measurements at a given iteration. Then FIM for estimation of
$\mathbf{x}$ from $\mathbf{y}_{\mathcal{S}}$ is given as
$\mathbf{A}_{\mathcal{S}}^{T}\mathbf{A}_{\mathcal{S}}$ where
$\mathbf{A}_{\mathcal{S}}\in\mathbb{R}^{|\mathcal{S}|\times K}$ is a matrix
consisting of rows of $\mathbf{A}$ that are indexed by the set $\mathcal{S}$.
The matrix is singular if $|\mathcal{S}|<K$; hence, CRLB can not be defined.
This results in an arbitrary selection of measurements in any greedy
algorithm’s first $K-1$ iterations. Alternative cost functions such as FP are
used to avoid such scenarios, as discussed next.

An FP-based cost depends on the correlation between the measurements [36, 37],
and it does not suffer from the singularity issue. Since correlated
measurements add less information about the unknown vector to be estimated,
FP-based cost can be minimized for subset selection. Submodular cost functions
based on FP are defined for linear and non-linear homogeneous measurements in
[36] and [37], respectively, where in the latter case, it is assumed that
$\mathcal{A}$ is a differentiable function of $\mathbf{x}$. We extend these
definitions for heterogeneous measurements and introduce weighted frame
potential (WFP) as a performance metric.

In a greedy selection step, while selecting a new sensor (or measurement) from
the remaining ones, any measurement that is highly correlated with the
selected sensors or has low SNR should be given less consideration. Following
this logic, we define WFP as

$\text{WFP}\left(\mathcal{S}\right)\coloneqq\sum_{i,j\in\mathcal{S}}w_{i}w_{j}\frac{\left|\left<\nabla_{\mathbf{x}}y_{i},\nabla_{\mathbf{x}}y_{j}\right>\right|^{2}}{\|\nabla_{\mathbf{x}}y_{i}\|_{2}^{2}\|\nabla_{\mathbf{x}}y_{j}\|_{2}^{2}},$
(6)

where $\nabla_{\mathbf{x}}y_{i}$ denotes the gradient of the $i$-th
observation with respect to the parameter vector $\mathbf{x}$, and
$w_{i}\coloneqq\phi\left(\sigma_{i}\right)$ are non-negative weights dependent
on the noise variance $\sigma_{i}$ corrupting the $i$-th measurement. The
definition is an extension of the modified frame potential introduced in [37]
and applies to non-linear and linear heterogeneous measurements. In the case
of a linear measurement system $\mathbf{A}$, the WFP metric reduces to the
simpler form,

$\text{WFP}\left(\mathcal{S}\right)\coloneqq\sum_{i,j\in\mathcal{S}}w_{i}w_{j}\frac{\left|\left<\mathbf{a}_{i},\mathbf{a}_{j}\right>\right|^{2}}{\|\mathbf{a}_{i}\|_{2}^{2}\|\mathbf{a}_{j}\|_{2}^{2}},$
(7)

where $\mathbf{a}_{i}$ denotes the $i$-th row of $\mathbf{A}$.

The weighting function $\phi\left(\sigma_{i}\right)$ needs to be chosen such
that the measurements corrupted by low noise are preferred for selection. A
natural choice is $\phi\left(\sigma_{i}\right)=1/\sigma_{i}$. This is also the
weighting function used in maximum likelihood estimation techniques [35].
However, when $\sigma_{i}\approx 0$, that is when the noise affecting a
measurement is negligible, this makes the corresponding terms in WFP extremely
large. Since our aim is to minimize the correlation among samples, having
$\phi\left(\sigma_{i}\right)=1/\sigma_{i}$ essentially ensures that the
measurements with very low noise are never selected. To address this issue, we
choose $\phi\left(\sigma_{i}\right):\mathbb{R}^{+}\rightarrow[0,1]$ to be a
function that maps the noise variance to a value within $[0,1]$, such that
more weight is given to measurements with low noise. Several such functions
have been used, such as $\frac{1}{1+\sigma_{i}}$,
$\frac{1}{1+\exp\left(-\left(\sigma_{i}-\bar{\sigma}\right)\right)}$, and
$\frac{\tanh\left(\sigma_{i}-\bar{\sigma}\right)}{2}$, with $\bar{\sigma}$
representing the mean of the noise variances of all the measurements. It is
observed empirically that the sigmoid function,
$\frac{1}{1+\exp\left(-\left(\sigma_{i}-\bar{\sigma}\right)\right)}$, gives
the best performance among all the $\phi\left(\sigma_{i}\right)$ used. Hence,
we select this as the weighting function for our experiments.

Next, we define an FP-based submodular performance metric that, when
maximized, finds an approximate solution for the problem (P1). Specifically,
we define weighted frame cost (WFC) as

$\text{WFC}(\mathcal{T})\coloneqq\text{WFP}(\mathcal{N})-\text{WFP}\left(\mathcal{N}\backslash\mathcal{T}\right).$
(8)

Here, $\mathcal{N}\backslash\mathcal{T}$ denotes the set of measurements that
are not in $\mathcal{T}$. In Appendix A, we show that WFC is a normalized,
monotone, non-decreasing submodular function. In principle, the definition of
WFC is similar to the FP-based cost functions used in [36, 37]

The cost, WFC, is used as the performance metric $\mathcal{C}$ in problem (P1)
for the simulations in the following sections. It is to be noted that the
maximization of $\text{WFC}(\mathcal{T})$ results in the minimization of
$\text{WFP}(\mathcal{N}\backslash\mathcal{T})$ as is apparent from the
definition of WFC given by (8). Since our objective is to minimize the WFP of
the selected set, $\mathcal{N}\backslash\mathcal{T}$ is the set of sensors the
JGS algorithm selects with WFC as the performance metric.

###  V-A Near Optimality of the WFP

From Theorem 1, we know that the WFC of the set $\mathcal{T}^{\ast}$ of
sensors selected by the JGS algorithm is at worst $50\%$ of the optimal WFC.
Using this fact, the WFP of the solution can also be bounded, as summarized in
the next theorem.

######  Theorem 3.

If Algorithm 2 selects the set $\mathcal{N}\backslash\mathcal{T}^{\ast}$ with
WFC as the cost function, then

$\text{WFP}\left(\mathcal{T}^{\ast}\right)\leq\frac{1}{2}\left(1+\frac{\text{WFP}(\mathcal{N})}{\text{WFP}\left(\mathcal{T}_{OPT}\right)}\right)\text{WFP}\left(\mathcal{T}_{OPT}\right),$
(9)

where $\mathcal{T}_{OPT}$ is the optimal solution when WFP is minimized.

###### Proof.

From Theorem 1, we have,
$\text{WFC}\left(\mathcal{N}\backslash\mathcal{T}^{\ast}\right)\geq\frac{1}{2}\text{WFC}\left(\mathcal{N}\backslash\mathcal{T}_{OPT}\right)$.
This implies,

$\displaystyle\text{WFP}(\mathcal{N})-\text{WFP}\left(\mathcal{T}^{\ast}\right)\geq\frac{1}{2}\left(\text{WFP}(\mathcal{N})-\text{WFP}\left(\mathcal{T}_{OPT}\right)\right)$
$\displaystyle\implies$
$\displaystyle\text{WFP}\left(\mathcal{T}^{\ast}\right)\leq\frac{1}{2}\left(\text{WFP}(\mathcal{N})+\text{WFP}\left(\mathcal{T}_{OPT}\right)\right),$

and the result follows. ∎

As is evident from (9), the WFP of $\mathcal{T}^{\ast}$ is at most a factor
$\gamma\coloneqq\frac{1}{2}\left(1+\frac{\text{WFP}(\mathcal{N})}{\text{WFP}(\mathcal{T}_{OPT})}\right)$
of the optimal WFP. Since
$\text{WFP}(\mathcal{N})\geq\text{WFP}(\mathcal{T}_{OPT})$, this implies
$\gamma\geq 1$. The value of $\gamma$ depends on the value of
$\text{WFP}(\mathcal{N})/\text{WFP}(\mathcal{T}_{OPT})$. In the linear case,
when the measurements are obtained using a measurement matrix $\mathbf{A}$,
$\text{WFP}(\mathcal{N})$ can be bounded as [36],

$\frac{1}{K}\left(\sum_{i=1}^{N}w_{i}^{2}\|\mathbf{a}_{i}\|^{2}\right)^{2}\leq\text{WFP}(\mathcal{N})\leq\left(\sum_{i=1}^{N}w_{i}^{2}\|\mathbf{a}_{i}\|^{2}\right)^{2},$

where the lower bound is reached when
$\tilde{\mathbf{A}}\coloneqq\text{diag}\left(\\{w_{i}\\}_{i=1}^{N}\right)\mathbf{A}$
is a tight frame, and the upper bound is reached when $\mathbf{A}$ is a rank-
one matrix.

Thus, the JGS algorithm not only achieves near-optimal WFC but also reaches
near-optimal WFP, which we want to minimize. However, since MSE is the
performance criterion used in most estimation tasks, we next prove a
theoretical bound on the MSE achieved by the JGS algorithm when the
measurements follow a linear model.

###  V-B Near Optimality of the MSE with respect to WFP

As mentioned earlier, mean squared error is a widely used error measure to
compute the performance of estimation methods. In this section, We prove
theoretical bounds on the MSE achieved by the JGS algorithm when WFC is used
as the performance metric and the measurement model is linear.

In order to compute the approximation factor for the MSE achieved by the JGS
algorithm, we first introduce the MSE metric and the estimation method used.
For an estimate $\hat{\mathbf{x}}$ of the parameter vector $\mathbf{x}$, the
MSE can be defined as
$\text{MSE}\coloneqq\|\mathbf{x}-\hat{\mathbf{x}}\|_{2}^{2}$. In the case when
the sensing system is linear, so that $\mathcal{A}$ is a matrix $\mathbf{A}$,
for a heterogeneous system with known noise covariance matrix
$\boldsymbol{\Sigma}$ and a subset $\mathcal{T}$ of selected
$M=\sum_{i=1}^{L}M_{i}$ measurements, the minimum MSE is achieved by the
estimate

$\hat{\mathbf{x}}\coloneqq\left(\mathbf{A}_{\mathcal{T}}^{H}\boldsymbol{\Sigma}_{\mathcal{T}}^{-1}\mathbf{A}_{\mathcal{T}}\right)^{-1}\mathbf{A}_{\mathcal{T}}^{H}\boldsymbol{\Sigma}_{\mathcal{T}}^{-1}\mathbf{y}_{\mathcal{T}},$
(10)

and the corresponding MSE is given by
$\text{MSE}(\mathcal{T})=\text{Trace}\left(\left(\mathbf{A}_{\mathcal{T}}^{H}\boldsymbol{\Sigma}_{\mathcal{T}}^{-1}\mathbf{A}_{\mathcal{T}}\right)^{-1}\right)$
[38]. Here, $\mathbf{A}_{\mathcal{T}}$ (or $\mathbf{y}_{\mathcal{T}}$) denotes
the rows of $\mathbf{A}$ (or $\mathbf{y}$) indexed by the set $\mathcal{T}$.
The corresponding noise covariance matrix is defined as
$\boldsymbol{\Sigma}_{\mathcal{T}}\coloneqq\text{diag}\left(\left\\{\sigma_{i}^{2}|i\in\mathcal{T}\right\\}\right)$.
Let us define the inverse error covariance matrix of the estimate
$\hat{\mathbf{x}}$ as
$\boldsymbol{\Phi}_{\mathcal{T}}\coloneqq\left(\mathbf{A}_{\mathcal{T}}^{H}\boldsymbol{\Sigma}_{\mathcal{T}}^{-1}\mathbf{A}_{\mathcal{T}}\right)$.
Then minimizing $\text{MSE}(\mathcal{T})$ is equivalent to minimizing
$\text{Trace}(\boldsymbol{\Phi}_{\mathcal{T}}^{-1})$, or equivalently
minimizing $\sum_{i=1}^{M}1/\lambda_{i}^{\mathcal{T}}$, where
$\lambda_{i}^{\mathcal{T}}$, $i=1,\ldots,M$, are the eigenvalues of
$\boldsymbol{\Phi}_{\mathcal{T}}$.

We derive the bounds for the MSE of the estimate only for a certain class of
measurement matrices with a bounded spectrum of their corresponding
$\boldsymbol{\Phi}_{\mathcal{T}}$ matrix. This class of measurement matrices
is called $(\delta,M)$-bounded frames.

######  Definition 1.

($(\delta,M)$-Bounded Frame) [36] A matrix $\mathbf{A}\in\mathbb{C}^{N\times
K}$, with $N\geq M>K$, is said to be $(\delta,M)$-bounded if, for every
$\mathcal{T}\subseteq\mathcal{N}$ such that $|\mathcal{T}|=M$, and
corresponding noise covariance matrix $\boldsymbol{\Sigma}_{\mathcal{T}}$, the
corresponding matrix $\boldsymbol{\Phi}_{\mathcal{T}}$ has a bounded spectrum

$d-\delta\leq\lambda_{i}^{\mathcal{T}}\leq d+\delta,$ (11)

for all $1\leq i\leq M$, $\delta>0$, and where
$d=\frac{1}{N}\sum_{i\in\mathcal{N}}\|\mathbf{a}_{i}\|^{2}$ is the average
squared norm of the rows of $\mathbf{A}$.

A $(\delta,M)$-bounded frame is reminiscent of the restricted isometry
property in compressed sensing [39]. For a $(\delta,M)$-bounded class of
measurement matrices, we can state the following bounds for the MSE of the
estimate.

######  Theorem 4.

If $\mathbf{A}$ is a $(\delta,M)$-bounded frame, and Algorithm 2 selects the
set $\mathcal{N}\backslash\mathcal{T}^{\ast}$ with WFC as the cost function,
then

$\text{MSE}\left(\mathcal{T}^{\ast}\right)\leq\zeta\text{MSE}_{OPT},$ (12)

where $\text{MSE}_{OPT}$ is the optimal MSE that can be achieved,
$\zeta=\gamma\kappa$ where $\gamma$ is the approximation factor in (9) and
$\kappa=\frac{(d+\delta)^{2}}{(d-\delta)^{2}}\frac{\alpha_{\max}}{\alpha_{\min}}$,
with
$\alpha_{\max}=\underset{\mathcal{T}\subset\mathcal{N},|\mathcal{T}|=M}{\max}\quad\sum_{i\in\mathcal{T}}w_{i}^{2}\|\mathbf{a}_{i}\|^{2}$,
and
$\alpha_{\min}=\underset{\mathcal{T}\subset\mathcal{N},|\mathcal{T}|=M}{\min}\quad\sum_{i\in\mathcal{T}}w_{i}^{2}\|\mathbf{a}_{i}\|^{2}$.

###### Proof.

We know that,
$\text{WFP}(\mathcal{T})=\text{Trace}\left(\boldsymbol{\Phi}_{\mathcal{T}}^{H}\mathbf{W}_{\mathcal{T}}^{H}\mathbf{W}_{\mathcal{T}}\boldsymbol{\Phi}_{\mathcal{T}}\right)=\sum_{j=1}^{M}\left|w_{j}\lambda_{j}^{\mathcal{T}}\right|^{2}$,
where
$W_{\mathcal{T}}=\text{diag}\left(\left\\{\sigma_{i}w_{i}|i\in\mathcal{T}\right\\}\right)$
and $w_{j}$ is a linear combination of the elements in
$\left\\{\sigma_{i}w_{i}|i\in\mathcal{T}\right\\}$. Using the relationship
[40] between the arithmetic mean, harmonic mean, and the standard deviation of
the $\left\\{\lambda_{i}^{\mathcal{T}}\right\\}_{i=1}^{M}$, and the fact that
$w_{i}\leq 1$, for $1\leq i\leq N$, we get,

$\frac{M^{2}}{\alpha_{\max}}\frac{\text{WFP}(\mathcal{T})}{\lambda_{\max}^{2}}\leq\text{MSE}(\mathcal{T})\leq\frac{M^{2}}{\alpha_{\min}}\frac{\text{WFP}(\mathcal{T})}{\lambda_{\min}^{2}},$
(13)

where $\lambda_{\max}$ and $\lambda_{\min}$ are the maximum and minimum
eigenvalues of $\boldsymbol{\Phi}_{\mathcal{T}}$ respectively. This implies
that,

$\text{MSE}\left(\mathcal{T}^{\ast}\right)\leq\frac{M^{2}}{\alpha_{\min}}\frac{\gamma\text{WFP}\left(\mathcal{T}_{OPT}\right)}{(d-\delta)^{2}},$
(14)

and,

$\text{MSE}_{OPT}\geq\frac{M^{2}}{\alpha_{\max}}\frac{\text{WFP}\left(\mathcal{T}_{OPT}\right)}{(d+\delta)^{2}},$
(15)

Combining (14) and (15), we get (12). ∎

The proof of Theorem 4 follows an approach similar to the one used in [36,
Theorem 3] where $\text{FP}(\mathcal{T})$ is used instead of
$\text{WFP}(\mathcal{T})$. Note that $\text{FP}(\mathcal{T})$ is a function of
$\boldsymbol{\Phi}_{\mathcal{T}}$ and hence its eigenvalues. On the other
hand, $\text{WFP}(\mathcal{T})$ is a function of
$\mathbf{W}_{\mathcal{T}}\boldsymbol{\Phi}_{\mathcal{T}}$, which is not a
function of the eigenvalues of $\boldsymbol{\Phi}_{\mathcal{T}}$. Thus, the
major challenge in deriving (13).

A bound on the MSE has also been obtained in homogeneous sensor selection by
exploiting its weak submodularity property and using a randomized greedy
algorithm [28]. This bound depends on the curvature [28, Definition 3] of the
MSE. Such results can be extended to the heterogeneous setting but are not
explored in this work due to space constraints. Instead, from Theorem 4, we
can conclude that the MSE of the solution is bounded compared to the optimal
MSE since the WFP achieved is bounded with respect to the optimal WFP, that
is, $\gamma$ is bounded.

In the next section, we experimentally validate our results for both linear
and non-linear measurement models.

##  VI Experiments and Results

This section presents a detailed analysis of the proposed algorithm through
simulations for linear and nonlinear measurement models. The results are
compared with different methods such as greedy selection, random selection,
independent greedy selection, and independent random selection (cf. Table I
for the list of methods and see Section IV for details). We apply an
exhaustive search to find an optimal solution for a small-scale problem. The
methods are compared in terms of normalized mean-squared error measured as

$\displaystyle\text{MSE}=10\log_{10}\left(\frac{\|\mathbf{x}-\mathbf{\hat{x}}\|^{2}}{\|\mathbf{x}\|^{2}}\right),$
(16)

where $\mathbf{\hat{x}}$ is an estimate of $\mathbf{x}$ given by (10).

TABLE I: Different methods used for comparing the results

OPT Optimal Solution (Exhaustive Search) JGS Joint Greedy Selection Algorithm
GS Greedy Selection Algorithm IGS Independent Greedy Selection Algorithm IRS
Independent Random Selection Algorithm RS Random Selection Algorithm

###  VI-A Linear Measurement Model

We first present simulation results when the measurement model is linear in
nature as in (2). In the experiments, $\mathbf{A}$ is a subsampled discrete
cosine transform (DCT) matrix obtained by randomly selecting $K$ columns from
a $N\times N$ DCT matrix. The entries of the parameter vector
$\mathbf{x}\in\mathbb{R}^{K}$ are independent and identically distributed
(i.i.d.) zero-mean Gaussian random variables with variance 25. For the
additive noise model in (2), the $L$ noise variances are specified in terms of
the SNRs as

$\text{SNR}_{i}\coloneqq\frac{1}{N_{i}\sigma_{i}^{2}}\sum_{j\in\mathcal{S}_{i}}\left([\mathcal{A}(\mathbf{x})]_{j}\right)^{2},\quad\text{for
}i=1,\ldots,L,$ (17)

where $[\mathcal{A}(\mathbf{x})]_{j}$ is the noise-free measurement at the
$j$-th sensor. MSEs are averaged over $1000$ Monte-Carlo iterations for each
set of SNRs. For each Monte Carlo iteration, $\mathbf{x}$, $\mathbf{A}$, and
$\text{SNR}_{i}$ are kept fixed, while the noise covariance matrix
$\boldsymbol{\Sigma}$ is changed by randomly choosing the locations of the
$N_{i}$ sensors in each set $\mathcal{S}_{i}$ out of the total $N$ possible
locations.

Figure 4:  Small-scale problem with linear measurements in additive noise:
Comparison of MSEs achieved by the different algorithms. Parameters: $L=3$,
$M_{1}=3$, $M_{2}=5$, $M_{3}=2$, $N_{1}=5$, $N_{2}=10$, $N_{3}=5$, $K=5$,
$\text{SNR}_{1}=40$ dB, $\text{SNR}_{2}=\text{SNR}_{\min}$, and
$\text{SNR}_{3}=\left(\text{SNR}_{1}+\text{SNR}_{2}\right)/2$. The JGS has
lower MSE than IGS, IRS, and RS by $5$-$8$ dB, and higher MSE than GS and OPT
by $0.2$-$2$ dB.

For a small-scale problem, the performances of the different algorithms
mentioned in Table I are compared with the optimal solution
$\mathcal{T}_{OPT}$ obtained through an exhaustive search. In this problem,
the goal is to select $M_{1}=3$ sensors from $N_{1}=5$ sensors, $M_{2}=5$ out
of $N_{2}=10$ sensors, and $M_{3}=2$ sensors from $N_{3}=5$ sensors for $K=5$.
We fix $\text{SNR}_{1}=40$ dB and vary $\text{SNR}_{2}$ from $0$ dB to $35$
dB. $\text{SNR}_{3}$ is chosen as the average of $\text{SNR}_{1}$ and
$\text{SNR}_{2}$. The MSEs of different methods are shown in Fig. 4. We
observe that compared to IGS and the random selection methods (RS and IRS), GS
and the proposed JGS method have $5$-$8$ dB lower error. Among the performance
metrics used, MSE as an objective function gives $0.5-2.5$ dB lower MSE as
compared to the WFC metric. This shows that JGS performs equally well with
non-submodular metrics, although no theoretical guarantees are provided for
the same. GS results in $0.5-2$ dB lower error among GS and JGS methods. This
is intuitively reasonable since the heterogeneous sensor selection problem is
more constrained than the homogeneous sensor selection problem. Specifically,
by applying the GS algorithm, we can select $M$ measurements from $N$
measurements but can not ensure that out of the selected sensors, $M_{1}$,
$M_{2}$ and $M_{3}$ are selected from the sets $\mathcal{S}_{1}$,
$\mathcal{S}_{2}$ and $\mathcal{S}_{3}$ respectively. As the difference
between $\text{SNR}_{1}$ and $\text{SNR}_{2}$ decreases, the difference
between the performances of GS and JGS reduces as the sets become more
homogeneous in nature. The optimal solution gives an MSE about $0.2-0.5$ dB
less than that JGS achieves. Thus, the proposed algorithm achieves near-
optimal performance.

Figure 5: Comparison of WFCs of JGS, IGS, and IRS with respect to the optimal
performance when $\text{SNR}_{2}=\text{SNR}_{\min}=0,5,30,35$ dB. Parameters:
$M_{1}=3$, $M_{2}=5$, $M_{3}=2$, $N_{1}=5$, $N_{2}=10$, $N_{3}=5$, and $K=5$.
$\text{SNR}_{1}=40$ dB and
$\text{SNR}_{3}=\left(\text{SNR}_{1}+\text{SNR}_{2}\right)/2$. JGS gives near-
optimal WFC, while the WFC of IGS and IRS are comparatively lower.

While simulating the small-scale problem, we also take the opportunity to
verify the weighted frame cost achieved by JGS, IGS, and IRS as compared to
the optimal WFC. Figure 5 shows the WFCs for $\text{SNR}_{1}=40$ dB and
$\text{SNR}_{2}=0$ dB, $5$ dB, $30$ dB, and $35$ dB. We observe that the
solution sets obtained by the JGS algorithm achieve performances equivalent to
the optimal. In comparison, IGS and IRS produce lower WFCs. This experiment
shows that, in practice, the proposed JGS algorithm achieves near-optimal
performance. Figure 4 and Fig. 5 show that MSE and WFC are inversely
correlated with each other, in the sense that they follow inverse trends. A
lower value of WFC indicates a higher MSE.

Figure 6: Large-scale problem with linear measurements in additive noise:
Comparison of MSEs achieved by the different algorithms. Parameters:
$M_{i}=\\{10,10,10,60,10\\}$, $N_{i}=\\{25,25,25,100,25\\}$,
$\text{SNR}_{1}=40$ dB, $\text{SNR}_{5}=\text{SNR}_{\text{Min}}$, and
$\text{SNR}_{2}$, $\text{SNR}_{3}$ and $\text{SNR}_{4}$ are equally spaced
between $\text{SNR}_{1}$ and $\text{SNR}_{5}$. JGS has lower MSE than IGS,
IRS, and RS by $4$-$8$ dB, and higher MSE than GS by $0.5$-$1.5$ dB.

In the next experiment, we focused on a large-scale problem with
$M_{i}=\\{10,10,10,60,10\\}$, $N_{i}=\\{25,25,25,100,25\\}$, for
$i=1,\ldots,5$, and $K=30$. Due to the size of the problem, an exhaustive
search could not be applied. $\text{SNR}_{1}$ is kept fixed at $40$ dB, while
$\text{SNR}_{5}$ is varied from $0-35$ dB. $\text{SNR}_{2}$, $\text{SNR}_{3}$
and $\text{SNR}_{4}$ are chosen to be uniformly spaced between
$\text{SNR}_{1}$ and $\text{SNR}_{5}$. The MSEs for the rest of the methods
are compared in Fig. 6. We observe that the JGS approach gives $4$-$8$ dB
lower error than the IGS, RS, and IRS methods for different noise levels.

Figure 7: Large-scale problem with quantized linear measurements: Comparison
of MSEs achieved by the different algorithms. Parameters:
$M_{i}=\\{10,10,10,60,10\\}$, $N_{i}=\\{25,25,25,100,25\\}$, for
$i=1,\ldots,5$, $K=30$, $Q_{1}=16$ bits, and $Q_{5}=Q_{\min}$. $Q_{2}$,
$Q_{3}$ and $Q_{4}$ are chosen to lie between $Q_{1}$ and $Q_{5}$. JGS has
lower MSE than IGS, IRS, and RS by $3-8$ dB, and higher MSE than GS by
$0.5-2.5$ dB.

Next, we consider the large-scale problem as earlier, but instead of adding
two levels of noise, we consider quantizing the measurements with a coarse and
a fine quantizer. The simulation settings consider the practical scenario
where high-precision and low-precision sensors may also be characterized by
the quantization levels of their analog-to-digital converters (ADCs). Although
quantization error is often modeled as random additive noise, the operation is
non-linear. In this experiment, the sensors in the set $\mathcal{S}_{1}$ are
quantized with $Q_{1}=16$ bits, while the sensors in set $\mathcal{S}_{5}$ are
quantized with $Q_{5}=Q_{\min}$ bits, where $Q_{\min}$ varies from $1-12$
bits. $Q_{2}$, $Q_{3}$ and $Q_{4}$ are chosen to be uniformly spaced integers
within the range $\left(Q_{\min},16\right)$. Figure 7 shows the results of
this experiment of estimating the parameter vector $\mathbf{x}$ from its
quantized linear measurements. As in the previous cases, JGS gives lower MSE
than random and independent greedy methods by $3-8$ dB.

(a) Small-scale problem

(b) Large-scale problem

Figure 8: Comparison of MSEs of different algorithms for varying $\mathbf{x}$:
(a) Parameters: $L=3$, $M_{i}=\\{3,5,2\\}$, $N_{i}=\\{5,10,5\\}$, for
$i=1,2,3$, $K=5$, $\sigma_{{}_{1}}=10^{-4}$, and
$\sigma_{{}_{2}}=\sigma_{\min}$. The noise variance of $\mathcal{S}_{3}$ is
uniformly spaced between $\sigma_{{}_{1}}$ and $\sigma_{{}_{2}}$. JGS has
lower MSE than IGS, IRS, and RS by $8$-$9$ dB and higher MSE than GS and OPT
by $0.5$-$1.5$ dB. (b) Parameters: $L=5$, $M_{i}=\\{10,10,10,60,10\\}$,
$N_{i}=\\{25,25,25,100,25\\}$, for $i=1,\ldots,5$, $K=30$,
$\sigma_{{}_{1}}=10^{-4}$, and $\sigma_{{}_{5}}=\sigma_{\min}$. The noise
variances of $\mathcal{S}_{2}$, $\mathcal{S}_{3}$ and $\mathcal{S}_{4}$ are
uniformly spaced between $\sigma_{{}_{1}}$ and $\sigma_{{}_{5}}$. JGS has
lower MSE than IGS, IRS, and RS by $4$-$9$ dB, and higher MSE than GS by
$1$-$1.5$ dB.

In the previous experiments, the results are obtained for a fixed
$\mathbf{x}$, while the noise covariance matrix $\boldsymbol{\Sigma}$ and the
measurement noise at each Monte Carlo trial is changed. In the following
experiment, we compare the algorithms for different $\mathbf{x}$ realizations
where $\boldsymbol{\Sigma}$ is fixed. In this case, the measurements are
corrupted by additive zero-mean Gaussian noise. The noise variances for
$\mathcal{S}_{1}$ and $\mathcal{S}_{5}$ are chosen as $\sigma_{1}=10^{-4}$ and
$\sigma_{5}=\sigma_{\min}$, with $\sigma_{\min}$ varying from $3\times
10^{-4}$ to $3$. The noise variances of $\mathcal{S}_{2}$, $\mathcal{S}_{3}$
and $\mathcal{S}_{4}$ are chosen to be uniformly spaced between $\sigma_{1}$
and $\sigma_{5}$. The average MSE is calculated over $1000$ Monte Carlo trials
where in each trial, entries of $\mathbf{x}$ are chosen from an i.i.d. uniform
distribution selected from the range $[-1,1]$. This ensures that the noise-
free measurements are bounded, thus making the SNR values of the two sets
finite. Comparison of average MSEs for different methods are presented in Fig.
8 for both small- and large-scale problems with the values of $M_{i}$,
$N_{i}$, for $i=1,\ldots,L$, and $K$ as used in the previous experiments. It
is observed that JGS performs better than IGS, RS, and IRS by $4$-$9$ dB,
while GS outperforms JGS by about $0.5$-$1.5$ dB. These results show that the
set of sensors chosen by the proposed JGS algorithm can be used to estimate
the underlying parameter vector $\mathbf{x}$ coming from a given distribution
as long as the measurement matrix $\mathbf{A}$ and the noise characteristics
given by $\boldsymbol{\Sigma}$ remain the same.

###  VI-B Non-linear Measurement Model

To compare the methods for non-linear measurement models, we consider the
direction of arrival (DoA) estimation problem. In this model, we assume that
there are $K$ far-field sources transmitting from $K$ different directions
$\boldsymbol{\theta}=[\theta_{1},\theta_{2},\ldots,\theta_{K}]\in\mathbb{R}^{K}$.
The receiving antenna array is composed of two different sets of sensors with
different noise characteristics. The problem is then to select the best set of
$M_{1}$ high-precision sensors and $M_{2}$ low-precision sensors from the
linear sensor array so that the MSE of the estimated DoA is minimized. The
measurements are related to the directions as

$\mathbf{y}=\mathbf{A}\left(\boldsymbol{\theta}\right)\boldsymbol{\alpha}+\boldsymbol{\eta}\in\mathbb{C}^{N},$
(18)

where $\mathbf{A}\left(\boldsymbol{\theta}\right)$ is the array sensing matrix
whose $(nk)$-th entry is
$e^{-j2\frac{\pi}{\lambda}d_{n}\sin\left(\theta_{k}\right)}$, for
$k=1,\ldots,K$, $n=1,\ldots,N$, where $d_{n}$ denotes the location of the
sensors measured from a reference sensor taken at the origin, and $\lambda$ is
the wavelength of the transmitted waves. The vector
$\boldsymbol{\alpha}=[\alpha_{1},\ldots,\alpha_{K}]^{T}\in\mathbb{R}^{K}$
consists of the amplitudes of the waveform received from the $K$ sources. The
vector $\boldsymbol{\eta}$ represents the additive noise in the measurements.
The goal is to select $M_{1}$ high-precision sensors and $M_{2}$ low-precision
sensors from the given sensor array, such that the error in the estimation of
$\boldsymbol{\theta}$ and $\boldsymbol{\alpha}$ is minimized.

Figure 9: Large-scale problem with non-linear measurements (DoA estimation):
Comparison of MSEs achieved by the different algorithms. Parameters: $L=5$,
$M_{i}=\\{10,10,10,60,10\\}$, $N_{i}=\\{25,25,25,100,25\\}$, for
$i=1,\ldots,5$, $K=30$, $\text{SNR}_{1}=40$ dB,
$\text{SNR}_{5}=\text{SNR}_{\min}$, and $\text{SNR}_{2}$, $\text{SNR}_{3}$ and
$\text{SNR}_{4}$ are equally spaced between $\text{SNR}_{1}$ and
$\text{SNR}_{5}$. JGS has lower MSE than IGS, IRS, and RS by $5$-$15$ dB, and
higher MSE than GS by $0.5$-$1$ dB.

In these experiments, simulations are performed to select
$M_{i}=\\{10,10,10,60,10\\}$ sensors out of $N_{i}=\\{25,25,25,100,25\\}$
sensors, for $i=1,\ldots,5$, for estimating the directions and amplitudes of
$15$ sources by using MUSIC algorithm [41, 42]. Thus, the number of parameters
to estimate is $K=30$. The simulations are performed with the sources
transmitting at $77$-GHz, which corresponds to $\lambda=4$ mm. The sensor
locations $d_{n}$, $n=1,\ldots,N$ are chosen uniformly at random within the
interval $[0,1]$. In this experiment, we set $\text{SNR}_{1}=40$ dB, and
$\text{SNR}_{5}$ being varied. $\text{SNR}_{2}$, $\text{SNR}_{3}$ and
$\text{SNR}_{4}$ are uniformly spaced between $\text{SNR}_{1}$ and
$\text{SNR}_{5}$. The entries of $\boldsymbol{\theta}$ are chosen uniformly at
random from the interval $[-\pi,\pi]$, and entries of $\boldsymbol{\alpha}$
are i.i.d. Gaussian random variables with zero mean and variance 25. Figure 9
shows the results of this experiment. As in the linear cases, the algorithm is
shown to perform almost as well as GS ($0.5$-$1$ dB worse) even when the
measurement model is non-linear and vastly outperforms the random selection
methods and the IGS method (by $5$-$15$ dB).

In conclusion, the above experiments show that the proposed JGS algorithm
gives a near-optimal performance; the MSE it achieves is much lower than
random solutions and independent greedy solutions for both linear and non-
linear measurement models. Being a less-constrained problem, GS gives a
slightly lower MSE than JGS.

##  VII Conclusion

In this work, we have considered the problem of sensor selection in
heterogeneous sensor networks when the number of sensors to choose from each
subset is specified as a cardinality constraint. We proposed a joint greedy
algorithm to select the sensors from the different subnetworks. We proved
theoretically that the worst-case performance of the JGS algorithm is $50\%$
of the optimal performance. In the special case when the HSN comprises two
subnetworks, asymptotically, it is seen that the worst-case error reaches
$(1-1/e)\approx 63\%$ of the optimal performance when $M_{1}/M_{2}\ll 1$.

We also showed using simulations that the algorithm works well in practice and
performs better than the predictions of the worst-case error bound. The small-
scale experiments show that JGS gives a near-optimal solution. Both the small-
scale and large-scale network simulations show that JGS gives lower MSE than
random selection methods and IGS by $4$-$10$ dB in linear and non-linear
measurement systems. The proposed algorithm thus can select sensors well in
heterogeneous sensing environments.

##  Appendix A Submodularity of WFC

The function WFC as given by (8) is normalized since
$\text{WFC}(\varnothing)=\text{WFP}(\mathcal{N})-\text{WFP}(\mathcal{N})=0$.

Let $\mathcal{S}_{1}\subset\mathcal{S}_{2}\subset\mathcal{N}$. Then,

$\displaystyle\text{WFC}(\mathcal{S}_{2})$
$\displaystyle-\text{WFC}(\mathcal{S}_{1})=\text{WFP}(\mathcal{N}\backslash\mathcal{S}_{1})-\text{WFP}(\mathcal{N}\backslash\mathcal{S}_{2})$
(19)
$\displaystyle=\sum_{i\in\mathcal{S}_{2}\backslash\mathcal{S}_{1}}\sum_{j\in\mathcal{N}\backslash\mathcal{S}_{1}}w_{i}w_{j}\frac{\left|\left<\nabla_{\mathbf{x}}y_{i},\nabla_{\mathbf{x}}y_{j}\right>\right|^{2}}{\|\nabla_{\mathbf{x}}y_{i}\|_{2}^{2}\|\nabla_{\mathbf{x}}y_{j}\|_{2}^{2}}\geq
0,$ (20)

since $w_{i}\geq 0$ for all $i\in\mathcal{N}$. This shows that WFC is a
monotone, non-decreasing function.

Finally, with $\mathcal{S}_{1}\subset\mathcal{S}_{2}\subset\mathcal{N}$ and
$\rho_{j}(\mathcal{S})$ defining the incremental cost of adding the element
$j$ to the set $\mathcal{S}$ with WFC as the cost function, the submodularity
of WFC is proved.

$\displaystyle\rho_{j}$
$\displaystyle(\mathcal{S}_{1})-\rho_{j}(\mathcal{S}_{2})$
$\displaystyle=\sum_{i\in\mathcal{N}\backslash\mathcal{S}_{1}}w_{i}w_{j}\frac{\left|\left<\nabla_{\mathbf{x}}y_{i},\nabla_{\mathbf{x}}y_{j}\right>\right|^{2}}{\|\nabla_{\mathbf{x}}y_{i}\|_{2}^{2}\|\nabla_{\mathbf{x}}y_{j}\|_{2}^{2}}$
$\displaystyle\hskip
56.9055pt-\sum_{i\in\mathcal{N}\backslash\mathcal{S}_{2}}w_{i}w_{j}\frac{\left|\left<\nabla_{\mathbf{x}}y_{i},\nabla_{\mathbf{x}}y_{j}\right>\right|^{2}}{\|\nabla_{\mathbf{x}}y_{i}\|_{2}^{2}\|\nabla_{\mathbf{x}}y_{j}\|_{2}^{2}}$
$\displaystyle=\sum_{i\in\mathcal{S}_{2}\backslash\mathcal{S}_{1}}w_{i}w_{j}\frac{\left|\left<\nabla_{\mathbf{x}}y_{i},\nabla_{\mathbf{x}}y_{j}\right>\right|^{2}}{\|\nabla_{\mathbf{x}}y_{i}\|_{2}^{2}\|\nabla_{\mathbf{x}}y_{j}\|_{2}^{2}}\geq
0.$

##  Appendix B Proof of Theorem 1

This proof is based on ideas from guarantees derived for submodular
maximization under matroid constraints [43]. We denote by
$M=\sum_{i=1}^{L}M_{i}$ the total number of sensors to be selected. Let
$\mathcal{T}^{m}$ denote the set selected by the JGS algorithm till iteration
$m$, with the sensor $t^{m}$ added at the $m$-th iteration. We define
$\rho_{t}\left(\mathcal{T}^{m}\right)\coloneqq\mathcal{C}\left(\mathcal{T}^{m}\cup
t\right)-\mathcal{C}\left(\mathcal{T}^{m}\right)$ to be the incremental cost
of adding the element $t$ to the set $\mathcal{T}^{m}$. Similarly,
$\rho_{{}_{\mathcal{R}}}\left(\mathcal{T}\right)\coloneqq\mathcal{C}\left(\mathcal{T}\cup\mathcal{R}\right)-\mathcal{C}\left(\mathcal{T}\right)$
is the incremental cost of adding the set $\mathcal{R}$ to the set
$\mathcal{T}$. This incremental cost
$\rho_{{}_{\mathcal{R}}}\left(\mathcal{T}\right)$ is a submodular function as
shown next.

$\displaystyle\rho_{{}_{\mathcal{P}}}\left(\mathcal{T}\right)$
$\displaystyle+\rho_{{}_{\mathcal{R}}}\left(\mathcal{T}\right)$
$\displaystyle=\mathcal{C}\left(\mathcal{T}\cup\mathcal{P}\right)-\mathcal{C}\left(\mathcal{T}\right)+\mathcal{C}\left(\mathcal{T}\cup\mathcal{R}\right)-\mathcal{C}\left(\mathcal{T}\right)$
$\displaystyle\geq\mathcal{C}\left(\left(\mathcal{P}\cup\mathcal{R}\right)\cup\mathcal{T}\right)+\mathcal{C}\left(\left(\mathcal{P}\cap\mathcal{R}\right)\cup\mathcal{T}\right)-2\mathcal{C}\left(\mathcal{T}\right)$
$\displaystyle=\rho_{{}_{\mathcal{P}\cup\mathcal{R}}}\left(\mathcal{T}\right)+\rho_{{}_{\mathcal{P}\cap\mathcal{R}}}\left(\mathcal{T}\right),$
(21)

where the inequality is followed by the submodularity of $\mathcal{C}$.

The optimal set $\mathcal{T}_{OPT}$ can be divided into its subsets
$\mathcal{T}_{OPT,i}\coloneqq\mathcal{T}_{OPT}\cap\mathcal{S}_{i}$ for
$i=1,\ldots,L$, where $\mathcal{T}_{OPT,i}$ denotes the subset of the optimal
set selected from $\mathcal{S}_{i}$. Since $\mathcal{T}_{OPT}$ is a feasible
solution of (P1), $\left|\mathcal{T}_{OPT,i}\right|=M_{i}$ for $i=1,\ldots,L$.
Similarly, $\left|\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right|=M_{i}$ since
$\mathcal{T}^{\ast}$ is also a feasible solution of (P1). A one-to-one mapping
can then be defined from the set $\mathcal{T}^{\ast}\cap\mathcal{S}_{i}$ to
the set $\mathcal{T}_{OPT,i}$ for each $i\in\\{1,\ldots,L\\}$ as follows. All
elements in
$\left(\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right)\cap\mathcal{T}_{OPT,i}$,
are mapped to themselves. A random bijection is constructed from the elements
in
$\left(\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right)\backslash\mathcal{T}_{OPT,i}$
to those in
$\mathcal{T}_{OPT,i}\backslash\left(\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right)$.
As a result, let this bijection map the element
$v_{j}^{i}\in\left(\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right)$ to the
element $o_{j}^{i}\in\mathcal{T}_{OPT,i}$, for $j=1,\ldots,M_{i}$.

Let $\mathcal{V}_{i}\subset\\{1,\ldots,M\\}$, for $i=1,\ldots,L$, denote the
index set of the iterations in which the JGS algorithm selects the sensor from
$\mathcal{S}_{i}$. Specifically, $m\in\mathcal{V}_{i}$ if at the $m$-th
iteration of Algorithm 2, the sensor is selected from $\mathcal{S}_{i}$. Thus,
we have, $\left|\mathcal{V}_{i}\right|=M_{i}$. Then,
$\left\\{\mathcal{V}_{i}\right\\}_{i=1}^{L}$ gives the trajectory followed by
the JGS algorithm in selecting its sensors from the different sets
$\mathcal{S}_{1},\ldots,\mathcal{S}_{L}$. In particular,
$\left\\{\mathcal{V}_{i}\right\\}_{i=1}^{L}$ depends on $\mathcal{A}$,
$\boldsymbol{\Sigma}$, and $M_{i}$ for $i=1,\ldots,L$.

For any iteration $m$ of the JGS algorithm, if $m\in\mathcal{V}_{i}$ for
$i\in\\{1,\ldots,L\\}$, then at this iteration, the sensor $t^{m}$ is selected
from the set $\left(\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right)$. Let $t^{m}$
be equal to
$v_{j^{m}}^{i}\in\left(\mathcal{T}^{\ast}\cap\mathcal{S}_{i}\right)$ for
$j^{m}\in\\{1,\ldots,M_{i}\\}$. Then,
$\rho_{t^{m}}\left(\mathcal{T}^{m-1}\right)\geq\rho_{o_{j^{m}}^{i}}\left(\mathcal{T}^{m-1}\right)$,
since $t^{m}$ is the element selected by the greedy algorithm. Thus, with
$\mathcal{T}^{0}=\varnothing$ denoting the initial selection, we get

$\displaystyle\mathcal{C}\left(\mathcal{T}^{\ast}\right)$
$\displaystyle=\sum_{m=1}^{M}\rho_{t^{m}}\left(\mathcal{T}^{m-1}\right)\overset{(a)}{=}\sum_{i=1}^{L}\sum_{m\in\mathcal{V}_{i}}\rho_{t^{m}}\left(\mathcal{T}^{m-1}\right)$
$\displaystyle\overset{(b)}{\geq}\sum_{i=1}^{L}\sum_{m\in\mathcal{V}_{i}}\rho_{o_{j^{m}}^{i}}\left(\mathcal{T}^{m-1}\right)\overset{(c)}{\geq}\sum_{i=1}^{L}\sum_{m\in\mathcal{V}_{i}}\rho_{o_{j^{m}}^{i}}\left(\mathcal{T}^{\ast}\right)$
$\displaystyle\overset{(d)}{\geq}\sum_{i=1}^{L}\rho_{{}_{\mathcal{T}_{OPT,i}}}\left(\mathcal{T}^{\ast}\right)\overset{(e)}{\geq}\rho_{{}_{\mathcal{T}_{OPT}}}\left(\mathcal{T}^{\ast}\right)$
$\displaystyle=\mathcal{C}\left(\mathcal{T}_{OPT}\cup\mathcal{T}^{\ast}\right)-\mathcal{C}\left(\mathcal{T}^{\ast}\right)\overset{(f)}{\geq}\mathcal{C}\left(\mathcal{T}_{OPT}\right)-\mathcal{C}\left(\mathcal{T}^{\ast}\right)$
(22)

Here, (a) follows by rearranging the terms in the summation, (b) follows from
the greediness of the JGS algorithm and the one-to-one maps constructed
previously, (c) follows from the submodularity of $\mathcal{C}$, (d) and (e)
follow from the submodularity of
$\rho_{{}_{\mathcal{R}}}\left(\mathcal{T}\right)$ from (21), and since
$\mathcal{C}$ is a normalized function, and (f) follows due to the
monotonicity of $\mathcal{C}$.

Finally, rearranging (22), Theorem 1 is proved.

##  Appendix C Proof of Theorem 2

For this proof, let $\mathcal{T}_{m}$ denote the set of samples selected by
the algorithm till the $m$-th iteration,
$c_{m}=\mathcal{C}\left(\mathcal{T}_{m}\right)-\mathcal{C}\left(\mathcal{T}_{m-1}\right)$
denote the incremental cost of the added sample at the $m$-th iteration, and
$\rho_{j}\left(\mathcal{T}_{m}\right)$ denote the incremental cost of adding
the element $\\{j\\}$ to the set $\mathcal{T}_{m}$.

In the proof, the following property of normalized, monotone, non-decreasing
submodular functions $\mathcal{C}$ will be extensively used.

$\mathcal{C}(\mathcal{T})\leq\mathcal{C}(\mathcal{S})+\sum_{j\in(\mathcal{T}-\mathcal{S})}\rho_{j}(\mathcal{S}),\text{
}\forall\mathcal{S},\mathcal{T}\in\mathcal{N}$ (23)

where
$\rho_{j}(\mathcal{S})\coloneqq\mathcal{C}\left(\mathcal{S}\cup\\{j\\}\right)-\mathcal{C}(\mathcal{S})$
is the incremental cost of adding the element $j$ to the set $\mathcal{S}$.

In order to prove Theorem 2, we first show the performance of the algorithm
until the switching of the search space occurs at the $m_{s}$-th iteration and
then how that affects the performance of the algorithm after the switch. Lemma
1 states the performance for $m\leq m_{s}$, and Lemma 2 states the performance
for $m>m_{s}$, where $m$ denotes the iteration count of the algorithm.

######  Lemma 1.

For $m\leq m_{s}$, if $\mathcal{T}_{m}$ is the set selected by the algorithm
till the $m$-th iteration, and $\mathcal{C}$ is a normalized non-decreasing
submodular function, then

$\mathcal{C}\left(\mathcal{T}_{m}\right)\geq\left[1-\left(1-\frac{1}{M_{1}+M_{2}}\right)^{m}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right),\\\
\text{ for }m=1,2,\ldots,m_{s}.$ (24)

###### Proof.

The cost function $\mathcal{C}$ is a normalized function, so that, if
$\mathcal{T}_{0}=\varnothing$, then,
$\mathcal{C}\left(\mathcal{T}_{0}\right)=0$.

The cost function $\mathcal{C}$ is a non-decreasing function, so that,
$\rho_{j}\left(\mathcal{T}_{m}\right)=\mathcal{C}\left(\mathcal{T}_{m}\cup\\{j\\}\right)-\mathcal{C}\left(\mathcal{T}_{m}\right)\geq
0$.

We use the property of submodular functions given by (23), assuming the
function is non-decreasing, to get,

$\displaystyle\mathcal{C}\left(\mathcal{T}_{OPT}\right)$
$\displaystyle\leq\mathcal{C}\left(\mathcal{T}_{m}\right)+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)}\rho_{j}\left(\mathcal{T}_{m}\right).$
(25)

Now, for $m\leq m_{s}$, the algorithm chooses the best possible sample out of
the entire available set of samples at each step. Thus, we get from inequality
(25),

$\displaystyle\mathcal{C}\left(\mathcal{T}_{OPT}\right)$
$\displaystyle\overset{\tiny{(a)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)}c_{m+1}$
$\displaystyle\overset{\tiny{(b)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+\left(M_{1}+M_{2}\right)c_{m+1}$
$\displaystyle=\mathcal{C}\left(\mathcal{T}_{m}\right)+\left(M_{1}+M_{2}\right)\left(\mathcal{C}\left(\mathcal{T}_{m+1}\right)-\mathcal{C}\left(\mathcal{T}_{m}\right)\right),$
(26)

where step (a) follows since $c_{m+1}\geq\rho_{j}\left(\mathcal{T}_{m}\right)$
for any $j\in\left(\mathcal{S}_{1}\cup\mathcal{S}_{2}-\mathcal{T}_{m}\right)$
since each iteration of the greedy algorithm chooses the sample with the
highest incremental cost. (b) follows as
$\left|\mathcal{T}_{OPT}-\mathcal{T}_{m}\right|\leq\left(M_{1}+M_{2}\right)$,
since $\mathcal{T}_{OPT}$ contains only $\left(M_{1}+M_{2}\right)$ elements.

Using inequality (26), and the fact that
$\mathcal{C}\left(\mathcal{T}_{0}\right)=0$, we can use inductive analysis to
get,

$\mathcal{C}\left(\mathcal{T}_{m+1}\right)\geq\left[1-\left(1-\frac{1}{M_{1}+M_{2}}\right)^{m+1}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right).$

∎

From Lemma 1, we get for $m=m_{s}$,

$\mathcal{C}\left(\mathcal{T}_{m_{s}}\right)\geq\left[1-\left(1-\frac{1}{M_{1}+M_{2}}\right)^{m_{s}}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right).$
(27)

This gives the worst-case performance of the set chosen by the algorithm till
the $m_{s}$-th iteration, that is, till just before the switch in the search
space occurs. Using inequality (27), we next find a lower bound for the
performance of the algorithm for iterations $m>m_{s}$.

######  Lemma 2.

Assuming that the algorithm has selected all $M_{1}$ samples from
$\mathcal{S}_{1}$ at the $m_{s}$-th iteration, for iteration $m=m_{s}+k$,
$1\leq k\leq\left(M_{1}+M_{2}-m_{s}\right)$, if $\mathcal{T}_{m_{s}+k}$ is the
set selected by the algorithm till the $\left(m_{s}+k\right)$-th iteration,
and $\mathcal{C}$ is a normalized non-decreasing submodular function, then

$\mathcal{C}\left(\mathcal{T}_{m_{s}+k}\right)\geq\left[1-\frac{M_{1}}{M_{2}}\sum_{j=0}^{k-1}\left(1-\frac{M_{1}+1}{M_{2}}\right)^{j}-\right.\\\
\left.\left(1-\frac{M_{1}+1}{M_{2}}\right)^{k}\left(1-\frac{1}{M_{1}+M_{2}}\right)^{m_{s}}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right),\\\
\text{for }k=1,2,\ldots,\left(M_{1}+M_{2}-m_{s}\right).$ (28)

If, on the other hand, the algorithm exhausts $M_{2}$ samples from
$\mathcal{S}_{2}$ at the $m_{s}$-th iteration, then, under similar assumptions
on the cost function,

$\mathcal{C}\left(\mathcal{T}_{m_{s}+k}\right)\geq\left[1-\frac{M_{2}}{M_{1}}\sum_{j=0}^{k-1}\left(1-\frac{M_{2}+1}{M_{1}}\right)^{j}-\right.\\\
\left.\left(1-\frac{M_{2}+1}{M_{1}}\right)^{k}\left(1-\frac{1}{M_{1}+M_{2}}\right)^{m_{s}}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right),\\\
\text{for }k=1,2,\ldots,\left(M_{1}+M_{2}-m_{s}\right).$ (29)

###### Proof.

For $m>m_{s}$, we can consider as if the algorithm is starting with
$\mathcal{T}_{m_{s}}$ as the initial set. Then, inequality (27) is the initial
cost from where the algorithm begins.

Let us first assume that the algorithm has selected $M_{1}$ samples from
$\mathcal{S}_{1}$ at the $m_{s}$-th iteration. The other case, when $M_{2}$
samples are exhausted from $\mathcal{S}_{2}$ at the $m_{s}$-th iteration,
follows similarly. For $m\geq m_{s}$, we again use the property of submodular
functions given by (23), assuming the function is non-decreasing, to obtain,

$\mathcal{C}\left(\mathcal{T}_{OPT}\right)\leq\mathcal{C}\left(\mathcal{T}_{m}\right)+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}}\rho_{j}\left(\mathcal{T}_{m}\right)+\\\
\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{2}}\rho_{j}\left(\mathcal{T}_{m}\right).$
(30)

Now, from the $\left(m_{s}+1\right)$-th iteration, i.e., for $m>m_{s}$ the
algorithm selects the samples from the set
$\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)$ only. It can be seen from Fig.
(10) that
$\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{2}=\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)$.
Thus, we get,

$\displaystyle\mathcal{C}\left(\mathcal{T}_{OPT}\right)$
$\displaystyle\overset{\tiny{(a)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)}c_{m+1}$
$\displaystyle+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}}\rho_{j}\left(\mathcal{T}_{m}\right)$
$\displaystyle\overset{\tiny{(b)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+M_{2}c_{m+1}+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}}\rho_{j}\left(\mathcal{T}_{m}\right)$
$\displaystyle\overset{\tiny{(c)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+M_{2}c_{m+1}$
$\displaystyle+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}}\rho_{j}\left(\mathcal{T}_{m_{s}-1}\right)$
$\displaystyle\mathcal{C}\left(\mathcal{T}_{OPT}\right)$
$\displaystyle\overset{\tiny{(d)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+M_{2}c_{m+1}+\sum_{j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}}c_{m_{s}}$
$\displaystyle\overset{\tiny{(e)}}{\leq}\mathcal{C}\left(\mathcal{T}_{m}\right)+M_{2}c_{m+1}+M_{1}c_{m_{s}}$
$\displaystyle\overset{\tiny{(f)}}{\leq}M_{2}\mathcal{C}\left(\mathcal{T}_{m+1}\right)-\left(M_{2}-M_{1}-1\right)\mathcal{C}\left(\mathcal{T}_{m}\right).$
(31)

Here,

  * $-$

(a) follows since the greedy algorithm chooses from the set
$\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)$ at the $m$-th iteration, making
the incremental cost $c_{m+1}\geq\rho_{j}\left(\mathcal{T}_{m}\right)$ for any
$j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)\subseteq\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)$.

  * $-$

(b) follows as
$\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{2}=\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)\subseteq\left(\mathcal{T}_{OPT}\cap\mathcal{S}_{2}\right)$,
thus making
$\left|\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)\right|\leq\left|\left(\mathcal{T}_{OPT}\cap\mathcal{S}_{2}\right)\right|=M_{2}$.

  * $-$

(c) follows from the definition of submodular functions, since
$\left(\mathcal{T}_{m_{s}-1}\right)\subseteq\left(\mathcal{T}_{m}\right)$.

  * $-$

(d) is true since at the $m_{s}$-th iteration of the greedy algorithm, the
incremental cost $c_{m_{s}}\geq\rho_{j}\left(\mathcal{T}_{m_{s}-1}\right)$ for
any $j\notin\mathcal{T}_{m_{s}-1}$. Now, as
$\mathcal{T}_{m_{s}-1}\subseteq\mathcal{T}_{m}$, then
$\left(\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}\right)\subseteq\left(\left(\mathcal{T}_{OPT}-\mathcal{T}_{m_{s}-1}\right)\cap\mathcal{S}_{1}\right)$.
This implies, if
$j\in\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}$, then
$j\notin\mathcal{T}_{m_{s}-1}$.

  * $-$

(e) is true since
$\left(\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}\right)\subseteq\left(\mathcal{T}_{OPT}\cap\mathcal{S}_{1}\right)$,
thus making
$\left|\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{1}\right|\leq\left|\mathcal{T}_{OPT}\cap\mathcal{S}_{1}\right|=M_{1}$.

  * $-$

(f) follows from the monotone increasing property of the given cost. Thus,
$\mathcal{C}\left(\mathcal{T}_{m_{s}}\right)\leq\mathcal{C}\left(\mathcal{T}_{m}\right)$.

Figure 10: Venn diagram to show
$\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\left(\mathcal{S}_{2}-\mathcal{T}_{m}\right)=\left(\mathcal{T}_{OPT}-\mathcal{T}_{m}\right)\cap\mathcal{S}_{2}$

Now, rearranging the inequality (31), we get,

$\mathcal{C}\left(\mathcal{T}_{m+1}\right)\geq\frac{1}{M_{2}}\mathcal{C}\left(\mathcal{T}_{OPT}\right)+\left(1-\frac{M_{1}+1}{M_{2}}\right)\mathcal{C}\left(\mathcal{T}_{m}\right).$
(32)

Using inequalities (31) and (27), we get, for
$k=1,2,\ldots,\left(M_{1}+M_{2}-m_{s}\right)$,

$\mathcal{C}\left(\mathcal{T}_{m_{s}+k}\right)\geq\left[1-\frac{M_{1}}{M_{2}}\sum_{j=0}^{k-1}\left(1-\frac{M_{1}+1}{M_{2}}\right)^{j}\right.\\\
\left.-\left(1-\frac{M_{1}+1}{M_{2}}\right)^{k}\left(1-\frac{1}{M_{1}+M_{2}}\right)^{m_{s}}\right]\mathcal{C}\left(\mathcal{T}_{OPT}\right).$
(33)

If the algorithm selects $M_{2}$ samples from $\mathcal{S}_{2}$ first at the
$m_{s}$-th iteration, the roles of $M_{1}$ and $M_{2}$ get interchanged in the
above steps. Similarly, the roles of $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$
get interchanged. Using the above analysis, we arrive at inequality (28). ∎

Theorem 2 follows directly from Lemma 2, by replacing $m_{s}+k=M_{1}+M_{2}$,
that is, by evaluating the worst-case performance of the algorithm from (28)
for the last iteration.

## References

  * [1] S. Constantinos, M. Pattichis, and E. Micheli-Tzanakou, “Medical imaging fusion applications: An overview,” in _Conf. Rec. 35th Asilomar Conf. Signals, Syst. and Comput._ , vol. 2, 2001, pp. 1263–1267 vol.2.
  * [2] J. Ko, C. Lu, M. B. Srivastava, J. A. Stankovic, A. Terzis, and M. Welsh, “Wireless sensor networks for healthcare,” _Proc. IEEE_ , vol. 98, no. 11, pp. 1947–1960, 2010.
  * [3] H. Alemdar and C. Ersoy, “Wireless sensor networks for healthcare: A survey,” _Comput. Netw._ , vol. 54, no. 15, pp. 2688–2710, 2010.
  * [4] G. Liu, R. Tan, R. Zhou, G. Xing, W.-Z. Song, and J. M. Lees, “Volcanic earthquake timing using wireless sensor networks,” in _Proc. 12th Int. Conf. Inf. Process. Sensor Netw._ , New York, NY, USA, 2013, p. 91–102.
  * [5] S. Savazzi, U. Spagnolini, L. Goratti, D. Molteni, M. Latva-aho, and M. Nicoli, “Ultra-wide band sensor networks in oil and gas explorations,” _IEEE Commun. Mag._ , vol. 51, no. 4, pp. 150–160, 2013.
  * [6] K. K. Khedo, Y. Bissessur, and D. S. Goolaub, “An inland wireless sensor network system for monitoring seismic activity,” _Future Gener. Comput. Syst._ , vol. 105, pp. 520–532, 2020.
  * [7] J. K. Hart and K. Martinez, “Environmental sensor networks: A revolution in the earth system science?” _Earth-Sci. Rev._ , vol. 78, no. 3, pp. 177–191, 2006.
  * [8] S. Rajasegarar, T. C. Havens, S. Karunasekera, C. Leckie, J. C. Bezdek, M. Jamriska, A. Gunatilaka, A. Skvortsov, and M. Palaniswami, “High-resolution monitoring of atmospheric pollutants using a system of low-cost sensors,” _IEEE Trans. Geosci. Remote Sens._ , vol. 52, no. 7, pp. 3823–3832, 2014.
  * [9] A. Bose and K. Clements, “Real-time modeling of power networks,” _Proc. IEEE_ , vol. 75, no. 12, pp. 1607–1622, 1987.
  * [10] V. Terzija, G. Valverde, D. Cai, P. Regulski, V. Madani, J. Fitch, S. Skok, M. M. Begovic, and A. Phadke, “Wide-area monitoring, protection, and control of future electric power networks,” _Proc. IEEE_ , vol. 99, no. 1, pp. 80–93, 2011.
  * [11] M. R. Alam, M. B. I. Reaz, and M. A. M. Ali, “A review of smart homes—past, present, and future,” _IEEE Trans. Syst., Man, Cybern. C_ , vol. 42, no. 6, pp. 1190–1203, 2012.
  * [12] M. Li and H.-J. Lin, “Design and implementation of smart home control systems based on wireless sensor networks and power line communications,” _IEEE Trans. Ind. Electron._ , vol. 62, no. 7, pp. 4430–4442, 2015.
  * [13] F. Viani, F. Robol, A. Polo, P. Rocca, G. Oliveri, and A. Massa, “Wireless architectures for heterogeneous sensing in smart home applications: Concepts and real implementation,” _Proc. IEEE_ , vol. 101, no. 11, pp. 2381–2396, 2013.
  * [14] G. W. Peters, I. Nevat, and T. Matsui, “How to utilize sensor network data to efficiently perform model calibration and spatial field reconstruction,” in _Modern Methodology and Appl. Spatial-Temporal Model._ Tokyo: Springer Japan, 2015, pp. 25–62.
  * [15] P. Zhang, I. Nevat, G. W. Peters, F. Septier, and M. A. Osborne, “Spatial field reconstruction and sensor selection in heterogeneous sensor networks with stochastic energy harvesting,” _IEEE Trans. Signal Process._ , vol. 66, no. 9, pp. 2245–2257, 2018.
  * [16] M. Sviridenko, “A note on maximizing a submodular set function subject to a knapsack constraint,” _Operations Res. Lett._ , vol. 32, no. 1, pp. 41–43, 2004.
  * [17] M. Sviridenko, J. Vondrák, and J. Ward, “Optimal approximation for submodular and supermodular optimization with bounded curvature,” _Math. Oper. Res._ , vol. 42, no. 4, pp. 1197–1218, 2017.
  * [18] A. Badanidiyuru and J. Vondrák, “Fast algorithms for maximizing submodular functions,” in _Proc. 2014 Annu. ACM-SIAM Symp. Discrete Algorithms_ , 2014, pp. 1497–1514.
  * [19] S. Joshi and S. Boyd, “Sensor selection via convex optimization,” _IEEE Trans. Signal Process._ , vol. 57, no. 2, pp. 451–462, 2009.
  * [20] S. P. Chepuri and G. Leus, “Sparsity-promoting sensor selection for non-linear measurement models,” _IEEE Trans. Signal Process._ , vol. 63, no. 3, pp. 684–698, 2015.
  * [21] P. Chiu and F. Lin, “A simulated annealing algorithm to support the sensor placement for target location,” in _Can. Conf. Elect. Comput. Eng. 2004_ , vol. 2, 2004, pp. 867–870 Vol.2.
  * [22] M. Al-Obaidy, A. Ayesh, and A. F. Sheta, “Optimizing the communication distance of an ad hoc wireless sensor networks by genetic algorithms,” _Artif. Intell. Rev._ , vol. 29, no. 3, pp. 183–194, 2008.
  * [23] R. Mukherjee and S. O. Memik, “Systematic temperature sensor allocation and placement for microprocessors,” in _Proc. 43rd Annu. Des. Automat. Conf._ , New York, NY, USA, 2006, p. 542–547.
  * [24] D. J. C. MacKay, “Information-Based Objective Functions for Active Data Selection,” _Neural Comput._ , vol. 4, no. 4, pp. 590–604, 07 1992.
  * [25] H. Wang, K. Yao, G. Pottie, and D. Estrin, “Entropy-based sensor selection heuristic for target localization,” in _Proc. 3rd Int. Symp. Inf. Process. Sensor Netw._ , New York, NY, USA, 2004, p. 36–45.
  * [26] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions—i,” _Math. Program._ , vol. 14, no. 1, pp. 265–294, 1978.
  * [27] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrak, and A. Krause, “Lazier than lazy greedy,” _Proc. AAAI Conf. Artif. Intell._ , vol. 29, no. 1, Feb. 2015.
  * [28] A. Hashemi, M. Ghasemi, H. Vikalo, and U. Topcu, “Randomized greedy sensor selection: Leveraging weak submodularity,” _IEEE Trans. Autom. Control_ , vol. 66, no. 1, pp. 199–212, 2020.
  * [29] L. A. Wolsey, “An analysis of the greedy algorithm for the submodular set covering problem,” _Combinatorica_ , vol. 2, no. 4, pp. 385–393, 1982.
  * [30] H. Lin and J. Bilmes, “Multi-document summarization via budgeted maximization of submodular functions,” in _Human Lang. Technol.: Annu. Conf. North Amer. Chapter Assoc. Comput. Linguistics_ , 2010, pp. 912–920.
  * [31] Z. Esmaeilbeig, K. V. Mishra, A. Eamaz, and M. Soltanalian, “Submodular optimization for placement of intelligent reflecting surfaces in sensing systems,” in _IEEE Int. Workshop Comput. Adv. Multi-Sensor Adaptive Process. (CAMSAP)_. IEEE, 2023, pp. 401–405.
  * [32] M. R. Kirchner, J. P. Hespanha, and D. Garagić, “Heterogeneous measurement selection for vehicle tracking using submodular optimization,” in _2020 IEEE Aerospace Conf._ , 2020, pp. 1–10.
  * [33] H. Zhang, R. Ayoub, and S. Sundaram, “Sensor selection for kalman filtering of linear dynamical systems: Complexity, limitations and greedy algorithms,” _Automatica_ , vol. 78, pp. 202–210, 2017.
  * [34] O. M. Bushnaq, A. Chaaban, S. P. Chepuri, G. Leus, and T. Y. Al-Naffouri, “Sensor placement and resource allocation for energy harvesting IoT networks,” _Digital Signal Process._ , vol. 105, p. 102659, 2020, special Issue on Optimum Sparse Arrays and Sensor Placement for Environmental Sensing.
  * [35] S. M. Kay, _Fundamentals of Statistical Signal Processing: Estimation Theory_. USA: Prentice-Hall, Inc., 1993\.
  * [36] J. Ranieri, A. Chebira, and M. Vetterli, “Near-optimal sensor placement for linear inverse problems,” _IEEE Trans. Signal Process._ , vol. 62, no. 5, pp. 1135–1146, 2014.
  * [37] E. Tohidi, M. Coutino, S. P. Chepuri, H. Behroozi, M. M. Nayebi, and G. Leus, “Sparse antenna and pulse placement for colocated mimo radar,” _IEEE Trans. Signal Process._ , vol. 67, no. 3, pp. 579–593, 2019.
  * [38] G. H. Golub, “Comparison of the variance of minimum variance and weighted least squares regression coefficients,” _Ann. Math. Statist._ , vol. 34, no. 3, pp. 984–991, 1963.
  * [39] Y. C. Eldar and G. Kutyniok, _Compressed Sensing: Theory and Applications_. Cambridge University Press, 2012.
  * [40] R. Sharma, “Some more inequalities for arithmetic mean, harmonic mean and variance,” _J. Math. Inequalities_ , vol. 2, no. 1, pp. 109–114, 2008.
  * [41] G. Bienvenu and L. Kopp, “Optimality of high resolution array processing using the eigensystem approach,” _IEEE Trans. Acoust., Speech, Signal Process._ , vol. 31, no. 5, pp. 1235–1248, 1983.
  * [42] E. Tuncer and B. Friedlander, _Classical and modern direction-of-arrival estimation_. Academic Press, 2009.
  * [43] Y. Filmus and J. Ward, “A tight combinatorial algorithm for submodular maximization subject to a matroid constraint,” in _IEEE Annu. Symp. Found. Comput. Sci._ , 2012, pp. 659–668.