1

A Randomized Greedy Algorithm for Near-Optimal
Sensor Scheduling in Large-Scale Sensor Networks

arXiv:1709.08823v2 [] 3 Apr 2018

Abolfazl Hashemi, Student Member, IEEE, Mahsa Ghasemi, Student Member, IEEE, Haris Vikalo, Senior
Member, IEEE, and Ufuk Topcu, Member, IEEE

Abstract—In a sensor network governed by a linear dynamical
system, often due to practical constraints such as computational
and power limitations, it is desired to select a small subset to
perform the state estimation task. In this paper, we formulate this
task as the combinatorial problem of maximizing a monotone set
function under a uniform matroid constraint. By introducing the
notion of curvature we show that the proposed objective function
is weak submodular under certain conditions by establishing
an upperbound on its maximum element-wise curvature. To
efficiently solve the proposed combinatorial problem, we develop
a randomized greedy algorithm that is significantly faster than
state-of-the-art methods. we analyze the performance of the
proposed algorithm and establish performance guarantees on
the mean square error (MSE) of the linear estimator that uses
the selected sensors in terms of the optimal MSE. Extensive
simulation results demonstrate efficacy of the randomized greedy
algorithm in a comparison with greedy and semidefinite programming relaxation methods.
Index Terms—sensor selection, sensor networks, Kalman filtering, weak submodularity

I. I NTRODUCTION

M

ODERN sensor networks, acquire myriads of measurements from a dynamical system through communication of a large number of sensors and sensor fusion centers.
In these networks, due to various practical considerations
and limitations on resources including computational and
communication constraints, the fusion center which aggregates
information typically queries only a small subset of the
available sensors. This scenario, also known as the sensor
selection problem, arises in various applications in control
systems and signal processing including sensor selection for
Kalman filtering [1]–[3], batch state estimation and stochastic
process estimation [4], [5], minimal actuator placement [6],
[7], voltage control and meter placement in power networks
[8]–[10], sensor scheduling in wireless sensor networks [1],
[11], and subset selection in machine learning [12].
Although an optimal solution to the sensor selection problem can be achieved by means of branch-and-bound algorithms [13], this requires finding solution to a computationally
challenging combinatorial optimization problem which by a
reduction to the set cover problem is shown to be NP-hard
[14]. This in turn has motivated development of heuristics and
approximate algorithms. For instance, in [15], sensor selection
problem is formulated as the maximization (minimization) of
the log det of the Fisher information matrix (error covariance
matrix) and a semidefinite programming relaxation is proposed. The computational complexity of the SDP relaxation
is cubic in the number of sensors in the network which limits

practical feasibility of this scheme, especially for the modern
sensor networks characterized by a growing number of sensors
in the network. Additionally, the SDP relaxation does not
come with any performance guarantees. To overcome these
drawbacks, Shamaiah et al. [2] proposed a greedy algorithm
for the log det maximization formulation of the sensor selection problem whose complexity is lower than that of the
SDP relaxation. Since the log det of the Fisher information
matrix is a monotone submodular function, the greedy scheme
in [2] is a (1 − 1/e)-approximation algorithm. More recently,
the greedy algorithm for log det maximization was employed
and analyzed in a number of other practical settings [3]–
[5], [7]. All the prior work consider log det of the Fisher
information matrix which is related to the volume of the ηconfidence ellipsoid. However, this criterion is not explicitly
related to the mean-square error (MSE) which is often the
natural performance measure of interest in sensor selection and
state estimation problems. The MSE, i.e., the trace of the error
covariance matrix, is not supermodular [16], [17]. Therefore,
the search for an approximation algorithm with performance
guarantees on the estimator’s achievable MSE remains an open
research problem.
Sensor selection is related to the problem of maximizing a
monotone submodular function subject to a uniform matroid
constraint. Nemhauser et al. [18] considered this problem
and showed that the greedy algorithm that iteratively selects
items with maximum marginal gain provides a (1 − 1/e)approximation factor. In [12], a (1 − 1/e − ǫ)-approximation
stochastic-greedy algorithm is developed for the maximization
of monotone increasing submodular functions under cardinality constraint that reduces the complexity of the greedy
algorithm proposed in [18]. However, the assumption of submodularity in [12], [18] does not hold in the sensor selection
problem with MSE objective. Recently, Wang et al. [19] analyzed the performance of the greedy algorithm in the general
setting where the function is monotone non-decreasing, but
not necessarily submodular. They defined a total curvature
1
)µ and showed that the greedy algorithm provides a ( 1+µ
approximation under matroid constraint. However, determining the elemental curvature defined in [19] is itself an NP-hard
task. Therefore, finding an explicit approximation factor for
the settings where the objective function is not supermodular,
e.g., trace of the error covariance matrix in sensor scheduling
for state estimation via Kalman filtering, remains a challenge.
As we stated before, the natural objective function that is
typically of interest in sensor selection applications, the MSE,
is not submodular (or supermodular, in case one considers

2

the minimization formulation of the problem). Hence, the
performance guarantees for the greedy scheme derived in [18],
[20] no longer hold. Moreover, processing massive amounts
of data collected by modern large-scale networks may be
challenging even when relying on greedy algorithms. To
address these challenges, in this paper we formulate the task of
sensor selection in a large-scale sensor network as the problem
of maximizing a monotone non-submodular objective function
directly related to the MSE of the linear estimator of the states
in a linear dynamical system. By introducing the notion of
curvature c, we derive sufficient conditions under which the
objective function of the proposed framework is weak submodular. An implication of these results is that in the important
scenarios of Gaussian and Bernoulli measurement vectors
that frequently come up in dimensionality-reduced Kalman
filtering using random projections [21], the MSE objective
is with high probability weak submodular. Since state-of-theart sensor selection schemes based on greedy optimization
and SDP relaxation face computational burden in modern
sensor networks, we further 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 randomized greedy algorithm. Using
extensive simulations on real and synthetic data, we illustrate
that the proposed randomized greedy sensor selection scheme
significantly outperforms both greedy and SDP relaxation
methods in terms of runtime and computational complexity
while providing nearly equivalent or improved performance.
The rest of the paper is organized as follows. Section II
explains the system model. In Section III we present the novel
formulation of sensor selection problem and establish bound
on curvature of its MSE-related objective. In Section IV, we
introduce the randomized greedy algorithm and analyze its
performance. Section V presents the simulation results while
the concluding remarks are stated in Section VI. MATLAB
implementation of the proposed algorithm in this paper is
freely available at https://github.com/realabolfazl/RGSS.
Before proceeding to subsequent section, we first briefly
summarize the notation used in the paper. Bold capital letters
refer to matrices and bold lowercase letters represent vectors.
Hij denotes the (i, j) entry of H, hj is the j th row of H,
HS is a submatrix of H that contains rows indexed by set
S, and λmax (H) and λmin (H) are maximum and minimum
eigenvalues of H, respectively. Spectral (ℓ2 ) norm of a matrix
is denoted by k.k. In ∈ Rn×n is the identity matrix. Moreover,
let [n] := {1, 2, . . . , n}.
II. S YSTEM M ODEL AND P ROBLEM F ORMULATION
Consider a linear time-varying dynamical system and its
measurement model,
x(t + 1) = A(t)x(t) + w(t)
y(t) = H(t)x(t) + v(t),

(1)

where x(t) ∈ Rm is the state vector, y(t) ∈ Rn is the measurement vector, w(t) and v(t) are zero-mean Gaussian noises
with covariances Q(t) and R(t), respectively, A(t) ∈ Rm×m
is the state transition matrix and H(t) ∈ Rn×m is the matrix

whose rows at time t are the measurement vectors hi (t) ∈ Rm .
We assume that the states x(t) are uncorrelated with w(t) and
v(t). In addition, for simplicity of exposition we assume that
x(0) ∼ N (0, Σx ), Q(t) = σ 2 Im , and R(t) = σ 2 In .
Due to limited resources, fusion center aims to select k out
of n sensors and use their measurements to estimate the state
vector x(t) by minimizing the mean squared error (MSE) in
the Kalman filtering setting. Note that we assume that the
measurement vectors hi (t) are available at the fusion center.
Let Pt|t−1 and Pt|t be the prediction and filtered error
covariance at time instant t, respectively. Then
Pt|t−1 = A(t)Pt−1|t−1 A(t)⊤ + Q(t)
−1

−1
⊤
HSt (t)
Pt|t = P−1
,
t|t−1 + HSt (t) RSt (t)

where St is the set of selected sensors at time t and P0|0 = Σx .
Since R(t) = σ 2 In and the measurements are uncorrelated
across sensors, it holds that
−1

−1
Pt|t = Pt|t−1
+ σ −2 HSt (t)⊤ HSt (t)
= F−1
St
P
−1
where FSt = Pt|t−1 + σ −2 i∈St hi (t)hi (t)⊤ is the corresponding Fisher information matrix. Let
1
(2)
HSt (t)⊤ y(t)
x̂(t) = 2 F−1
σ St
be the linear minimum mean-square estimator (LMMSE) of
x(t). Then its MSE at time t is expressed by the trace of the
filtered error covariance matrix Pt|t . That is,
h
i

2
MSE = E x(t) − x̂t|t 2 = Tr F−1
(3)
St
where x̂t|t denotes the filtered estimate of the state vector at
time t. To minimize MSE (3) at each time step t the fusion
center seeks a solution to the following optimization problem:

min Tr F−1
s.t. S ⊂ [n], |S| = k.
(4)
S
S

The combinatorial optimization problem (4) is NP-hard by
a reduction to the well-known set cover problem [14]. Intuitively, the reason is that one needs to exhaustively search over
all schedules of k sensors to find the optimal solution. Using
the techniques established in [15] (although for a different
optimality criterion from MSE) an approximate solution, i.e.,
a schedule of sensors that results in a sub-optimal MSE, can
be found by the following SDP relaxation (see Appendix I for
the details of the derivation),
min Tr(Y)
z,Y

s.t.

0 ≤ zi ≤ 1, ∀i ∈ [n]
n
X
zi = k

(5)

i=1



Y
I

P−1
t|t−1

+σ

PIn
−2

⊤
i=1 zi hi (t)hi (t)



 0.

The complexity of the SDP algorithm scales as O(n3 ) which
is infeasible in practice. Furthermore, there is no guarantee
on the achievable MSE performance of the SDP relaxation.
When the number of sensors in a network and the size of the
state vector x(t) are relatively large, even the greedy algorithm
proposed in [2] may be computationally prohibitive.

3

III. P ROPOSED F ORMULATION BASED
W EAK S UBMODULARITY

ON

In this section, we propose a new formulation for optimizing
MSE in a sensor selection task for state estimation via Kalman
filtering in a sensor network by leveraging the idea of weak
submodularity. First, we overview some definitions that are
essential in the development of the proposed framework.
Definition 1. A set function f : 2X → R is monotone nondecreasing if f (S) ≤ f (T ) for all S ⊆ T ⊆ X.
Definition 2. A set function f : 2X → R is submodular if
f (S ∪ {j}) − f (S) ≥ f (T ∪ {j}) − f (T )

A closely related concept to submodularity is the notion
of curvature of a set function that quantifies how close the
function is to being submodular. Here, we define the elementwise curvature.
Definition 3. The element-wise curvature of a monotone nondecreasing function f is defined as
max

(S,T,i)∈Xl

fi (T )/fi (S),

(7)

where Xl = {(S, T, i)|S ⊂ T ⊂ X, i ∈ X\T, |T \S| =
l, |X| = n}. Furthermore, the maximum element-wise curn−1
vature is given by Cmax = maxl=1
Cl .
When Cmax > 1, f (S) is called a weak submodular set
function. Note that a set function is submodular if and only
if Cmax ≤ 1. Further, we say f (S) is weak submodular iff it
has a bounded Cmax .
Definition 4. Let X be a finite set and let I be a collection
of subsets of X. The pair M = (X, I) is a matroid if the
following properties hold:
• Hereditary property. If T ∈ I, then S ∈ I for all S ⊆ T .
• Augmentation property. If S, T ∈ I and |S| < |T |, then
there exists e ∈ T \S such that S ∪ {e} ∈ 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.
X

Given a monotone non-decreasing set function f : 2 → R
with f (∅) = 0, and a uniform matroid M = (X, I), we are
interested in the combinatorial problem
max f (S).
S∈I

(8)

S ⊂ [n], |S| = k.

(10)

where,
−1
F−1
S∪{j} = FS −

⊤ −1
F−1
S hj (t)hj (t) FS
.
−1
σ 2 + hj (t)⊤ FS hj (t)

Proof. See Appendix II.

(11)


Recall, as we stated it is shown that MSE is not supermodular [16], [17]. This immediately implies
that the proposed

objective f (S) = Tr Pt|t−1 − F−1
is
not
submodular
as it is
S
the additive inverse of MSE. However as we show in Theorem
1, under certain conditions, f (S) is characterized with a
bounded maximum element-wise curvature Cmax . Theorem 1
also states a probabilistic theoretical upper bound on Cmax in
scenarios where at each time step the measurement vectors
hj (t)’s are i.i.d. random vectors.
Before proceeding to Theorem 1 and its proof, we first state
the matrix Bernstein inequality [22] that will be used in the
proof of Theorem 1.
Lemma 1. (Theorem 6.6.1 in [22].) Let {Xℓ }nℓ=1 be a finite
collection of independent, random, Hermitian matrices in
Rm×m . Assume that for all ℓ ∈ [n],
E [Xℓ ] = 0,

λmax (Xℓ ) ≤ L.

Pn

Xℓ . Then, for all q > 0, it holds that


−q 2 /2
.
Pr{λmax (Y) ≥ q} ≤ m exp
k E [Y2 ] k + Lq/3

Let Y =

(12)

ℓ=1

(13)

We now proceed to the statement and proof of Theorem 1.
Theorem 1. Let Cmax be the maximum element-wise curvature of f (S), i.e., the objective function of sensor scheduling
problem and assume khj (t)k22 ≤ C for all j and t. Then, if
1
1
1
λmax (H(t)⊤ H(t)) ≤ −
σ2
φ λmin (Pt|t−1 )

Cmax ≤

Evidently, since Pt|t−1 is known, given the value of f (S) one
can easily infer the corresponding MSE of linear estimator
using subset S of sensors selected at time t. Then, we can
express the optimization problem in (4) as
S

hj (t)⊤ F−2
S hj (t)
,
σ 2 + hj (t)⊤ F−1
S hj (t)

(14)

for some 0 < φ < λmin (Pt|t−1 ), it holds that

Next, we establish the proposed framework. Let

f (S) = Tr Pt|t−1 − F−1
.
S

max f (S) s.t.

fj (S) =

(6)

for all subsets S ⊆ T ⊂ X and j ∈ X\T . The term fj (S) =
f (S ∪ {j}) − f (S) is the marginal value of adding element j
to set S.

Cl =

We now argue that (9) is indeed an instance of the general combinatorial problem (8). By defining X = [n] and
I = {S ⊂ X||S| = k}, it is easy to see that M = (X, I) is
a matroid. 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.

Proposition 1. Let f (S) = Tr Pt|t−1 − F−1
. Then, f (S)
S
is a monotonically increasing set function, f (∅) = 0, and

(9)

λmax (Pt|t−1 )2 (σ 2 + λmax (Pt|t−1 )C)
,
φ2 (σ 2 + φC)

(15)

Furthermore, if hj (t)’s are independent zero-mean random
vectors with covariance matrix σh2 Im such that for all j, σh2 <
C, for all q > 0 with probability


−q 2 /2
(16)
p ≥ 1 − m exp
(C − σh2 )(nσh2 + q/3)

4

it holds that
φ≥



1
nσh2 + q
+
λmin (Pt|t−1 )
σ2

−1

.

(17)

Proof. First, from the definition of element-wise curvature and
(10) we obtain that
2
⊤ −1
(hj (t)⊤ F−2
T hj (t))(σ + hj (t) FS hj (t))
−2
2
⊤ −1
(S,T,j)∈Xl (hj (t)⊤ F
S hj (t))(σ + hj (t) FT hj (t))
−1
2
2
λmax (F−2
T )(σ + λmax (FS )khj (t)k2 )
,
≤ max
(S,T,j)∈Xl λmin (F−2 )(σ 2 + λmin (F−1 )khj (t)k2
2)
S
T
(18)
where the last inequality follows from the Courant–Fischer
min-max theorem [23]. Notice that λmax (F−1
=
S )
λmin (FS )−1 and λmin (FT ) ≥ λmin (FS ) ≥ λmin (F∅ ) =
λmin (P−1
t|t−1 ). This fact, along with the definition of Cmax
implies

Cl =

max

λmax (Pt|t−1 )2 (σ 2 + λmax (Pt|t−1 )khj (t)k22 )
λmax (FS )−2 (σ 2 + λmax (FT )−1 khj (t)k22 )
2 2
2
(a) λmax (P
t|t−1 ) (σ + λmax (Pt|t−1 )khj (t)k2 )
≤
λmax (F[n] )−2 (σ 2 + λmax (F[n] )−1 khj (t)k22 )
2 2
(b) λmax (P
t|t−1 ) (σ + λmax (Pt|t−1 )C)
≤
,
λmax (F[n] )−2 (σ 2 + λmax (F[n] )−1 C)
(19)
where (a) follows from the fact that λmax (FS ) ≤
λmax (FT ) ≤ λmax (F[n] ) and (b) holds since
Cmax ≤

g(x) =

σ 2 + λmax (Pt|t−1 )x
σ 2 + λmax (F[n] )−1 x

≤

n
X
1
1
hj (t)hj (t)⊤ )
+ 2 λmax (
λmin (Pt|t−1 ) σ
j=1

1
1
λmax (H(t)⊤ H(t))
+
λmin (Pt|t−1 ) σ 2

(21)
Hence, by combining the condition (14) and (19), we obtain
the results stated in (15). Next, to obtain the expression for the
scenario of i.i.d random measurement vectors we now bound
λmax (F[n] ) using the matrix BernsteinPinequality [22]. Let
Xj = hj (t)hj (t)⊤ − σh2 Im and Y = nj=1 Xj . To use the
result of Lemma 1, one should find the quantities in (12). Note
that,
E[Xj ] = E[hj (t)hj (t)⊤ − σh2 Im ]
(22)
= E[hj (t)hj (t)⊤ ] − σh2 Im = 0.
This in turn implies that E[Y] = 0. Since Xj ’s are independent,
n
n
X
X
k E[X2j ]k
(23)
X2j ]k ≤
k E[Y2 ]k = k E[
j=1

λmax (Xj ) ≤ C − σh2 > 0.

(25)

We now establish an upper-bound for E[X2j ] as follows:


E[X2j ] = E[ hj (t)hj (t)⊤ − σh2 Im hj (t)hj (t)⊤ − σh2 Im ]

= khj (t)k22 − σh2 E[hj (t)hj (t)⊤ ]

− σh2 E[ hj (t)hj (t)⊤ − σh2 Im ]

= khj (t)k22 − σh2 σh2 Im  (C − σh2 )σh2 Im
(26)
where we have used the fact that E[Xj ] = 0. Thus, L = C−σh2
and k E[Y2 ]k ≤ n(C − σh2 )σh2 . Now, according to Lemma 1,
for all q > 0 it holds that Pr{λmax (Y) ≤ q} ≥ p where


−q 2 /2
.
(27)
p = 1 − m exp
(C − σh2 )(nσh2 + q/3)
Therefore,
λmax (F[n] ) ≤

1
nσh2 + q
= φ−1
+
λmin (Pt|t−1 )
σ2

(28)


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 [21] for more details). Such
sketching schemes give rise to the following important and
widely-used examples:
1) Multivariate Gaussian measurement vectors: Let
1
Im ) for all j. It is easy to show that
hj (t) ∼ N (0, m
E[khj (t)k22 ] = 1 for all j. Furthermore, it can be shown
that khj (t)k22 is with high probability distributed around
1
its expected value. Therefore, for this case, σh2 = m
and C = 1.
2) Centered Bernoulli measurement vectors: Let each entry
of hj (t) be set to ± √1m with equal probability. There1
since
fore, khj (t)k22 = 1 = C. Additionally, σh2 = m
the entries of hj (t) are i.i.d. zero-mean random variables
1
with variance m
.
The conditions stated in Theorem 1 can be interpreted as
conditions on the condition number of Pt|t−1 as explained
1
, we can
next. For sufficiently large m, and when σh2 = m
approximate C ≈ 1. Assume φ ≥ λmax (Pt|t−1 )/∆ for some
∆ > 1. Define
λmax (Pt|t−1 )
,
σ2

(29)

λmax (Pt|t−1 )
≥1
λmin (Pt|t−1 )

(30)

SNR =

j=1

by the linearity of expectation and triangle inequality. It just
remains to determine λmax (Xj ) and E[X2j ].

(24)

where hj (t)hj (t)⊤ − σh2 Im is the corresponding eigenvalue.
Since hj (t)hj (t)⊤ is a rank-1 matrix, other eigenvalues of Xj
are all equal to −σh2 . Hence,

with probability p. This completes the proof.
(20)

is a monotonically increasing function for x > 0. Now, since
the maximum eigenvalue of a positive definite matrix satisfies
the triangle inequality, we have
λmax (F[n] ) ≤

First, we verify hj is an eigenvector of Xj :

Xj hj = hj (t)hj (t)⊤ − σh2 Im hj

= khj (t)k22 − σh2 hj .

and let
κ=

5

Algorithm 1 Randomized Greedy Sensor Scheduling
1:
2:
3:
4:
5:

6:

Input: Pt|t−1 , Ht , k, ǫ.
Output: Subset St ⊆ [n] with |St | = k.
(0)
Initialize St = ∅, FS (0) = P−1
t|t−1 .
t
for i = 0, . . . , k − 1
Choose R by sampling s = nk log (1/ǫ) indices uni(i)
formly at random from [n]\St .
is = argmaxj∈R

hj (t)⊤ F−2
h (t)
(i) j
St

σ2 +hj (t)⊤ F−1
h (t)
(i) j

.

St

(i+1)
St

7:

Set

8:

F−1(i+1)
St

9:
10:

=

=

(i)
St

F−1(i)
St

∪ {is }.

−

F−1
h (t)his (t)⊤ F−1
(i) is
(i)
St

St

σ2 +his (t)⊤ F−1
h (t)
(i) is

end for
(k)
return St = St .

St

be the condition number of Pt|t−1 . Then, with some elementary numerical approximations we obtain the following
corollary.
Corollary 1.1. Assume
n
SNR,
m
for some c1 > 1. Then, with probability
n
p ≥ 1 − m exp(− c2 ),
m
∆ ≥ κ + c1

(31)

Remark 2: The parameter ǫ in Algorithm 1, e−k ≤ ǫ < 1,
denotes 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 greedy scheme. However,
as ǫ approaches 1, |R| and thus the overall computational
complexity decreases.
A. Performance Analysis of the Proposed Scheme
In this section we analyze performance and complexity
of 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 the maximization
(9).
Before stating the main results, we first provide two lemmas.
Lemma 2 upper-bounds the difference between the values
of the objective corresponding to two sets having different
cardinalities while Lemma 3 provides a lower bound on the
expected marginal gain.
n−1
Lemma 2. Let {Cl }l=1
be the element-wise curvatures of
f (S). Let S and T be any schedules of sensors such that
S ⊂ T ⊆ [n] with |T \S| = r. Then, it holds that
X
fj (S),
(33)
f (T ) − f (S) ≤ C(r)
j∈T \S

where C(r) = r1 (1 +
(32)

it holds that Cmax ≤ ∆3 for some c2 > 0.
Hence, informally, Theorem 1 states that for a wellconditioned Pt|t−1 , curvature of f (S) is small, implying
weak-submodularity of f (S). Furthermore, the probability
of such event is exponentially increasing in the number of
available measurements.
IV. R ANDOMIZED G REEDY S ENSOR S ELECTION
In the this section, we present a randomized greedy algorithm to approximately solve optimization problem (9) and
provide its performance guarantees.
Given prohibitive complexity of SDP relaxation and greedy
schemes for sensor scheduling in large-scale systems, to provide practical feasibility, inspired by the algorithm developed
in [12] that only works for submodular objectives, we propose
a computationally efficient randomized greedy algorithm (see
Algorithm 1) that finds an approximate solution to (9) with
a guarantee on its achievable MSE. Algorithm 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 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 used in the next iteration.
This procedure is repeated k times.

Pr−1
l=1

Cl ).

Proof. See Appendix III.



(i)
St

Lemma 3. Let
be the set of selected sensors at the end
of the ith iteration of Algorithm 1. Then
i 1 − ǫβ X
h
(i)
(i)
(i)
fj (St ), (34)
E f(i+1)s (St )|St ≥
k
(i)
j∈Ot \St

where Ot is the set of optimal sensors at time t, is is the index
s
−
of the selected sensor at the ith iteration, β = 1+max{0, 2n
1
n
},
and
s
=
log
(1/ǫ).
2(n−s)
k
Proof. See Appendix IV.



Theorem 2 below states that Algorithm 1 provides an
approximate solution to the sensor scheduling problem. In
particular, if f (S) is characterized by a bounded maximum
element-wise curvature, Algorithm 1 returns a subset of
sensors yielding an objective that is on average within a
multiplicative factor of the objective achieved by the optimal
schedule.
Theorem 2. Let Cmax be the maximum element-wise curvature of f (S), i.e., the objective function of sensor scheduling
problem in (9). Let St denote the schedule of sensors selected
by Algorithm 1 at time t, and let Ot be the optimum solution
of (9) such that |Ot | = k. Then f (St ) is on expectation a
multiplicative factor away from f (Ot ). That is,


ǫβ
1
f (Ot ),
(35)
E [f (St )] ≥ 1 − e− c −
c

where c = max{Cmax, 1}, e−k ≤ ǫ < 1, and β =
s
1
1 + max{0, 2n
− 2(n−s)
}. Furthermore, the computational

6

complexity of Algorithm 1 is O(nm2 log( 1ǫ )) where n is the
total number of sensors and m is the dimension of xt .
(i)

Proof. Consider St , the set generated at the end of the ith
(i)
iteration of Algorithm 1. Employing Lemma 2 with S = St
(i)
and T = Ot ∪ St , and using monotonicity of f yields
(i)

(i)

(i)

f (Ot ∪ St ) − f (St )
f (Ot ) − f (St )


Pr−1  ≤
Pr−1 
1
1
C
1
+
1
+
l
l=1
l=1 Cl
r
r
X
(i)
fj (St ),
≤

(36)

(i)

j∈Ot \St

(i)

where |Ot \St | = r. Now, using Lemma 3 we obtain
i
h
 f (Ot ) − f (St(i) )
(i)
(i)

E f(i+1)s (St )|St ≥ 1 − ǫβ
Pr−1  . (37)
k
1
+
l=1 Cl
r

Applying the law of total expectation yields
i
h
i
h
(i)
(i+1)
(i)
) − f (St )
E f(i+1)s (St ) = E f (St
h
i
(i)
f (Ot ) − E f (St )


≥ 1 − ǫβ
Pr−1  .
k
1
+
l=1 Cl
r

(38)

Using the definition of the maximum element-wise curvature,
we obtain
!
r−1
X
1
1
Cl ≤ (1 + (r − 1)Cmax ) = g(r).
1+
(39)
r
r
l=1

It is easy to verify, e.g., by taking the derivative, that g(r) is
decreasing (increasing) with respect to r if Cmax < 1 (Cmax >
1). Let c = max{Cmax , 1}. Then
!
r−1
X
1
1
1+
Cl ≤ (1 + (r − 1)Cmax ) ≤ c.
(40)
r
r
l=1

Hence,
h
i
h
i 1 − ǫβ 
(i)
(i+1)
(i)
f (Ot ) − E f (St ) .
E f (St
) − f (St ) ≥
kc
(41)
By induction and due to the fact that f (∅) = 0,

k !
1 − ǫβ
E[f (St )] ≥ 1 − 1 −
f (Ot ).
(42)
kc
Finally, using the fact that (1 + x)y ≤ exy for y > 0 and the
easily verifiable fact that eax ≤ 1 + axea for 0 < x < 1,


1−ǫβ
f (Ot )
E[f (St )] ≥ 1 − e− c


(43)
1
ǫβ
≥ 1 − e− c −
f (Ot ).
c
To take a closer look at computational complexity, note
that step 6 costs O( nk m2 log( 1ǫ )) as one needs to compute
n
1
2
k log( ǫ ) marginal gains, each with complexity O(m ). Step
2
8 requires O(m ) arithmetic operations. Since there are k such
iterations, running time of Algorithm 1 is O(nm2 log( 1ǫ )).
This completes the proof.


Using the definition of f (S) we obtain Corollary 2.1 stating
that, at each time step, the achievable mean-square error in (3)
obtained by forming an estimate using sensors selected by the
randomized greedy algorithm is within a factor of the optimal
mean-square error.
Corollary 2.1. Instate the notation and hypothesis of Theorem
1
2 and let α = 1 − e− c − cǫ . Let MSESt denote the meansquare estimation error obtained by forming an estimate using
information provided by the sensors selected by Algorithm 1 at
time t, and let MSEo be the optimal mean-square error formed
using information collected by optimum solution of (9). Then
the expected MSESt is bounded as
E [MSESt ] ≤ αMSEo + (1 − α)Tr(Pt|t−1 ).

(44)

Remark 3: Since the proposed scheme is a randomized
algorithm, Theorem 2 and Corollary 2.1 state that the expected
MSE associated with the solution returned by Algorithm 1
is a multiplicative factor α away from the optimal MSE.
Notice that, as we expect, α is decreasing in both c and ǫ.
If f (S) is characterized by a small curvature, then f (S) is
nearly submodular and randomized greedy algorithm delivers a
near-optimal scheduling. As we decrease ǫ, α increases which
in turn results in a better approximation factor. In the limit,
−k
1
if ǫ = e−k , then α = 1 − e− c − e c corresponds to the
approximation factor of the greedy algorithm. Notice that the
−k
negligible term − e c stems from the specific analysis that we
employed to treat the randomization step of Algorithm 1. In
1
fact, one can show α = 1 − e− c for the greedy algorithm by
following a similar argument as that of the classical analysis
given in [18].
Remark 4: The computational complexity of the greedy
method for sensor selection that utilizes the efficient recursions given in Proposition (1) to find the marginal gains is
O(knm2 ). Hence, our proposed scheme provides a reduction
in complexity by k/ log( 1ǫ ) which may be particularly beneficial in large-scale networks, as we illustrate in our simulation
results.
Next, we study the performance of the randomized greedy
algorithm using the tools of probably approximately correct
(PAC) learning theory [24]. The randomized selection step of
Algorithm 1 can be interpreted as approximating the marginal
gains of the selected sensors using a greedy scheme [2]. More
(i)
specifically, for the ith iteration it holds that fjrg (St ) =
(i)
(i)
ηt fjg (St ), where subscripts rg and g refer to the sensors
selected by the randomized greedy (Algorithm 1) and the
(i)
greedy algorithm, respectively, and ℓi (ǫ) ≤ ηt ≤ 1 for all
1
i ∈ [k] are random variables with mean µi (ǫ). In view of this
argument, we obtain Theorem 3 which states that if f (S) is
characterized by a bounded maximum element-wise curvature
(i)
and {ηt }ki=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.
1 Notice that ℓ (ǫ) and µ (ǫ) are time-varying quantities where the time
i
i
index is omitted for simplicity of the notation.

7

Theorem 3. Instate the notation and hypotheses of Theorem
(i)
2. Assume {ηt }ki=1 is a collection of random variables such
(i)
(i)
that ℓi (ǫ) ≤ ηt ≤ 1, and E[ηt ] = µi (ǫ) for all i and t. let
ℓmin (ǫ) = mini,t {ℓi (ǫ)} and µmin (ǫ) = mini,t {µi (ǫ)}. Then


ℓmin (ǫ)
(45)
f (Ot ),
f (St ) ≥ 1 − e− c
(i)

Furthermore, if {ηt }ki=1 are independent, for all 0 < q < 1,
with probability at least 1 − e−Ck it holds that


(1−q)µmin (ǫ)
c
f (St ) ≥ 1 − e−
f (Ot ),
(46)
for some C > 0.

(i)

Proof. Consider St , the set generated at the end of the
ith iteration of Algorithm 1 and let (i + 1)g and (i + 1)rg
denote the sensors selected by greedy and randomized greedy
algorithm at ith iteration, respectively. Let c = max{Cmax, 1}.
(i)
(i)
Employing Lemma 2 with S = St and T = Ot ∪ St , and
using monotonicity of f yields
(i)

(i)

(i)

f (Ot ) − f (St ) ≤ f (Ot ∪ St ) − f (St )
X
(i)
fj (St ).
≤c

(47)

(i)
j∈Ot \St

Using the fact that
(i)

(i)

(i)

fj (St ) ≤ f(i+1)rg (St ) ≤ f(i+1)g (St )

(48)

for all j, we obtain
(i)

(i)

f (Ot ) − f (St ) ≤ ckf(i+1)g (St ).

(49)

(i+1)

(i)

(i)

) − f (St ) = f(i+1)rg (St )
=

(i)
(i+1)
f(i+1)g (St ).
ηt

(50)

(i+1) 

η
(i)
(i+1)
(i)
f (Ot ) − f (St ) . (51)
f (St
) − f (St ) ≥ t
kc
Using a similar inductive argument as we did in the proof of
Theorem 2 and due to the fact that f (∅) = 0,
!!
k
(i)
X
ηt
f (St ) ≥ 1 − 1 −
f (Ot )
kc
i=1
(52)

(i) 
Pk
(a)
ηt
≥ 1 − e− i=1 kc f (Ot ),

where to obtain (a) we use the fact that (1 + x)y ≤ exy for
y > 0. To obtain the stated result, we apply the Bernstein’s
Pk
(i)
inequality [25] on the term i=1 ηt that is a sum of inde(i)
pendent random variables. Note that since {ηt } are bounded
random variables, by Popoviciu’s inequality [25] for all i ∈ [k]
it holds that
1
(i)
(53)
Var[ηt ] ≤ (1 − ℓi (ǫ))2 .
4
Hence, by Bernstein’s inequality for all 0 < q < 1
k
X
i=1

= e−C(ǫ,q)k
where (a) follows as p only increases by lower bounding µi (ǫ)
and ℓi (ǫ). Finally, employing this results in (52) yields


(1−q)µmin (ǫ)
c
f (Ot ),
(56)
f (St ) ≥ 1 − e−

with probability at least 1−eC(ǫ,q)k . This completes the proof.

Indeed, in simulation studies (see Section V) we empirically
verify the results of Theorems 2 and 3 and illustrate that
Algorithm 2 performs favorably compared to the competing
schemes both on average and for each individual sensor
scheduling tasks.
Similar to Corollary 2.1, we now obtain a probabilistic
bound on the achievable mean-square error in (3) at each
time step using the proposed randomized greedy algorithm,
as stated in Corollary 3.1 below.
Corollary 3.1. Instate the notation and hypotheses of Corollary 2.1 and Theorem 3. Let 0 < q < 1 and define
α = 1 − exp(− (1−q)µcmin (ǫ) ). Then, with probability at least
1 − e−Ck it holds that

(i)

ηt < (1 − q)

k
X
i=1

µi } < p

(57)

for some C > 0.
V. S IMULATION R ESULTS

Combining (49) and (50) yields

Pr{

!
Pk
(1 − q)2 ( i=1 µi (ǫ))2
p = exp − 1−q Pk
Pk
1
2
i=1 µi (ǫ) + 4
i=1 (1 − ℓi (ǫ))
3
!
(a)
(55)
k(1 − q)2 µ2min (ǫ)
≤ exp − 1−q
1
2
3 µmin (ǫ) + 4 (1 − ℓmin (ǫ))

MSESt ≤ αMSEo + (1 − α)Tr(Pt|t−1 ),

On the other hand,
f (St

where

(54)

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 below.
We consider the problem of Kalman filtering for state
estimation in a linear time-varying system. For simplicity, let
us assume that the system is in steady state and H = Im .
The initial state is a zero-mean Gaussian random vector with
covariance Σx = Im . We further specify zero-mean Gaussian
process and measurement noises with covariance matrices
Q = 0.05Im and R = 0.05In , respectively. At each time step,
the measurement vectors, i.e., the rows of the measurement
1
matrix H(t), are drawn according to N ∼ (0, m
Im ).
The MSE values and running time of each scheme is
averaged over 10 Monte-Carlo simulations. The time horizon
for each run is T = 10. The greedy and randomized greedy
algorithms are implemented in MATLAB while the SDP relaxation scheme is implemented via CVX [26]. 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 system having state dimension m =
50, the number of measurements n = 400, and k = 55, and
compare the MSE values of each method over the time horizon
of interest. For randomized greedy we set ǫ = 0.001. Fig. 1

8

8

8

7

7

6

6

5

5

4

4

3

3

2

2

1

1

0

0
2

4

6

8

10

12

14

16

18

20

60

70

Fig. 1: MSE comparison of randomized greedy, greedy, and SDP relaxation
sensor selection schemes employed in Kalman filtering.

80

(a)

90

100

110

100

110

MSE comparison

10 3

shows that the greedy method consistently yields the lowest
MSE while the MSE of the randomized greedy algorithm is
slightly higher. The MSE performance achieved by the SDP
relaxation is considerably larger than those of the greedy
and randomized greedy algorithms. The running time of each
method is given in Table I. Both the greedy algorithm and
the randomized greedy algorithm are much faster than the
SDP formulation. The randomized greedy scheme is nearly
two times faster than the greedy method. Note that, in this
Randomized Greedy
0.20 s

Greedy
0.38 s

SDP Relaxation
249.86 s

Table I: Running time comparison of randomized greedy, greedy, and SDP
relaxation sensor selection schemes (m = 50, n = 400, k = 55, ǫ = 0.001).

example, in each iteration of the sensor selection procedure
the randomized scheme only computes the marginal gain for
a sampled subset of size 50. As a comparison, the greedy
approach computes the marginal gain for all 400 sensors. In
summary, the greedy method yields the lowest MSE but is
much slower than the proposed randomized greedy algorithm.
To study the effect of the number of selected sensors on
performance, we vary k from 55 to 115 with increments of
10. The MSE values at the last time step (i.e., t = 10)
for each algorithm are shown in Fig. 2(a). As the number
of selected sensors increases, the estimation becomes more
accurate, as reflected by the MSE of each algorithm. Further,
the difference between the MSE values consistently decreases
as more sensors are selected. The running times shown in
Fig. 2(b) 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, 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
sizes of the system. The initial size was 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

10 2

10 1

10 0

10 -1

10 -2

60

70

(b)

80

90

Running time comparison

Fig. 2: Comparison of randomized greedy, greedy, and SDP relaxation
schemes as the number of selected sensors increases.

approach, we repeat experiments for ǫ ∈ {0.1, 0.01, 0.001}.
Note that the computational complexity of the SDP relaxation
scheme is prohibitive in this setting. Fig. 3(a) illustrates the
percentage difference of the MSE between the two methods.
In particular, we show
% ∆MSE =

MSERG − MSEG
× 100
MSEG

where “RG” and “G” refer to the randomized greedy and
greedy algorithms, respectively. It can be seen that this difference between the MSEs reduces as the system scales up. The
running time is plotted in Fig. 3(b). As the figure illustrates,
the gap between the running times grows with the size of
the system and the randomized greedy algorithm performs
nearly 25 times faster than the greedy method for the largest
network. Fig. 3 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.

9

interest to extend the framework established in this manuscript
to related problems such as minimal actuator placement.

25

20

A PPENDIX A
D ERIVATION OF SDP R ELAXATION OF (5)

15

Let zi ∈ {0, 1} indicate the membership of the ith sensor in
the selected subset at time t and define z = [z1 , z2 , . . . , zn ]⊤ .
Hence, (9) can be written as

!−1 
n
X

zi hi (t)hi (t)⊤
min Tr  P−1 + σ −2

10

5

0
2

4

6

8

10

(a)

12

14

16

18

z

t|t−1

s.t.

zi ∈ {0, 1}, ∀i ∈ [n]
n
X
zi = k.

20

i=1

i=1

∆ MSE

The convex relaxation of the above optimization problem is
given by

!−1 
n
X
−1

zi hi (t)hi (t)⊤
min Tr  Pt|t−1
+ σ −2

10 2

10 1

z

10

0

s.t.

10 -1

i=1

(58)

0 ≤ zi ≤ 1, ∀i ∈ [n]
n
X
zi = k.
i=1

10 -2

10 -3

2

4

6

8

10

12

14

16

18

20

In order to obtain an SDP in standard form, let Y be a positive
semidefinite matrix such that
!−1
n
X
−1
⊤
−2
(59)
zi hi (t)hi (t)
Y  Pt|t−1 + σ
i=1

(b)

Running time comparison

Fig. 3: A comparison of the randomized greedy and greedy algorithms for
varied network size.

Then, (58) can equivalently be written as
min

Tr(Y)

s.t.

0 ≤ zi ≤ 1, ∀i ∈ [n]
n
X
zi = k

z,Y

VI. C ONCLUSION
In this paper, we considered the problem of state estimation
in large-scale linear time-varying dynamical systems. We
proposed a randomized greedy algorithm for selecting sensors
to query such that their choice minimizes the estimator’s meansquare error at each time step. We established the performance guarantee for the proposed algorithm and analyzed its
computational complexity. To our knowledge, the proposed
scheme is the first randomized algorithm for sensor scheduling
with an explicit bound on its achievable mean-square error. In
addition, we provided a probabilistic theoretical bound on the
element-wise curvature of the objective function. Furthermore,
in simulations we demonstrated that the proposed algorithm is
superior to the classical greedy and SDP relaxation methods
in terms of running time while providing the same or better
utility.
As a future work, we intend to extend this approach to
nonlinear dynamical systems and obtain a theoretical guarantee on the quality of the resulting approximate solution found
by randomized greedy algorithm. Moreover, it would be of

i=1

Y−

P−1
t|t−1

+σ

−2

n
X
i=1

⊤

zi hi (t)hi (t)

!−1

0

(60)
Note that the expression on the left hand side of last constraint
in (60) can be thought of as the Schur complement [27] of the
block PSD matrix


Y
I
P
B=
.
(61)
n
−1
I Pt|t−1
+ σ −2 i=1 zi hi (t)hi (t)⊤

Since Schur complement of B is positive semidefinite if and
only if B  0, we obtain the SDP relaxation given in (5).
The solution to the SDP may take fractional values, in which
case some kind of sorting and rounding need to be employed
in order to obtain the desired solution. Here, we select the
sensors corresponding to the k zi ’s with largest values, as
originally suggested by [15].

10

A PPENDIX B
P ROOF OF P ROPOSITION 1
First, note that


f (∅) = Tr Pt|t−1 − F−1
= Tr Pt|t−1 − Pt|t−1 = 0.
∅

Now, for j ∈ [n]\S it holds that

fj (S) = f (S ∪ {j}) − f (S)



−1
= Tr Pt|t−1 − F−1
S∪{j} − Tr Pt|t−1 − FS



−1
= Tr F−1
−
Tr
F
S
S∪{j}


−1 
−1
= Tr FS − Tr FS + σ −2 hj (t)hj (t)⊤
 −1

FS hj (t)hj (t)⊤ F−1
(a)
S
= Tr
σ 2 + hj (t)⊤ F−1
S hj (t)
⊤ −2
hj (t) FS hj (t)
(b)
= 2
σ + hj (t)⊤ FS−1 hj (t)
(62)
where (a) is by applying matrix inversion lemma (Sherman–Morrison formula) [23] on (FS + σ −2 hj (t)hj (t)⊤ )−1 ,
and (b) is by properties of trace of a matrix. Finally, since FS
is a symmetric positive definite matrix, fj (S) > 0 which in
turn implies monotonicity.

(i)

MSE. Consider St , the set of selected sensors at the end of
(i)
ith iteration of Algorithm 1 and let Φ = R ∩(O\St ). It holds
2
that
!
s−1
(i)
Y
|O\St |
Pr{Φ = ∅} =
1−
(i)
|[n]\St | − l
l=0
!s
(i) s−1
(a)
|O\St | X
1
≤ 1−
(66)
(i)
s
l=0 |[n]\St | − l
!s
(i) s−1
(b)
|O\St | X 1
≤ 1−
s
n−l
l=0

where (a) is by the inequality of arithmetic and geometric
means, and (b) holds since |[n]\Si | ≤ n. Now recall for any
integer p,
p
X
1
= log p + γ + ζp
(67)
Hp =
p
l=1

where, Hp is the pth harmonic number, γ is the Eu1
− O( p14 ) is a monoler–Mascheroni constant, and ζp = 2p
tonically decreasing sequence related to Hurwitz zeta function
[28]. Therefore, using the identity (67) we obtain
(i)

A PPENDIX C
P ROOF OF L EMMA 2
Let S ⊂ T and T \S = {j1 , . . . , jr }. Therefore,
f (T ) − f (S) = f (S ∪ {j1 , . . . , jr }) − f (S)
= fj1 (S) + fj2 (S ∪ {j1 }) + . . .
+ fjr (S ∪ {j1 , . . . , jr−1 }). (63)
Applying definition of element-wise curvature yields
f (T ) − f (S) ≤ fj1 (S) + C1 fj2 (S) + · · · + Cr−1 fjr (S)
= fj1 (S) +

r−1
X

Cl fjt (S).

l=1

(64)
Note that (64) is invariant to the ordering of elements in
T \S. In fact, it is straightforward to see that given ordering
{j1 , . . . , jr }, one can choose a set P = {P1 , . . . , Pr } with r
permutations – e.g., by defining the right circular-shift operator
Pt ({j1 , . . . , jr }) = {jr−t+1 , . . . , j1 , . . . } for 1 ≤ t ≤ r –
such that Pp (j) 6= Pq (j) for p 6= q and ∀j ∈ T \S. Hence,
(64) holds for r such permutations. Summing all of these r
inequalities we obtain
!
r−1
X
X
fj (S).
(65)
r(f (T ) − f (S)) ≤ 1 +
Cl
l=1

j∈T \S

Rearranging (65) yields the desired result.
A PPENDIX D
P ROOF OF L EMMA 3
First, we aim to bound the probability of the event that the
random set R contains at least an index from the optimal set
of sensor as this is a necessary condition to reach the optimal

|O\St |
(Hn − Hn−s ))s
s
(i)
n
|O\St |
(log(
) + ζn − ζn−s ))s
= (1 −
s
n−s
(i)
(a)
|O\St |
n
s
≤ (1 −
(log(
)−
))s
s
n−s
2n(n − s)
(b)
(i)
s
s
≤ ((1 − )e 2n(n−s) )|O\St |
n
(68)
1
1
1
where (a) follows since ζn −ζn−s = 2n
− 2(n−s)
+O( (n−s)
4 ),
and (b) is by the fact that (1 + x)y ≤ exy for any real number
2
y > 0. Next, the fact that log(1 − x) ≤ −x− x2 for 0 < x < 1
yields
β1 s
s
s
(69)
(1 − )e 2n(n−s) ≤ e− n
n
Pr{Φ = ∅} ≤ (1 −

s
1
where β1 = 1 + ( 2n
− 2(n−s)
). On the other hand, we can
also upper bound Pr{Φ = ∅} as
!s
(i) s−1
|O\St | X 1
Pr{Φ = ∅} ≤ 1 −
s
n−l
l=0
!
s
(i)
(70)
|O\St |
≤ 1−
n
(i)

s

≤ e− n |O\St

|

where we again employed the inequality (1+x)y ≤ exy . Now,
let β = max{1, β1 }. Thus,
βs

(i)

Pr{Φ 6= ∅} ≥ 1 − e− n |O\St

|

≥

1 − ǫβ
(i)
(|O\St |)
k

(71)

2 Note that without loss of generality and for simplicity we assume that s
is an integer.

11

βs

by definition of s and the fact that 1 − e− n x is a concave
function. Finally, according to Lemma 2 in [12],
Pr{Φ 6= ∅} X
(i)
(i)
(i)
E[f(i+1)s (St )|St ] ≥
fo (St ). (72)
(i)
|O\St |
(i)
j∈Ot \St

Combining (71) and (72) yields the stated results.
R EFERENCES
[1] A. Nordio, A. Tarable, F. Dabbene, and R. Tempo, “Sensor selection and
precoding strategies for wireless sensor networks,” IEEE transactions on
signal processing, vol. 63, no. 16, pp. 4411–4421, Jun. 2015.
[2] M. Shamaiah, S. Banerjee, and H. Vikalo, “Greedy sensor selection:
Leveraging submodularity,” in Proceedings of Conference on Decision
and Control (CDC). IEEE, Dec. 2010, pp. 2572–2577.
[3] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Sensor placement for
optimal kalman filtering: Fundamental limits, submodularity, and algorithms,” in Proceedings of the American Control Conference (ACC).
IEEE, Jun. 2016, pp. 191–196.
[4] V. Tzoumas, N. A. Atanasov, A. Jadbabaie, and G. J. Pappas, “Scheduling nonlinear sensors for stochastic process estimation,” in Proceedings
of American Control Conference (ACC). IEEE, Jul. 2017, pp. 580–585.
[5] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Near-optimal sensor
scheduling for batch state estimation: Complexity, algorithms, and
limits,” in Proceedings of Conference on Decision and Control (CDC).
IEEE, Dec. 2016, pp. 2695–2702.
[6] T. H. Summers, F. L. Cortesi, and J. Lygeros, “On submodularity and
controllability in complex dynamical networks,” IEEE Transactions on
Control of Network Systems, vol. 3, no. 1, pp. 91–101, Mar. 2016.
[7] V. Tzoumas, M. A. Rahimian, G. J. Pappas, and A. Jadbabaie, “Minimal
actuator placement with optimal control constraints,” in Proceedings of
American Control Conference (ACC). IEEE, Jul. 2015, pp. 2081–2086.
[8] M. G. Damavandi, V. Krishnamurthy, and J. R. Martı́, “Robust meter
placement for state estimation in active distribution systems,” IEEE
Transactions on Smart Grid, vol. 6, no. 4, pp. 1972–1982, Feb. 2015.
[9] N. Gensollen, V. Gauthier, M. Marot, and M. Becker, “Submodular
optimization for control of prosumer networks,” in Proceedings of International Conference on Smart Grid Communications (SmartGridComm).
IEEE, Nov. 2016, pp. 180–185.
[10] Z. Liu, A. Clark, P. Lee, L. Bushnell, D. Kirschen, and R. Poovendran,
“Towards scalable voltage control in smart grid: A submodular optimization approach,” in Proceedings of the International Conference on
Cyber-Physical Systems (ICCPS). ACM, Apr. 2016, p. 20.
[11] M. Shamaiah, S. Banerjee, and H. Vikalo, “Greedy sensor selection
under channel uncertainty,” IEEE Wireless Communications Letters,
vol. 1, no. 4, pp. 376–379, Jun. 2012.

[12] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrak, and
A. Krause, “Lazier than lazy greedy,” in Proceedings of the Conference
on Artificial Intelligence. AAAI, Jan. 2015.
[13] W. J. Welch, “Branch-and-bound search for experimental designs based
on d optimality and other criteria,” Technometrics, vol. 24, no. 1, pp.
41–48, 1982.
[14] D. P. Williamson and D. B. Shmoys, The design of approximation
algorithms. Cambridge university press, 2011.
[15] S. Joshi and S. Boyd, “Sensor selection via convex optimization,” IEEE
Transactions on Signal Processing, vol. 57, no. 2, pp. 451–462, Oct.
2009.
[16] A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements
in Gaussian processes: Theory, efficient algorithms and empirical studies,” Journal of Machine Learning Research, vol. 9, pp. 235–284, Feb.
2008.
[17] A. Olshevsky, “On (non) supermodularity of average control energy,”
IEEE Transactions on Control of Network Systems, Apr. 2017.
[18] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of approximations for maximizing submodular set functions I,” Mathematical
Programming, vol. 14, no. 1, pp. 265–294, Dec. 1978.
[19] Z. Wang, B. Moran, X. Wang, and Q. Pan, “Approximation for maximizing monotone non-decreasing set functions with a greedy method,”
Journal of Combinatorial Optimization, vol. 31, no. 1, pp. 29–43, Jan.
2016.
[20] M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, “An analysis
of approximations for maximizing submodular set functions II,” in
Polyhedral combinatorics. Springer, Dec. 1978, pp. 73–87.
[21] D. Berberidis and G. B. Giannakis, “Data sketching for large-scale
Kalman filtering,” IEEE Transactions on Signal Processing, vol. 65,
no. 14, pp. 3688–3701, Jul. 2017.
[22] J. A. Tropp et al., “An introduction to matrix concentration inequalities,”
Foundations and Trends R in Machine Learning, vol. 8, no. 1-2, pp. 1–
230, May 2015.
[23] R. Bellman, Introduction to matrix analysis. SIAM, 1997.
[24] L. G. Valiant, “A theory of the learnable,” Communications of the ACM,
vol. 27, no. 11, pp. 1134–1142, Nov. 1984.
[25] R. V. Hogg and A. T. Craig, Introduction to mathematical statistics.
Upper Saddle River, New Jersey: Prentice Hall, 1995.
[26] M. Grant, S. Boyd, and Y. Ye, “CVX: Matlab software for disciplined
convex programming,” 2008.
[27] R. A. Horn and C. R. Johnson, Matrix analysis. Cambridge university
press, 2012.
[28] S. Lang, Algebraic number theory. Springer Science & Business Media,
2013, vol. 110.

