placement in power networks [9]- [11], sensor scheduling in wireless sensor networks [2], [12], and subset selection in machine learning [13].

For a variety of performance criteria, finding an optimal subset of sensors requires solving a computationally challenging combinatorial optimization problem, possibly using branch-and-bound search [14]. By reducing it to the set cover problem, sensor selection was in fact shown to be NP-hard [15]. This hardness result has motivated development of numerous heuristics and approximate algorithms. For instance, [16] formulated the sensor selection problem as the maximization (minimization) of the log det of the Fisher information matrix (error covariance matrix), and found a solution by relaxing the problem to a semidefinite program (SDP). The computational complexity of finding the solution to the SDP relaxation of the sensor selection problem is cubic in the total number of available sensors, which limits its practical feasibility in large-scale networks consisting of many sensing nodes. Moreover, the solution to the SDP relaxation comes with no performance guarantees. To overcome these drawbacks, Shamaiah et al. [3] proposed a greedy algorithm guaranteed to achieve at least (1 1/e) of the optimal objective at a complexity lower than that of the SDP relaxation. The theoretical underpinnings of the greedy approach to the sensor selection problem in [3] are drawn from the area of submodular function optimization. In particular, these results stem from the fact that the logarithm of the determinant (log det) of the Fisher information matrix is a monotone submodular function. Nemhauser et al. [17] studied maximization of such a function subject to a uniform matroid constraint and showed that the greedy algorithm, which iteratively selects items providing maximum marginal gain, achieves (1 1/e) approximation factor. More recently, [4]- [6], [8], employed and analyzed greedy algorithms for finding approximate solutions to the log det maximization problem in a number of practical settings.

Most of the existing work on greedy sensor selection has focused on optimizing the log det of the Fisher information matrix, an objective indicative of the volume of the confidence ellipsoid. However, this criterion does not explicitly relate to the mean-square error (MSE) which is often a natural performance metric of interest in estimation problems. The MSE, i.e., the trace of the covariance matrix of the estimation error, is not supermodular [18]- [23]. Therefore, its negative value, which we would like to maximize, is not submodular. Consequently, the setting and results of [17] do not apply to the MSE minimization problem. Recently, Wang et al. [24] analyzed performance of the greedy algorithm in the general setting of maximizing a monotone non-decreasing objective function that is not necessarily submodular. They used a notion of the total curvature µ of the objective function to show that the greedy algorithm provides a ((1 + µ) 1 )-approximation under a matroid constraint. However, determining the elemental curvature defined in [24] is itself an NP-hard problem. Therefore, providing performance guarantees for the settings where the objective function is not submodular or supermodular, such as the trace of the covariance matrix of the estimation error in the sensor selection problem, remains a challenge.

On another note, processing massive amounts of data collected by modern large-scale networks may be challenging even for greedy algorithms. To further reduce the computational burden of maximizing a monotone increasing, submodular function subject to cardinality constraints, the authors of [13] proposed a stochastic greedy algorithm that achieves (1 1/e ✏)-approximation factor, where ✏ denotes a parameter that can be varied to explore the performance-complexity trade-off. However, the results of [13] do not apply to the sensor selection problem under The objective is to select a small subset of range and angular measurements gathered by the UAVs to communicate to the control unit.

the (non-submodular) MSE objective.

In this paper, we formulate the task of selecting sensors in a large-scale network as the problem of maximizing a monotone non-submodular objective function that is directly related to the mean-square estimation error. By analyzing curvature of the objective function, we derive sufficient conditions under which the function is weak submodular. In the important setting where a state-space model describes the dynamics of the process and sensor observations, we propose a randomized greedy algorithm and find a bound on the MSE of the state estimate formed by the Kalman filter that uses the measurements of the sensors selected by the proposed algorithm. A further implication of these results is that, when the measurement vectors are Gaussian or Bernoulli as frequently encountered in reduced-dimensionality Kalman filtering using random projections [25], the MSE objective is weak submodular with high probability. Our extensive simulations demonstrate that the proposed randomized greedy sensor selection scheme significantly outperforms both greedy and SDP relaxation methods in terms of computational complexity, and hence runtime, while providing essentially the same or improved MSE performance.

The rest of the paper is organized as follows. Section II presents a motivating example and sets up the system model. In Section III we describe the novel formulation of the sensor selection problem and derive a bound on the curvature of the MSE-related objective function. In Section IV, we introduce the randomized greedy algorithm and analyze its performance. Section V presents the simulation results while Section VI states the concluding remarks.

Notation: Bold capital letters denote matrices while bold lowercase letters represent vectors. H k (i, j) is the (i, j) entry of the time-varying matrix H k at time k, h k,j is the j th row of H k , H k,S is a submatrix of H k that consists of the rows of H k indexed by the set S, and max (H k ) and min (H k ) are the maximum and minimum eigenvalues of H k , respectively. Spectral (`2) norm of a matrix is denoted by k.k. I n 2 R n⇥n is the identity matrix. Moreover, let [n] := {1, 2, . . . , n}.

This section starts by a description of a motivating example of multi-object tracking under communication and power constraints. Then we proceed to define the system model and mathematically formulate the sensor selection problem studied in the paper.

Consider a tracking system, shown in Fig. 1, where a control unit surveys an area via a swarm of unmanned aerial vehicles (UAVs). The UAVs are equipped with GPS and radar systems and can communicate with each other over locally established communication channels. However, only a few of the UAVs known as swarm leaders are allowed to communicate to the control unit because of various practical restrictions such as power constraints. The UAVs patrol the area according to a predefined search pattern to gather information about the location of mobile objects of interest. Each UAV, by using its radar system, acquires range and angular measurements of all the objects that are within the maximum radar detection range and are capable of transmitting those measurements to the swarm leaders. Due to limitations on the rate of communication between the swarm leaders and the control unit, and to reduce delays in tracking from high computation, only a subset of the gathered measurements is communicated to the control unit. In order to track the locations of the object, the control unit employs Kalman filtering using the received measurements. Therefore, the goal of swarm leaders is to perform sensor scheduling and select a subset of range and angular measurements such that (i) the communication constraint is satisfied, and (ii) the mean-square error of the Kalman filter estimate of the objects' locations is minimized.

Consider a discrete-time, linear, time-varying state-space model described by

where x k 2 R m is the state vector at time k that we aim to estimate, y k 2 R n is the measurement vector, w k 2 R m and v k 2 R n are zero-mean white Gaussian noise processes with covariances Q k and R k , respectively, A k 2 R m⇥m is the state transition matrix and H k 2 R n⇥m is the matrix whose rows at time k are the measurement vectors h k,i 2 R m , 1  i  n. We assume the states x k are uncorrelated with w k and v k . Additionally, we assume

I m , and R k = diag( 2 1 , . . . , 2 n ). Note that, unlike the past work on greedy sensor selection in [3], [12], [26], [27], this model does not restrict the noise covariance matrix to be a multiple of identity.

Due to limited resources, fusion center aims to select K out of n sensors and use their measurements to estimate the state vector x k such that the trace of the covariance matrix of the estimation error, i.e., the MSE of the estimator implemented using the Kalman filter is minimized. Similar to prior work in [3], [12], [16], we assume that the measurement vectors h k,i are available at the fusion center. Let xk|k 1 and xk|k denote the predicted and filtered linear minimum mean-square error (LMMSE) estimators of x k , respectively. In other words, xk|k 1 is the LMMSE estimator of x k given {y S1 , . . . , y S k 1 } and xk|k is the LMMSE estimator of x k given {y S1 , . . . , y S k }, where S j denotes the set of sensors selected at time j and y Sj denotes the vector of measurements collected by those sensors. Moreover, let P k|k 1 and P k|k denote the predicted and filtered error covariance matrix of the Kalman filter at time instant k, respectively, i.e.,

where

) and the measurements are uncorrelated across sensors, it holds that

Furthermore,

is the corresponding Fisher information matrix. In the information form, the filtered estimator of x k is expressed as

The MSE of the estimate found in ( 2) is given by the trace of the filtered error covariance matrix P k|k :

To minimize (3), at each time step the fusion center seeks a solution to the optimization problem min

By a reduction to the well-known set cover problem, the combinatorial optimization (4) can be shown to be NP-hard [15], [28]. In principle, to find the optimal solution one needs to exhaustively search over all schedules of K sensors.

The techniques proposed in [16], albeit for an optimality criterion different from MSE and a simpler measurement model, find a subset of sensors that yields a sub-optimal MSE performance while being computationally much more efficient than the exhaustive search. In particular, [16] relies on finding the solution to the following SDP relaxation: min

The complexity of the SDP algorithm scales as O(n 3 ) which is infeasible in many practical settings. Furthermore, there are no guarantees on the achievable MSE performance of the SDP relaxation. Note that when the number of sensors in a network and the size of the state vector x k are relatively large, even the greedy algorithm proposed in [3] may be computationally prohibitive.

Leveraging the idea of weak submodularity, in this section we propose a new formulation of the sensor selection problem concerned with minimizing the MSE of the Kalman filter that relies on a subset of network nodes to track states of a hidden random process. We first overview concepts that are essential for the development of the proposed framework.

for all subsets S ✓ T ⇢ X and j 2 X\T .

A concept closely related to submodularity is the notion of curvature of a set function. The curvature quantifies how close the function is to being submodular. In particular, here we define the element-wise curvature.

Definition 3. The element-wise curvature C l of a monotone non-decreasing function f is defined as

where

denote the marginal values of adding element i to sets S and T , respectively, and

A set function is submodular if and only if C max  1. We refer to f (S) as being weak submodular if its curvature

Let X be a finite set and let I denote a collection of subsets of X. The pair M = (X, I) is a matroid if the following two statements hold:

• Hereditary property. If T 2 I, then S 2 I for all S ✓ T .

• Augmentation property. If S, T 2 I and |S| < |T |, then there exists e 2 T \S such that S [ {e} 2 I.

The collection I is called the set of independent sets of the matroid M. A maximal independent set is a basis. It is easy to show that all the bases of a matroid have the same cardinality.

Given a monotone non-decreasing set function f : 2 X ! R with f (;) = 0, and a uniform matroid M = (X, I), we are interested in solving the combinatorial problem

Recall that for Kalman filtering in the resource constrained scenario, if S k is the set of sensors selected at time k then the error covariance matrix of the filtered estimate is P k|k = F 1 S k , the inverse of the corresponding Fisher information matrix. Let us define f (S) as

Clearly, since P k|k 1 is known, there is a one-to-one correspondence between f (S k ) computed for a given subset of sensors S k and the MSE of the LMMSE estimator (i.e., filtered estimate of the Kalman filter) that uses measurements acquired by the sensors in S k . Therefore, we can express the optimization problem (4) as

We now argue that ( 9) is indeed an instance of the general combinatorial problem (8). By defining X = [n] and

In Proposition 1 below we characterize important properties of f (S) and develop a recursive scheme to efficiently compute the marginal gain of querying a sensor. The formula for the marginal gain of f (S) is also of interest in our subsequent analysis of its weak submodularity properties.

Then, f (S) is a monotonically increasing set function, f (;) = 0, and

where upon adding element j to S, F S is updated according to

Proof. See Appendix A. ⌅

As stated in Section I, the MSE is not supermodular [18], [23]. Consequently, the proposed objective f (S) =

is also not submodular. However, as we show in Theorem 1, under certain conditions f (S) is characterized by a bounded maximum element-wise curvature C max . Theorem 1 also states a probabilistic theoretical upper bound on C max in scenarios where at each time step the measurement vectors h k,j 's are realizations of independent identically distributed (i.i.d.) random vectors drawn from a suitable distribution.

Before proceeding to Theorem 1 and its proof, we first state the matrix Bernstein inequality [29] and Weyl's inequality [30] which we will later use in the proof of Theorem 1.

Lemma 1. (Matrix Bernstein inequality [29]) Let {X `}n `=1 be a finite collection of independent, random, Hermitian matrices in R m⇥m . Assume that for all `2 [n],

Then, for all q > 0, it holds that

Lemma 2. (Weyl's inequality [30]) Let A and B be two m ⇥ m real positive definite matrices. Then it holds that

where l (A) denotes the l th largest eigenvalue of A.

We now proceed to the statement and proof of Theorem 1.

Theorem 1. Let C max be the maximum element-wise curvature of f (S), the objective function of the sensor selection problem. Assume that kh k,j k 2 2  C for all j and k. If

for some 0 < < min (P k|k 1 ), then it holds that

Furthermore, if h k,j 's are i.i.d. zero-mean random vectors with covariance matrix 2 h I m such that 2 h < C, then for all q > 0, with probability

it holds that

Proof. We prove the statement of the theorem by relying on the recursive expression for the marginal gain stated in Proposition 1. We first establish a sufficient condition for weak submodularity of f (S). In particular, from the definition of the element-wise curvature and (10), for all (S, T, j) 2 X l we obtain

where the inequality follows from the Courant-Fischer min-max theorem [30]. Notice that max (F 1 S ) = min (F S ) 1 and min (F T ) min (F S ) min (F ; ) = min (P 1 k|k 1 ) by Lemma 2. This fact, along with the definition of C max implies

where (a) follows from the fact that max (F S )

) and (b) holds since

is a monotonically increasing function for x > 0. Now, since the maximum eigenvalue of a positive definite matrix satisfies the triangle inequality, we have

Therefore, by combining inequalities (15) and ( 20) we obtain the result in (16).

Next, to analyze the setting of i.i.d random measurement vectors, we bound max (F [n] ) using Lemma 1. Let

h I m and Y = P n j=1 X j . To use the result of Lemma 1, one should first verify expressions in (12). To this end, note that

This in turn implies that

by the linearity of expectation and the triangle inequality. To proceed, we need to determine max (X j ) and E[X 2 j ]. First, let us verify h k,j is an eigenvector of X j by observing that

where h k,j h > k,j 2 h I m is the corresponding eigenvalue. Since h k,j h > k,j is a rank-1 matrix, other eigenvalues of X j are all equal to

and we recall that C 2 h > 0. We can now establish an upper bound on

where we have used the fact that E[X j ] = 0. Thus,

h . Now, according to Lemma 1, for all q > 0 it holds that Pr{ max (Y)  q} p where

Therefore,

with probability p. This completes the proof. ⌅ Remark 1: The setting of i.i.d. random vectors described in Theorem 1 arises in scenarios where sketching techniques, such as random projections, are used to reduce dimensionality of the measurement equation (see [25] for more details). The following are often encountered examples of such settings:

1) Multivariate Gaussian measurement vectors: Let h k,j ⇠ N (0, 1 m I m ) for all j. It is straightforward to show that E[kh k,j k 2 2 ] = 1. Furthermore, it can be shown that kh k,j k 2 2 is with high probability concentrated around its expected value. Therefore, for this case,

and let

be the condition number of P k|k 1 . Then, following some elementary numerical approximations, we obtain the following corollary.

for some c 1 > 1. Then with probability

it holds that C max  3 for some c 2 > 0.

Informally, Theorem 1 states that for a well-conditioned P k|k 1 the curvature of f (S) is small, which implies weak submodularity of f (S). Furthermore, the probability of such an event exponentially increases with the number of available measurements.

The complexity of SDP relaxation and greedy algorithms for sensor selection become prohibitive in large-scale systems. Motivated by the need for practically feasible schemes, we present a randomized greedy algorithm for finding an approximate solution to (9) and derive its performance guarantees. In particular, inspired by the technique in [13] proposed in the context of optimizing submodular objective functions, we develop a computationally efficient randomized greedy algorithm (see Algorithm 1) that finds an approximate solution to (9) with a guarantee on the achievable MSE performance of the Kalman filter that uses only the observations of the selected sensors. Algorithm Algorithm 1 Randomized Greedy Sensor Scheduling 1: Input:

4: for i = 0, . . . , K 1

Set S

8:

1 performs the task of sensor scheduling in the following way. At each iteration of the algorithm, a subset R of size s is sampled uniformly at random and without replacement from the set of available sensors. The marginal gain provided by each of these s sensors to the objective function is computed using (10), and the one yielding the highest marginal gain is added to the set of selected sensors. Then the efficient recursive formula in ( 11) is used to update F 1 S so it can be analyzed when making the selection in the next iteration. This procedure is repeated K times.

Remark 2: The parameter ✏ in Algorithm 1, e K  ✏ < 1, is a predefined constant that is chosen to strike a desired balance between performance and complexity. When ✏ = e K , each iteration includes all of the non-selected sensors in R and Algorithm 1 coincides with the conventional greedy scheme. However, as ✏ approaches 1, |R| and thus the overall computational complexity decreases.

In this section we analyze Algorithm 1 and in Theorem 2 provide a bound on the performance of the proposed randomized greedy scheme when applied to finding an approximate solution to maximization problem (9).

Before deriving the main result, we first provide two lemmas. Lemma 3 states an upper bound on the difference between the values of the objective function corresponding to two sets having different cardinalities while Lemma 4 provides a lower bound on the expected marginal gain. Lemma 3. Let {C l } n 1 l=1 denote the element-wise curvatures of f (S). Let S and T be any subsets of sensors such that S ⇢ T ✓ [n] with |T \S| = r. Then it holds that

where

k be the set of selected sensors at the end of the i th iteration of Algorithm 1. Then

where O k is the set of optimal sensors at time k, (i + 1) s is the index of the selected sensor at the (i + 1) st iteration,

where c = max{C max , 1}, e K  ✏ < 1, and = 1 + max{0, s 2n 1 2(n s) }. Furthermore, the computational complexity of Algorithm 1 is O(nm 2 log( 1 ✏ )) where n is the total number of sensors and m is the dimension of x k .

k , the set generated by the end of the i th iteration of Algorithm 1. Employing Lemma 3 with S = S (i)

k , and using monotonicity of f , yields

where

Applying the law of total expectation yields

Using the definition of the maximum element-wise curvature, we obtain

It is easy to verify, e.g., by taking the derivative, that g(r) is decreasing (increasing) with respect to r if C max < 1

Hence,

Using an inductive argument and due to the fact that f (;) = 0, we obtain

Finally, using the fact that (1+x) y  e xy for y > 0 and the easily verifiable fact that e ax  1+axe a for 0 < x < 1,

To take a closer look at computational complexity of Algorithm obtained by forming an estimate using sensors selected by the randomized greedy algorithm is within a factor of the optimal MSE. ✏ c . Let MSE S k denote the mean-square estimation error obtained by forming an estimate using information provided by the sensors selected by Algorithm 1 at time k, and let MSE o be the optimal mean-square error formed using information collected by the sensors specified by the optimum solution of (9). Then the expected MSE S k is bounded as

Remark 3: Since the proposed sensor selection scheme is a randomized algorithm, the analysis of its expected MSE, as provided by Theorem 2 and Corollary 2.1, is a meaningful performance characterization. Notice that, as expected, ↵ is decreasing in both c and ✏. If f (S) is characterized by a small curvature, then f (S) is nearly submodular and the randomized greedy algorithm delivers a near-optimal sensor scheduling. As we decrease ✏, ↵ increases which in turn leads to a better approximation factor. Moreover, by following an argument similar to that of the classical analysis in [17], one can show that the approximation factor for the greedy algorithm is given by

1 c (see also [22], [27]). Therefore, the term ✏ c in ↵ denotes the difference between the approximation factors of the proposed randomized greedy algorithm and the conventional greedy scheme.

Remark 4: The computational complexity of the greedy method for sensor selection that finds marginal gains via the efficient recursion given in Proposition 1 is O(Knm 2 ). Hence, our proposed scheme provides a reduction in complexity by K/ log( 1✏ ) which may be particularly beneficial in large-scale networks, as illustrated in our simulation results.

Remark 5: In contrast to the results of [13] derived in the context of maximizing monotone submodular functions, Theorem 2 relaxes the submodularity assumption and states that the randomized greedy algorithm does not require submodularity to achieve near-optimal performance. Rather, if the set function is weak submodular, Algorithm 1 still selects a subset of sensors that provide an MSE near that achieved by the optimal subset of sensors. In addition, even if the function is submodular (e.g., if we use the log det objective instead of the MSE), the results of Theorem (2) offer an improvement over the theoretical results of [13] due to a tighter approximation bound stemming from the analysis presented in the proof of Theorem (2). Moreover, a major assumption in [13] is that R is constructed by sampling with replacement. Clearly, this contradicts the fact that a sensor selected in one iteration will not be in R in the subsequent iteration with probability one. On the contrary, we assume R is constructed by sampling without replacement and carry out the analysis in this setting that matches the actual randomized greedy sensor selection strategy.

The randomized selection step of Algorithm 1 can be interpreted as an approximation of the marginal gains of the selected sensors using a greedy scheme [3]. More specifically, for the i th iteration it holds that f jrg (S

, where subscripts rg and g refer to the sensors selected by the randomized greedy (Algorithm 1) and the greedy algorithm, respectively, and 1 In view of this argument, we obtain Theorem 3 which states that if f (S) is characterized by a bounded maximum element-wise curvature and {⌘ (i) k } K i=1 are independent random variables, Algorithm 1 returns a subset of sensors yielding an objective that with high probability is only a multiplicative factor away from the objective achieved by the optimal schedule. Theorem 3. Instate the notation and assumptions of Theorem 2. Let {⌘

k } K i=1 are independent, then for all 0 < q < 1 with probability at least 1 e CK , it holds that

for some C > 0.

k , the set generated by the end of the i th iteration of Algorithm 1 and let (i + 1) g and (i + 1) rg denote the sensors selected by the greedy and randomized greedy algorithm in the i th iteration, respectively. Let c = max{C max , 1}. Employing Lemma 3 with S = S (i)

k , and using monotonicity of f , yields

Using the fact that

for all j, we obtain

On the other hand, f (S

Combining ( 50) and (51) yields

Using an inductive argument similar to the one in the proof of Theorem 2, and noting that f (;) = 0,

1 e

where to obtain (a) we use the fact that (1 + x) y  e xy for y > 0. Therefore, since by assumption `min

k  1, we establish (46). To show the second statement, i.e., prove (47) holds in the setting of independent {⌘ (i) k } K i=1 , we apply the Bernstein's inequality [31] to the sum of independent random variables

k } are bounded random variables, from Popoviciu's inequality [31] for all i 2 [K], it follows that

Hence, based on the Bernstein's inequality, for all 0 < q < 1 Pr{

where

where (b) follows because p increases as we replace µ i (✏) and `i(✏) by their lower bounds. Finally, substituting this results in (53) yields

with probability at least 1 e C(✏,q)K . This completes the proof. ⌅

Our simulation studies in Section V empirically confirm the results of Theorems 2 and 3, and illustrate that Algorithm 1 performs favorably compared to the competing schemes both on average as well as for each individual sensor scheduling task.

Similar to Corollary 2.1, we can now obtain a probabilistic bound on the MSE (3) achievable at each time step using the proposed randomized greedy algorithm. This result is stated in Corollary 3.1 below.

Corollary 3.1. Consider the notation and assumptions of Corollary 2.1 and Theorem 3. Let 0 < q < 1 and define ↵ = 1 exp( (1 q)µmin(✏) c

). Then, with probability at least 1 e CK it holds that

for some C > 0.

To test the performance of the proposed randomized greedy algorithm, we compare it with the classic greedy algorithm and the SDP relaxation in a variety of settings as detailed next. We implemented the greedy and randomized greedy algorithms in MATLAB and the SDP relaxation scheme via CVX [32]. All experiments were run on a laptop with 2.0 GHz Intel Core i7-4510U CPU and 8.00 GB of RAM.

We first consider the problem of state estimation in a linear time-varying system via Kalman filtering. For simplicity, we assume the state transition matrix to be identity, i.e., A k = I m . At each time step, the measurement vectors, i.e., the rows of the measurement matrix H k , are drawn according to N ⇠ (0, 1 m I m ). The initial state is a zero-mean Gaussian random vector with covariance ⌃ x = I m ; and the process and measurement noise are zero-mean Gaussian with covariance matrices Q = 0.05I m and R = 0.05I n , respectively.

The MSE of the filtered estimator and running time of each scheme is averaged over 100 Monte-Carlo simulations.

The time horizon for each run is T = 10.

We first consider a system having state dimension m = 50 and the total number of sensors n = 400. We set a constraint on the number of sensors allowed to be queried at each time step to K = 55 and compare the MSE achieved by each sensor selection method over the time horizon of interest. For the randomized greedy algorithm we set ✏ = 0.001. Fig. 2 shows that the greedy method consistently yields the lowest estimation MSE while the MSE provided by the randomized greedy algorithm is slightly higher. The MSE performance achieved by solving the SDP relaxation is considerably larger than those of the greedy and randomized greedy algorithms. The time it takes each method to select K sensors is given in Table I. Both the greedy algorithm and the randomized greedy algorithm are much faster than the SDP formulation. Moreover, the randomized greedy scheme is nearly two times faster than the greedy method. Note that, in this example, in each iteration of the sensor selection procedure the randomized scheme only computes the marginal gain for a sampled subset of size 50. In contrast, the classic greedy approach computes the marginal gain for all 400 sensors. In summary, the greedy method yields slightly lower MSE but is much slower than the proposed randomized greedy algorithm.

To study the effect of the number of selected sensors on the MSE performance, we vary K from 55 to 115 with increments of 10. The MSE values at the last time step for each algorithm are shown in Fig. 3(a). As the number of selected sensors increases, the estimation becomes more accurate, as reflected by the MSE of the estimates provided by each algorithm. Moreover, the differences between the MSE values achieved by different schemes monotonically decrease as more sensors are selected. The sensor selection running times shown in Fig.

indicate that the randomized greedy scheme is nearly twice as fast as the greedy method, while the SDP method is orders of magnitude slower than both greedy and randomized greedy algorithms.

Finally, to empirically verify the results of Theorem 3, in Fig. 4 we compare histograms of MSE achieved by the greedy and the proposed randomized greedy sensor selection schemes with various choices of ✏ when K = 60. As the figure shows, the MSE of sets selected by the proposed scheme is relatively close to that selected by state-ofthe-art greedy algorithm. In addition, as ✏ decreases, the MSE of the randomized greedy algorithm approaches that of the greedy algorithm. These empirical observations coincide with our theoretical results in Theorem 3. That is, the proposed algorithm, although a randomized scheme, returns a near-optimal subset of sensors for each individual sensor selection task.

Next, we compare the performance of the randomized greedy algorithm to that of the greedy algorithm as the size of the system increases. We run both methods for 20 different system dimensions. The initial dimensions are set to m = 20, n = 200, and K = 25 and all three parameters are scaled by where varies from 1 to 20. In addition, to evaluate the effect of ✏ on the performance and runtime of the randomized greedy approach, we repeat experiments for ✏ 2 {0.1, 0.01, 0.001}. Note that the computational complexity of the SDP relaxation scheme is prohibitive in this setting and hence it is omitted. As the figure illustrates, the gap between the running times grows with the size of the system and the randomized greedy algorithm performs nearly 28 times faster than the greedy method for the largest network. Fig. 5 shows that using a smaller ✏ results in a lower MSE while it slightly increases the running time. These results suggest that, for large systems, the randomized greedy provides almost the same MSE while being much faster than the greedy algorithm.

Finally, we study the multi-object tracking application introduced in Section II-A. Specifically, we consider a scenario where twenty moving objects are initially uniformly distributed in a 5 ⇥ 10 area. At each time instance, the objects move in a random direction with a constant velocity set to 0.2. Twenty UAVs, equidistantly spread over the area, move according to a periodic parallel-path search pattern [33]. The initial phases of the UAVs' = Tr

where (a) is obtained by applying matrix inversion lemma (Sherman-Morrison formula) [30] to (F S + 2 j h k,j h > k,j ) 1 , and (b) follows from the properties of the matrix trace operator. Finally, since F S is a symmetric positive definite matrix, f j (S) > 0 which in turn implies monotonicity. (62) Note that (62) is established for a specific ordering of elements in T \S. Given an ordering {j 1 , . . . , j r }, one can form a set P = {P 1 , . . . , P r } of r permutations (e.g., by defining the right circular-shift operator P t ({j 1 , . . . , j r }) = {j r t+1 , . . . , j 1 , . . . } for 1  t  r) such that P p (j) 6 = P q (j) for p 6 = q and 8j 2 T \S; (62) holds for each such permutation. By summing the corresponding r inequalities we obtain

Rearranging (63) yields the desired result.

PROOF OF LEMMA 4

First, we aim to bound the probability of an event that a random set R contains at least one index from the optimal set of sensors which is a necessary condition to reach the optimal MSE. Let us consider S

where H p is the p th harmonic number, is the Euler-Mascheroni constant, and

) is a monotonically decreasing sequence related to Hurwitz zeta function [34]. Therefore, using the identity (65) we obtain

 ((1

where (c) follows since ⇣ n ⇣ n s = 1

by the definition of s and the fact that 1 e s n x is a concave function. Finally, according to Lemma 2 in [13],