Sensor Placement for Optimal Kalman Filtering: Fundamental Limits, Submodularity, and
Algorithms✩
Vasileios Tzoumas∗, Ali Jadbabaie, George J. Pappas

arXiv:1509.08146v3 [math.OC] 31 Jan 2016

Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104-6228 USA

Abstract
In this paper, we focus on sensor placement in linear dynamic estimation, where the objective is to place a small number of sensors
in a system of interdependent states so to design an estimator with a desired estimation performance. In particular, we consider a
linear time-variant system that is corrupted with process and measurement noise, and study how the selection of its sensors affects
the estimation error of the corresponding Kalman filter over a finite observation interval. Our contributions are threefold: First, we
prove that the minimum mean square error of the Kalman filter decreases only linearly as the number of sensors increases. That is,
adding extra sensors so to reduce this estimation error is ineffective, a fundamental design limit. Similarly, we prove that the number
of sensors grows linearly with the system’s size for fixed minimum mean square error and number of output measurements over an
observation interval; this is another fundamental limit, especially for systems where the system’s size is large. Second, we prove
that the log det of the error covariance of the Kalman filter, which captures the volume of the corresponding confidence ellipsoid,
with respect to the system’s initial condition and process noise is a supermodular and non-increasing set function in the choice of
the sensor set. Therefore, it exhibits the diminishing returns property. Third, we provide efficient approximation algorithms that
select a small number sensors so to optimize the Kalman filter with respect to this estimation error —the worst-case performance
guarantees of these algorithms are provided as well. Finally, we illustrate the efficiency of our algorithms using the problem of
surface-based monitoring of CO2 sequestration sites studied in Weimer et al. (2008).
Keywords: Least-Squares Linear Estimator, Process and Measurement Noise, Minimal Sensor Placement, Greedy Algorithms.

1. Introduction

sor measurements (Kailath et al. (2000)) and, as a result, we
consider the presence of measurement noise.
In this paper, we aim to monitor dynamic, interdependent
Specifically, we consider phenomena modelled as linear tiphenomena, that is, phenomena with temporal and spatial corme-variant systems corrupted with process and measurement
relations —with the term “spatial” we refer to any kind of internoise. Our first goal is to study how the placement of their sendependencies between the phenomena. For example, the temsors affects the minimum mean square error of their Kalman
perature at any point of an indoor environment depends across
filter over a finite observation interval (Kailath et al. (2000)).
time —temporal correlation— on the temperatures of the adjaMoreover, we aim to select a small number of sensors so to
cent points —spatial correlation (Madsen & Holst (1995)). There- minimize the volume of the corresponding confidence ellipsoid
fore, these correlations allow to monitor such phenomena usof this estimation error. Thereby, this study is an important dising a reduced number of sensors; this is an important observatinction in the minimal sensor placement literature (Clark et al.
tion when operational constraints, such as limited bandwidth
(2012); Lin et al. (2013); Olshevsky (2014); Pequito et al. (2014);
and communication power, necessitate the design of estimaPasqualetti et al. (2014); Summers et al. (2014); Tzoumas et al.
tors using a small number of sensors (Rowaihy et al. (2007);
(2015); Matni & Chandrasekaran (2014); Pequito et al. (2015);
Hero III & Cochran (2011)). Hence, in this paper we consider
Tzoumas et al. (July 2015); Yan et al. (2015); Zhao & Cortés (2015)),
to place a few sensors so to monitor this kind of phenomena. To
since the Kalman filter is the optimal linear estimator —in the
this end, we also account for unknown interdependencies and
minimum mean square sense— given a sensor set (Kalman (1960)).
inputs in their dynamics (Bertsekas (2005)) and, as a result, we
Our contributions are threefold:
consider the presence of process noise, i.e., noise that affects
directly these dynamics. In addition, we account for noisy senFundamental limits. First, we identify fundamental limits in
the design of the Kalman filter with respect to its sensors. In
particular, given a fixed number of output measurements over
✩ This paper was not presented at any IFAC meeting. Some of the results in
any finite observation interval, we prove that the minimum mean
this paper will appear in preliminary form in Tzoumas et al. (2016).
∗ Corresponding author. Tel.: +1 (215) 898 5814; fax: +1 (215) 573 2048.
square error of the Kalman filter decreases only linearly as the
Email addresses: vtzoumas@seas.upenn.edu (Vasileios Tzoumas),
number of sensors increases. That is, adding extra sensors so to
jadbabai@seas.upenn.edu (Ali Jadbabaie),
reduce this estimation error of the Kalman filter is ineffective,
pappasg@seas.upenn.edu (George J. Pappas)
Preprint submitted to Elsevier

February 2, 2016

a fundamental design limit. Similarly, we prove that the number of sensors grows linearly with the system’s size for fixed
minimum mean square error; this is another fundamental limit,
especially for systems where the system’s size is large. On the
contrary, given a sensor set of fixed cardinality, we prove that
the number of output measurements increases only logarithmically with the system’s size for fixed estimation error. Overall,
our novel results quantify the trade-off between the number of
sensors and that of output measurements so to achieve a specified value for the minimum mean square error.
These results are the first to characterize the effect of the
sensor set on the minimum mean square error of the Kalman filter. In particular, in Pasqualetti et al. (2014), the authors quantify only the trade-off between the total energy of the consecutive output measurements and the number of its selected sensors. Similarly, in Yan et al. (2015), the authors consider only
the maximum-likelihood estimator for the system’s initial condition and only for a special class of stable linear time-invariant
systems. Moreover, they consider systems that are corrupted
merely with measurement noise, which is white and Gaussian.
Finally, they also assume an infinite observation interval, that is,
infinite number of consecutive output measurements. Nonetheless, we assume a finite observation interval and study the Kalman
estimator both for the system’s initial condition and for the system’s state at the time of the last output measurement. In addition, we consider general linear time-variant systems that are
corrupted with both process and measurement noise, of any distribution (with zero mean and finite variance). Overall, our results characterize the effect of the cardinality of the sensor set
on the minimum mean square error of the Kalman filter, that is,
the optimal linear estimator.

Algorithms. Third, we consider two problems of sensor placement so to optimize the log det of the error covariance of the
Kalman filter with respect to the system’s initial condition and
process noise of Kalman estimator —henceforth, we refer to
this error as log det error. First, we consider the problem of
designing an estimator that guarantees a specified log det error
and uses a minimal number of sensors —we refer to this problem as P1 . Second, we consider the problem of designing an
estimator that uses at most r sensors and minimizes the log det
error —we refer to this problem as P2 . Naturally, P1 and P2 are
combinatorial, and in particular, they involve the minimization
of the supermodular log det error. Because the minimization
of a general supermodular function is NP-hard (Feige (1998)),
we provide efficient approximation algorithms for their general
solution, along with their worst-case performance guarantees.
Specifically, we first provide an efficient algorithm for P1 that
returns a sensor set that satisfies the estimation guarantee of
P1 and has cardinality up to a multiplicative factor from the
minimum cardinality sensor sets that meet the same estimation
bound. More importantly, this multiplicative factor depends
only logarithmically on the problem’s P1 parameters. Next, we
provide an efficient algorithm for P2 that returns a sensor set of
cardinality l ≥ r (l is chosen by the designer) and achieves a
near optimal value for increasing l. Specifically, for l = r, it
achieves a worst-case approximation factor 1 − 1/e.2
In comparison, the related literature has focused either a) on
only the optimization of the log det error for special cases of
systems with zero process noise, or b) on heuristic algorithms
that provide no worst-case performance guarantees, or c) on
static phenomena. In particular, in Joshi & Boyd (2009), the
authors minimize the log det error for the case where there is
no process noise in the system’s dynamics —we assume both
process and measurement noise. Moreover, to this end they use
convex relaxation techniques that provide no performance guarantees. Furthermore, in Dhingra et al. (2014) and Munz et al.
(2014), the authors design an H2 -optimal estimation gain with
a small number of non-zero columns. To this end, they also
use convex relaxation techniques that provide no performance
guarantees. In addition, in Belabbas (2015), the author designs
an output matrix with a desired norm so to minimize the minimum mean square error of the corresponding Kalman estima-

Submodularity. Second, we identify properties for the log det
of the error covariance of the Kalman filter, which captures the
volume of the corresponding confidence ellipsoid, with respect
to the system’s initial condition and process noise over a finite
observation interval as a sensor set function —the design of an
optimal Kalman filter with respect to the system’s initial condition and process noise implies the design of an optimal Kalman
filter with respect to the system’s state. Specifically, we prove
that it is a supermodular and non-increasing set function in the
choice of the sensor set.
In Krause et al. (2008), the authors study sensor placement
counterexample in the context of sensor scheduling that the minimum mean
for monitoring static phenomena with only spatial correlations.
square error of the Kalman filter with respect to the system’s state is not in
To this end, they prove that the mutual information between
general a supermodular set function. We can extend this counterexample in the
the chosen and non-chosen locations is submodular. Notwithcontext of minimal sensor placement as well: the minimum mean square error
of the Kalman with respect to the system’s state is not in general a supermodular
standing, we consider dynamic phenomena with both spatial
set function with respect to the choice of the sensor set.
and temporal correlations, and as a result, we characterize as
2 Such algorithms, that involve the minimization of supermodular set
submodular a richer class of estimation performance metrics.
functions, are also used in the machine learning (Krause & Guestrin), path
Furthermore, in the sensor scheduling literature (Gupta et al.
planning for information acquisition (Singh et al. (2009); Atanasov et al.
(2014)), leader selection (Clark et al. (2012, 2014b,a)), sensor scheduling
(2006)), the log det of the error covariance of the Kalman filter
(Shamaiah et al. (2010); Jawaid & Smith (2015); Zhang et al. (2015)), achas been proven submodular but only for special cases of systuator placement (Olshevsky (2014); Summers et al. (2014); Tzoumas et al.
tems with zero process noise (Shamaiah et al. (2010); Jawaid & Smith
(2015); Tzoumas et al. (July 2015,D); Zhao & Cortés (2015)) and sensor place(2015)); in contrast, we consider the presence of process noise,
ment in static phenomena (Krause et al. (2008); Jiang et al. (2015)) literature. Their popularity is due to their simple implementation —they are
and prove our result for the general case. 1
1 In

greedy algorithms— and provable worst-case approximation factors, that are
the best one can achieve in polynomial time for several classes of functions
(Nemhauser & Wolsey (1978); Feige (1998)).

Jawaid & Smith (2015); Zhang et al. (2015), the authors prove with a

2

where xk ∈ Rn (n ∈ N) is the state vector, yk ∈ Rc (c ∈ [n])
the output vector, wk the process noise and vk the measurement
noise —without loss of generality, the input vector in (1) is assumed zero. The initial condition is x0 .

tor; nonetheless, the author does not minimize the number of
selected sensors. Finally, in Das & Kempe (2008), the authors
consider the problem of sensor placement for monitoring static
phenomena with only spatial correlation. To this end, they
place a small number of sensors so to minimize a worst-case
estimation error of an aggregate function, such as the average.
In contrast, we consider dynamic phenomena with both spatial
and temporal correlations, and we minimize the log det error of
the Kalman filter; as a result, we do not focus on a worst-case
estimation error, and we can efficiently estimate any function.
Overall, in this paper we optimize the log det error for the general case of dynamic systems and, at the same time, we provide
worst-case performance guarantees for the corresponding algorithms.
The remainder of this paper is organized as follows. In Section 2, we introduce our model, and our estimation and sensor
placement framework, along with our sensor placement problems. In Section 3, we provide a series of design and performance limits and characterize the properties of the Kalman estimator with respect to its sensor set; in Section 4, we prove that
the log det estimation error of the Kalman filter with respect to
the system’s initial condition and process noise is a supermodular and non-increasing set function in the choice of the sensor
set; and in Section 5, we provide efficient approximation algorithms for selecting a small number of sensors so to design
an optimal Kalman filter with respect to its log det error —the
worst-case performance guarantees of these algorithms are provided as well. Finally, in Section 6, we illustrate our analytical
findings, and test the efficiency of our algorithms, using simulation results from an integrator chain network and the problem
of surface-based monitoring of CO2 sequestration sites studied
in Weimer et al. (2008). Section 7 concludes the paper.

Assumption 1 (For all k ≥ 0, the initial condition, the process
noise and the measurement noise are uncorrelated random variables). x0 is a random variable with covariance C(x0 ) ≻ 0.
Moreover, for all k ≥ 0, C(wk ) ≻ 0 and C(vk ) = σ 2 I, where
σ > 0. Finally, for all k, k ′ ≥ 0 such that k 6= k ′ , x0 , wk and
vk , as well as, wk , wk′ , vk and vk′ , are uncorrelated.3
Moreover, for k ≥ 0, consider the vector of measurements
ȳk , the vector of process noises w̄k and the vector of measurement noises v̄k , defined as follows: ȳk ≡ (y0⊤ , y1⊤ , . . . , yk⊤ )⊤ ,
w̄k ≡ (w0⊤ , w1⊤ , . . . , wk⊤ )⊤ , and v̄k ≡ (v0⊤ , v1⊤ , . . . , vk⊤ )⊤ , respectively; the vector ȳk is known, while the w̄k and v̄k are not.
Definition 1 (Observation interval and its length). The interval
[0, k] ≡ {0, 1, . . . , k} is called the observation interval of (1).
Moreover, k + 1 is its length.
Evidently, the length of an observation interval [0, k] equals
the number of measurements y0 , y1 , . . . , yk .
In this paper, given an observation interval [0, k], we consider the minimum mean square linear estimators for xk′ , for
any k ′ ∈ [0, k] (Kailath et al. (2000)). In particular, (1) implies
ȳk = Ok zk−1 + v̄k ,

⊤
⊤ ⊤
where Ok is the c(k+1)×n(k+1) matrix [L⊤
0 C0 , L1 C1 , . . . ,
⊤ ⊤ ⊤
Lk Ck ] , L0 the n × n(k + 1) matrix [I, 0], Li , for i ≥ 1, the
n× n(k + 1) matrix [Ai−1 · · · A0 , Ai−1 · · · A1 , . . . , Ai−1 , I, 0],
⊤
⊤
and zk−1 ≡ (x⊤
0 , w̄k−1 ) . As a result, the minimum mean
square linear estimate of zk−1 is the ẑk−1 ≡ E(zk−1 )+C(zk−1 )
−1
Ok⊤ Ok C(zk−1 )Ok⊤ + σ 2 I
(ȳk − Ok E(zk−1 ) − E(v̄k )); its
error covariance is

Σzk−1 ≡ E (zk−1 − ẑk−1 )(zk−1 − ẑk−1 )⊤

2. Problem Formulation
Notation. We denote the set of natural numbers {1, 2, . . .} as
N, the set of real numbers as R, and the set {1, 2, . . . , n} as [n],
where n ∈ N. Given a set X , |X | is its cardinality. Matrices
are represented by capital letters and vectors by lower-case letters. For a matrix A, A⊤ is its transpose and Aij its√element
located at the i−th row and j−th column. kAk2 ≡ A⊤ A is
its spectral norm, and λmin (A) and λmax (A) its minimum and
maximum eigenvalues, respectively. Moreover, if A is positive
semi-definite or positive definite, we write A  0 and A ≻ 0,
respectively. Furthermore, I is the identity matrix —its dimension is inferred from the context; similarly for the zero matrix
n
0. Finally, for a random
 variable x ∈ R , E(x) is its expected
value, and C(x) ≡ E [x − E(x)] [x − E(x)]⊤ its covariance.
The rest of our notation is introduced when needed.

= C(zk−1 ) − C(zk−1 )Ok⊤
−1
Ok C(zk−1 )Ok⊤ + σ 2 I
Ok C(zk−1 )


mmse(zk−1 ) ≡ E (zk−1 − ẑk−1 )⊤ (zk−1 − ẑk−1 )

= tr Σzk−1 .

(4)

As a result, the corresponding minimum mean square linear estimator of xk′ , for any k ′ ∈ [0, k], is
x̂k′ = Lk′ ẑk−1 ,
(since xk′ = Lk′ zk−1 ), with minimum mean square error

mmse(xk′ ) ≡ tr Lk′ Σzk−1 L⊤
k′ .

For k ≥ 0, we consider the linear time-variant system
yk = Ck xk + vk ,

(3)

and its minimum mean square error

2.1. Model and Estimation Framework

xk+1 = Ak xk + wk ,

(2)

(5)

(6)

3 This assumption is common in the related literature (Joshi & Boyd (2009)),
and it translates to a worst-case scenario for the problem we consider in this
paper.

(1)

3

In particular, the recursive implementation of (5) results to the
Kalman filtering algorithm (Bertsekas (2005)).
In this paper, in addition to the minimum mean square error of x̂k′ , we also consider per (5) the estimation error metric that is related to the η-confidence ellipsoid of zk−1 − ẑk−1
(Joshi & Boyd (2009)). Specifically, this is the minimum volume ellipsoid that contains zk−1 − ẑk−1 with probability η, that
(η) and
is, the Eǫ ≡ {z : z ⊤ Σzk−1 z ≤ ǫ}, where ǫ ≡ Fχ−1
2

Objective 1 (Fundamental limits in optimal sensor placement).
Given an observation interval [0, k], i ∈ {0, k} and a desired
mmse(xi ), identify fundamental limits in the design of the sensor set.
As an example of a fundamental limit, we prove that the
number of sensors grows linearly with the system’s size for
fixed estimation error mmse(xi ) —this is clearly a major limitation, especially when the system’s size is large. This result, as
well as, the rest of our contributions with respect to Objective
1, is presented in Section 3.

n(k+1)

Fχ2n(k+1) is the cumulative distribution function of a χ-squared
random variable with n(k + 1) degrees of freedom (Venkatesh
(2012)). Therefore, the volume of Eǫ ,


(ǫπ)n(k+1)/2
det Σ1/2
vol(Eǫ ) ≡
zk−1 ,
Γ (n(k + 1)/2 + 1)

Objective 2 (log det estimation error as a sensor set function).
Given an observation
interval [0, k], identify properties of the

log det Σzk−1 as a sensor set function.

(7)

We addressthis objective in Section 4, where we prove that
log det Σzk−1 is a supermodular and non-increasing set function with respect to the choice of the sensor set —the basic definitions of supermodular set functions are presented in that section as well.

where Γ(·) denotes the Gamma function (Venkatesh (2012)),
quantifies the estimation’s error of ẑk−1 , and as a result, for any
k ′ ∈ [0, k], of x̂k′ as well, since per (5) the optimal estimator
for zk−1 defines the optimal estimator for xk′ .
Henceforth, we consider the logarithm of (7),

(8)
log vol(Eǫ ) = β + 1/2 log det Σzk−1 ;

Objective 3 (Algorithms for optimal sensor placement). Given
an observation interval [0, k], identify a sensor set S that solves
either the minimal sensor placement problem:

β is a constant that depends only on n(k + 1) and ǫ, in accor
dance to (7), and as a result, we refer to the log det Σzk−1 as
the log det estimation error of the Kalman filter of (1):

minimize
S⊆[n]

subject to

Definition 2 (log det estimation error of the Kalman filter).
Given an observation interval [0, k], the log det Σzk−1 is called the log det estimation error of the Kalman filter of (1).

|S|

log det Σzk−1 ≤ R;

(P1 )

or the cardinality-constrained sensor placement problem for minimum estimation error:

minimize log det Σzk−1
S⊆[n]
(P2 )
subject to |S| ≤ r.

In the following paragraphs, we present our sensor placement framework, that leads to our sensor placement problems.
2.2. Sensor Placement Framework
In this paper, we study among others the effect of the selected sensors in (1) on mmse(x0 ) and mmse(xk ). Therefore,
this translates to the following conditions on Ck , for all k ≥
0, in accordance with the minimal sensor placement literature
(Olshevsky (2014)).

That is, with P1 we design an estimator that guarantees
a specified error and uses a minimal number of sensors, and
with P2 an estimator
that uses at most r sensors and minimizes

log det Σzk−1 . The corresponding algorithms are provided in
Section 5.

Assumption 2 (C is a full row-rank constant zero-one matrix).
For all k ≥ 0, Ck = C ∈ Rc×n , where C is a zero-one constant
matrix. Specifically, each row of C has one element equal to
one, and each column at most one, such that C has rank c.

3. Fundamental Limits in Optimal Sensor Placement
In this section, we present our contributions with respect to
Objective 1. In particular, given any finite observation interval,
we prove that the minimum mean square error decreases only
linearly as the number of sensors increases. That is, adding extra sensors so to reduce the minimum mean square estimation
error of the Kalman filter is ineffective, a fundamental design
limit. Similarly, we prove that the number of sensors grows
linearly with the system’s size for fixed minimum mean square
error; this is another fundamental limit, especially for systems
where the system’s size is large. On the contrary, given a sensor
set of fixed cardinality, we prove that the length of the observational interval increases only logarithmically with the system’s
size for fixed minimum mean square error. Overall, our novel
results quantify the trade-off between the number of sensors and

In particular, when for some i, Cij is one, the j-th state of
xk is measured; otherwise, it is not. Therefore, the number of
non-zero elements of C coincides with the number of placed
sensors in (1).
Definition 3 (Sensor set and sensor placement). Consider a C
per Assumption 2 and define S ≡ {i : i ∈ [n] and Cji =
1, for some j ∈ [r]}; S is called a sensor set or a sensor placement and each of its elements a sensor.
2.3. Sensor Placement Problems
We introduce three objectives, that we use to define the sensor placement problems we consider in this paper.
4

at least as large as their harmonic mean, using (12),

that of output measurements so to achieve a specified value for
the minimum mean square error.
To this end, given i ∈ {0, k}, we first determine a lower and
upper bound for mmse(xi ).4

mmse(x0 ) ≥

Theorem 1 (A lower and upper bound for the estimation error with respect to the number of sensors and the length of
the observation interval). Consider a sensor set S, any finite
observation interval [0, k], and a non-zero σ. Moreover, let
µ ≡ maxm∈[0,k] kAm k2 and assume µ 6= 1. Finally, denote the
maximum diagonal element of C(x0 ), C(x0 )−1 , and C(wk′ ),
2
among all k ′ ∈ [0, k], as σ02 , σ0−2 , and σw
, respectively. Given
i ∈ {0, k},
|S| 1 −

nσ 2 li

≤ mmse(xi ) ≤ nui ,
/ (1 − µ2 ) + σ 2 σ0−2
(9)

n2 σ 2

.
tr Õk + nσ 2 σ0−2


2(k+1)

n|S| 1−µ
, and as a result, the lower bound in (9) for mmse(x0 )
1−µ2
follows.
Next, we prove the upper bound in (9), using (18), which is
proved in the proof of Proposition 1, and (6) for k ′ = 0: Ok +
σ 2 C(zk−1 )−1  σ 2 C(zk−1 )−1 , and as a result, from Propo−1
sition 8.5.5 of Bernstein (2009), Ok + σ 2 C(zk−1 )−1


2
σ −2 C(zk−1 ). Hence, mmse(x0 ) ≤ tr L0 C(zk−1 )L⊤
0 ≤ nσ0 .
Finally, to derive the lower and upper bounds for mmse(xk ),
observe that mmse(x0 ) ≤ mmse(zk−1 ) and mmse(zk−1 ) ≤
2
n(k + 1) max(σ02 , σw
) —the proof follows using similar steps
as above. Then, from Theorem 1 of Fang et al. (1994),

λmin L⊤
k Lk mmse(zk−1 ) ≤mmse(xk ) ≤

λmax L⊤
k Lk mmse(zk−1 ).


where l0 = 1, u0 = σ02 , lk = λmin L⊤
k Lk and uk = (k +
2
2
1)λmax L⊤
k Lk max(σ0 , σw ).

Proof. We first prove the lower bound in (9): observe first
that mmse(x0 ) ≥ mmse(x0 )w· =0 , where mmse(x0 )w· =0 is the
minimum mean square error of x0 when the process noise wk
in (1) is zero for all k ≥ 0. To express mmse(x0 )w· =0 in a
closed form similar to (15), note that in this case (2) becomes


⊤
⊤ ⊤ ⊤
ȳk = Õk x0 + v̄k , where Õk ≡ C0⊤ , Φ⊤
1 C1 , . . . , Φk Ck
and Φm ≡ Am−1 · · · A0 , for m > 0, and Φm ≡ I, for m = 0.
Thereby, from Corollary E.3.5 of Bertsekas (2005), the mini· =0
, has
mum mean square linear estimate of x0 , denoted as x̂w
k0
error covariance

· =0 ⊤
· =0
· =0
)
)(x0 − x̂w
≡ E (x0 − x̂w
Σw
k0
k0
k0

and minimum mean square error

· =0
mmse(x0 )w· =0 ≡ tr Σw
k0

−1 
2
⊤
2
−1
= σ tr Õk Õk + σ C(x0 )

−1 
,
≡ σ 2 tr Õk + σ 2 C(x0 )−1

tr Õk + σ 2 C(x0 )−1

 ≥

Now, for i ∈ [n], let I (i) be the n × n matrix where Iii is
one,
(j, k) 6= (i,
i). Then, tr(Õk ) 
=
 all P
P
Pwhile Ijk is zero, for
n
k
k
⊤ (i)
⊤ ⊤
=
tr
Φm I Φm ;
i=1 si tr
m=0 Φm C CΦm

P m=0

P
k
k
⊤ (i)
⊤ (i)
=
Φ
I
Φ
≤
nλ
now, tr
Φ
I
Φ
m
max
m
m=0 m
m=0 m
Pk
Pk
2
(i)
⊤ (i)
nk m=0 Φm I Φm k2 ≤ n m=0 kΦm k2 , because kI k2 =
1, and from the definition of Φm and Proposition 9.6.1 of Bernstein
Pk
Pn
2(k+1)
2
(2009), m=0 kΦm k22 ≤ 1−µ
. Therefore, tr(Õk ) ≤ i=1 si n 1−µ
1−µ2
1−

µ2(k+1)

= C(x0 ) − C(x0 )Õk⊤

−1
Õk C(x0 )Õk⊤ + σ 2 I
Õk C(x0 ),

n2 σ 2


The combination of these inequalities completes the proof.

The upper bound corresponds to the case where no sensors
have been placed (C = 0). On the other hand, the lower bound
corresponds to the case where |S| sensors have been placed.
As expected, the lower bound in (9) decreases as the number
of sensors or the length of the observational interval increases;
the increase of either should push the estimation error downwards. Overall, this lower bound quantifies fundamental performance limits in the design of the Kalman estimator: first,
this bound decreases only inversely proportional to the number
of sensors. Therefore, the estimation error of the optimal linear
estimator decreases only linearly as the number of sensors increases. That is, adding extra sensors so to reduce the minimum
mean square estimation error of the Kalman filter is ineffective,
a fundamental design limit. Second, this bound increases linearly with the system’s size. This is another fundamental limit,
especially for systems where the system’s
size is large. Finally,

,
these
scaling extend to
L
for fixed and non-zero λmin L⊤
k k
the mmse(xk ) as well, for any finite k.

(10)

(11)
(12)

where we deduce (11) from (10) using the Woodbury matrix
identity (Corollary 2.8.8 of Bernstein (2009)), and (12) from
(11) using the notation Õk ≡ Õk⊤ Õk . In particular, Õk is the
Pk−1 ⊤ ⊤
observability matrix Õk = m=0
Φm Ck Ck Φm of (1) (Chen
(1998)).

−1 
2
2
−1
Hence, mmse(x0 ) ≥ σ tr Õk + σ C(x0 )
, and

Corollary 1 (Trade-off among the number of sensors, estimation error and the length of the observation interval). Consider
any finite observation interval [0, k], a non-zero σ, and for i ∈
{0, k}, that the desired value for mmse(xi ) is α (α > 0). Moreover, let µ ≡ maxm∈[0,k] kAm k2 and assume µ 6= 1. Finally,
denote the maximum diagonal element of C(x0 )−1 as σ0−2 . Any

since the arithmetic mean of a finite set of positive numbers is
4 The extension of Theorem 1 to the case µ = 1 is straightforward, yet
notationally involved; as a result, we omit it.

5

sensor set S that achieves mmse(xi ) = α satisfies:
|S| ≥ nσ 2 li /α − σ 2 σ0−2



1 − µ2
.
1 − µ2(k+1)

We now give the definition of a supermodular set function,
as well as, that of an non-decreasing set function —we follow
Wolsey (1982) for this material.
Denote as 2[n] the power set of [n].

(13)

Definition 4 (Submodularity and supermodularity). A function
h : 2[n] 7→ R is submodular if for any sets S and S ′ , with
S ⊆ S ′ ⊆ [n], and any a ∈
/ S′,


where l0 = 1 and lk = λmin L⊤
k Lk .

The above corollary shows that the number of sensors increases as the minimum mean square error or the number of output measurements decreases. More importantly, it shows that
the number of sensors increases linearly with the system’s size
for fixed minimum mean square error. This is again a fundamental design limit, especially when the system’s size is large.5

h(S ∪ {a}) − h(S) ≥ h(S ′ ∪ {a}) − h(S ′ ).
A function h : 2[n] 7→ R is supermodular if (−h) is submodular.
An alternative definition of a submodular function is based
on the notion of non-increasing set functions.

Corollary 2 (Trade-off among the length of the observation interval, estimation error and the number of sensors). Consider
any finite observation interval [0, k], a sensor set S, a non-zero
σ, and for i ∈ {0, k}, that the desired value for mmse(xi ) is
α (α > 0). Moreover, let µ ≡ maxm∈[0,k] kAm k2 and assume µ 6= 1. Finally, denote the maximum diagonal element of
C(x0 )−1 as σ0−2 . Any observation interval [0, k] that achieves
mmse(xi ) = α satisfies:


log 1 − nσ 2 li /α − σ 2 σ0−2 (1 − µ2 )/|S|
k≥
− 1, (14)
2 log (µ)

where l0 = 1 and lk = λmin L⊤
k Lk .

Definition 5 (Non-increasing and non-decreasing set function).
A function h : 2[n] 7→ R is a non-increasing set function if
for any S ⊆ S ′ ⊆ [n], h(S) ≥ h(S ′ ). Moreover, h is a nondecreasing set function if (−h) is a non-increasing set function.
Therefore, a function h : 2[n] 7→ R is submodular if, for
any a ∈ [n], the function ha : 2[n]\{a} 7→ R, defined as
ha (S) ≡ h(S ∪ {a}) − h(S), is a non-increasing set function.
This property is also called the diminishing returns property.
The first major result of this section follows, where we let
Ok ≡ Ok⊤ Ok ,
given an observation interval [0, k].

As expected, the number of output measurements increases
as the minimum mean square error or the number of sensors decreases. Moreover, in contrast to our comments on Corollary 1
and the number of sensors, Corollary 2 indicates that the number of output measurements increases only logarithmically with
the system’s size for fixed error and number of sensors. On the
other hand, it also decreases logarithmically with the number of
sensors, and this is our final design limit result.
In the following paragraphs, we prove that the log det error
of the Kalman filter is a supermodular and non-increasing set
function in the choice of the sensor set. Then, we use this result
to provide efficient algorithms for the solution of P1 and P2 .

Proposition 1 (Closed formula for the log det error as a sensor
set function). Given an observation interval [0, k] and non-zero
σ, irrespective of Assumption 2,

log det Σzk−1 =

2n(k + 1) log (σ) − log det Ok + σ 2 C(zk−1 )−1 . (15)
Proof. From (3),

Σzk−1 = C(zk−1 ) − C(zk−1 )Ok⊤
−1
Ok C(zk−1 )Ok⊤ + σ 2 I
Ok C(zk−1 )
−1
= σ −2 Ok⊤ Ok + C(zk−1 )−1
−1
,
= σ 2 Ok + σ 2 C(zk−1 )−1

4. Submodularity in Optimal Sensor Placement
In this section, we present our contributions with respect
to Objective 2. In particular, we first derive a closed formula
for log det Σzk−1 and then prove that it is a supermodular
and non-increasing set function in the choice of the sensor set.
This implies that the greedy algorithms for the solution of P1
and P2 return efficient approximate solutions (Feige (1998);
Nemhauser & Wolsey (1978)). In Section 5, we use this supermodularity result, and known results from the literature on submodular function maximization (Nemhauser & Wolsey (1988)),
to provide efficient algorithms for the solution of P1 and P2 .

(16)
(17)
(18)

where we deduce (17) from (16) using the Woodbury matrix
identity (Corollary 2.8.8 of Bernstein (2009)), and (18) from
(17) using the fact that Ok = Ok⊤ Ok .

Therefore, the log det Σzk−1 depends on the sensor set
through Ok . Now, the main result of this section follows, where
we make explicit the dependence of Ok on the sensor set S.

Theorem 2 (The log det error is a supermodular and non-increasing set function with respect to the choice of the sensor
set). Given an observation interval [0, k], the

log det Σzk−1 , S =

2n(k + 1) log (σ) − log det Ok,S + σ 2 C(zk−1 )−1 :


fixed and non-zero λmin L⊤
k Lk , the comments of this paragraph
extend to the mmse(xk ) as well, for any finite k —on the other
 hand, if
⊤
λmin L⊤
k Lk varies with the system’s size, since λmin Lk Lk ≤ 1, the
number of sensors can increase sub-linearly with the system’s size for fixed
mmse(xk ).
5 For

S ∈ 2[n] 7→ R

6

is a supermodular and non-increasing set function with respect
to the choice of the sensor set S.

erty: its rate of reduction with respect to newly placed sensors
decreases as the cardinality of the already placed sensors increases. On the one hand, this property implies another fundamental design limit, in accordance to that of Theorem 1: adding
new sensors, after a first few, becomes ineffective for the reduction of the estimation error. On the other hand, it also implies that greedy approach for solving P1 and P2 is effective
(Nemhauser & Wolsey (1978); Feige (1998)). Thereby, we next
use the results from the literature on submodular function maximization (Nemhauser & Wolsey (1988)) and provide efficient
algorithms for P1 and P2 .

Proof. For i ∈ [n], let I (i) be the n × n matrix where Iii is
one, while Ijk is zero, for all (j, k) 6= (i, i). Also, let C̄ ≡
σ 2 C(zk−1 )−1 . Now, to prove that the log det Σzk−1 , S is
non-increasing, observe that
Ok,S =

n
X

m=1

sm

k
X
j=0

(m)
Lj
L⊤
j I

=

n
X

sm Ok,{m} ,

(19)

m=1

Then, for any S1 ⊆ S2 ⊆ [n], (19) and Ok,{1} , Ok,{2} , . . .,
Ok,{n}  0 imply Ok,S1  Ok,S2 , and as a result, Ok,S1 + C̄ 
Ok,S2 + C̄. Therefore,
 from Theorem 8.4.9 of Bernstein (2009),
log det Ok,S1 + C̄  log det Ok,S2 + C̄ , and as a result,
log det Σzk−1 is non-increasing.

set
Next, to prove that log det Σzk−1 is a supermodular

function, it suffices to prove that log det Ok,S + C̄ is a submodular one. In particular, recall that a function h : 2[n] 7→ R
is submodular if and only if, for any a ∈ [n], the function
ha : 2[n]\{a} 7→ R, where ha (S) ≡ h(S ∪ {a}) − h(S), is
a non-increasing set function. Therefore, to prove that h(S) =
log det(Ok,S + C̄) is submodular, we may prove that the ha (S)
is a non-increasing set function. To this end, we follow the
proof of Theorem 6 in Summers et al. (2014): first, observe that

5. Algorithms for Optimal Sensor Placement
In this section, we present our contributions with respect to
Objective 3: P1 and P2 are combinatorial, and in Section 4 we
proved that they involve the minimization of the supermodular set function log det error. In particular, because the minimization of a general supermodular function is NP-hard (Feige
(1998)), in this section we provide efficient approximation algorithms for the general solution of P1 , and P2 , along with their
worst-case performance guarantees.
Specifically, we first provide an efficient algorithm for P1
that returns a sensor set that satisfies the estimation bound of
P1 and has cardinality up to a multiplicative factor from the
minimum cardinality sensor sets that meet the same estimation
bound. More importantly, this multiplicative factor depends
only logarithmically on the problem’s P1 parameters. Next, we
provide an efficient algorithm for P2 that returns a sensor set of
cardinality l ≥ r (l is chosen by the designer) and achieves a
near optimal value for increasing l.
To this end, we first present a fact from the supermodular
functions minimization literature that we use so to construct an
approximation algorithm for P1 —we follow Wolsey (1982)
for this material. In particular, consider the following problem,
which is of similar structure to P1 , where h : 2[n] 7→ R is a
supermodular and non-increasing set function:

ha (S) = log det(Ok,S∪{a} + C̄) − log det(Ok,S + C̄)

= log det(Ok,S + Ok,{a} + C̄) − log det(Ok,S + C̄).

Now, for any S1 ⊆ S2 ⊆ [n] and t ∈ [0, 1], define O(t) ≡ C̄+
Ok,S1 +t(Ok,S2 −Ok,S1 ) and h̄(t) ≡ log det O(t) + Ok,{a} −
log det (O(t)) ; it is h̄(0) = ha (S1 ) and h̄(1) = ha (S2 ). More
over, since d log det(O(t)))/dt = tr O(t)−1 dO(t)/dt (cf.
equation (43) in Petersen & Pedersen (2012)),
i

h
−1
dh̄(t)
= tr
O(t) + Ok,{a}
− O(t)−1 Ok,21 ,
dt

where Ok,21 ≡ Ok,S2 − Ok,S1 . From Proposition 8.5.5 of
minimize |S|
−1
S⊆[n]
(P)
Bernstein (2009), O(t) + Ok,{a}
 O(t)−1 , because O(t) ≻
subject to h(S) ≤ R.
0 for all t ∈ [0, 1], since C̄ ≻ 0, Ok,S1  0, and Ok,S2  Ok,S1 .
Thereby, from Corollary 8.3.6 of Bernstein (2009),
The following greedy algorithm has been proposed for its


approximate solution, for which, the subsequent fact is true.
−1
O(t) + Ok,{a}
− O(t)−1 Ok,21  0.
Algorithm 1 Approximation Algorithm for P.
As a result, dh̄(t)/dt ≤ 0, and
Input: h, R.
Output: Approximate solution for P.
Z 1
dh̄(t)
S←∅
ha (S2 ) = h̄(1) = h̄(0) +
dt ≤ h̄(0) = ha (S1 ).
dt
while h(S) > R do
0
ai ← a′ ∈ arg maxa∈[n]\S (h(S) − h(S ∪ {a}))
Therefore, ha (S) is a non-increasing set function, and the proof
S ← S ∪ {ai }
is complete.
end while
The above theorem states that for any finite observation interval, the log det error of the Kalman filter is a supermodular
and non-increasing set function with respect to the choice of
the sensor set. Hence, it exhibits the diminishing returns prop-

Fact 1. Denote as S ⋆ a solution to P and as S0 , S1 , . . . the
sequence of sets picked by Algorithm 1. Moreover, let l be the
7

smallest index such that h(Sl ) ≤ R. Then,

at most n(k + 1) matrices must be computed so that the


arg max log det Σzk−1 , S − log det Σzk−1 , S ∪ {a}

l
h([n]) − h(∅)
≤ 1 + log
.
|S ⋆ |
h([n]) − h(Sl−1 )

a∈[n]\S

can be computed. Furthermore, O(n) time is required to find a
maximum element between n available. Therefore, the computational complexity of Algorithm 2 is O(n2 (nk)3 ).

For several classes of submodular functions, this is the best
approximation factor one can achieve in polynomial time (Feige
(1998)). Therefore, we use this result to provide the approximation Algorithm 2 for P
 1 , where we make explicit the dependence of log det Σzk−1 on the selected sensor set S. Moreover, its performance is quantified with Theorem 3.

Therefore, Algorithm 2 returns a sensor set that meets the
estimation bound of P1 . Moreover, the cardinality of this set
is up to a multiplicative factor of Fi from the minimum cardinality sensor sets that meet the same estimation bound —that
is, Fi is a worst-case approximation guarantee for Algorithm 2.
Additionally, Fi depends only logarithmically on the problem’s
P1 parameters. Finally, the dependence of Fi on n, R and
2
) is expected from a design perspective: increasing
max(σ02 , σw
the network size n, requesting a better estimation guarantee by
decreasing R, or incurring a noise of greater variance, should
all push the cardinality of the selected sensor set upwards.
From a computational perspective, the matrix inversion is
the only intensive procedure of Algorithm 2 —and it is necessary for computing the minimum mean square error of x̂i . In
particular, it requires O((nk)3 ) time if we use the Gauss-Jordan
elimination decomposition, since Ok in (15) is an n(k + 1) ×
n(k +1) matrix. On the other hand, we can speed up this procedure using the Coppersmith-Winograd algorithm (Coppersmith & Winogr
(1987)), which requires O(n2.376 ) time for n × n matrices. Alternatively, we can use numerical methods, which efficiently
compute an approximate inverse of a matrix even if its size
is of several thousands (Reusken (2001)). Moreover, we can
speed up Algorithm 2 using the method proposed in Minoux
(1978), which avoids the computation of log det(Σzk−1 , S) −
log det(Σzk−1 , S ∪ {a}) for unnecessary choices of a towards
the computation of the


arg max log det Σzk−1 , S − log det Σzk−1 , S ∪ {a} .

Algorithm 2 Approximation Algorithm for P1 .

For h(S) = log det Σzk−1 , S , where S ⊆ [n], Algorithm 2
is the same as Algorithm 1.

Theorem 3 (A Submodular Set Coverage Optimization for P1 ).
Denote a solution to P1 as S ⋆ and the selected set by Algorithm 2 as S. Moreover, denote the maximum diagonal element
2
,
of C(x0 ) and C(wk′ ), among all k ′ ∈ [0, k], as σ02 and σw
respectively. Then,

log det Σzk−1 , S ≤ R,
(20)


log det Σzk−1 , ∅ − log det Σzk−1 , [n]
|S|

≤ 1 + log
|S ⋆ |
R − log det Σzk−1 , [n]
≡ Fi ,

(21)


2
where log det Σzk−1 , ∅ ≤ n(k+1) log max(σ02 , σw
). Finally,
the computational complexity of Algorithm 2 is O(n2 (nk)3 ).
Proof. Let S0 , S1 , . . . be the sequence of sets selected by Algo
rithm 2 and l the smallest index such that log det Σzk−1 , Sl ≤
R. Therefore, Sl is the set that Algorithm 2 returns, and this
proves (20). Moreover, from Fact 1,


log det Σzk−1 , ∅ − log det Σzk−1 , [n]
l

.
≤ 1 + log
|S ⋆ |
log det Σzk−1 , Sl−1 − log det Σzk−1 , [n]

Now, l is the first time that
 log det Σzk−1 , Sl ≤ R, and a
result log det Σzk−1 , Sl−1 > R. This implies (21). 
Furthermore, log det Σzk−1 , ∅ = log det Czk−1 , and so
from the geometric-arithmetic mean inequality,

a∈[n]\S

Next, we develop our approximation algorithm for P2 . To
this end, we first present a relevant fact from the supermodular
functions minimization literature —we follow Wolsey (1982)
for this material. In particular, consider the following problem,
which is of similar structure to P2 , where h : 2[n] 7→ R is a
supermodular, non-increasing and non-positive set function:
minimize


tr(Czk−1 )
log det Czk−1 ≤ n(k + 1) log
n(k + 1)
2
n(k + 1) max(σ02 , σw
)
≤ n(k + 1) log
n(k + 1)

S⊆[n]

subject to

h(S)

(P ′ )

|S| ≤ r.

Algorithm 3 has been proposed for its approximate solution,
where l ≥ r, for which, the subsequent fact is true.

2
= n(k + 1) log max(σ02 , σw
).

Fact 2. Denote as S ⋆ a solution to P ′ and as S0 , S1 , . . . , Sl the
sequence of sets picked by Algorithm 3. Then, for all l ≥ r,


h(Sl ) ≤ 1 − e−l/r h(S ⋆ ).

Finally, with respect to the computational complexity of Algorithm 2, note that the while loop is repeated for at most n
times. Moreover, the complexity to compute the determinant of
an n(k + 1) × n(k + 1) matrix, using Gauss-Jordan elimination decomposition, is O((nk)3 ) (this is also the complexity to
multiply two such matrices). Additionally, the determinant of

In particular, for l = r, h(Sl ) ≤ (1 − 1/e) h(S ⋆ ).
8

Thus, Algorithm 3 constructs a solution of cardinality l instead of r and achieves an approximation factor 1 − e−l/r instead of 1 − 1/e. For example, for l = r, 1 − 1/e ∼
= .63, while
for l = 5r, 1 − e−l/r ∼
= .99; that is, for l = 5r, Algorithm 3
returns an approximate solution that although violates the cardinality constraint r, it achieves a value for h that is near to the
optimal one.
Moreover, for several classes of submodular functions, this
is the best approximation factor one can achieve in polynomial
time (Nemhauser & Wolsey (1978)). Therefore, we use this result to provide the approximation Algorithm 4 forP2 , where
we make explicit the dependence of log det Σzk−1 on the selected sensor set S. Theorem 4 quantifies its performance.

1

2

3

4

5

Figure 1: A 5-node integrator chain.

6. Examples and Discussion
6.1. Integrator Chain Network
We first illustrate the efficiency of Algorithms 2 and 4 using
the integrator chain in Fig. 1, where for all i ∈ [5], Aii is −1,
Ai+1,i is 1, and the rest of the elements of A are 0.
We run Algorithm 2 for k ← 5, C(x0 ), C(wk′ ), C(vk′ ) ←
I, for all k ′ ∈ [0, k], and R ← log det(Σz4 , {2, 4}). The
algorithm returned the sensor set {3, 5}. Specifically, {3, 5}
is the best such set, as it follows by comparing the values of
log det(Σz4 , ·) for all sets of cardinality at most two using MATLAB R : for all i ∈ [5], log det(Σz4 , {i}) > R, while for all
i, j ∈ [5] such that {i, j} =
6 {3, 5}, log det(Σz4 , {i, j}) >
log det(Σz4 , {3, 5}). Therefore, any singleton set does not satisfy the bound R, while {3, 5} not only satisfies it, it also achieves the smallest log det error among all other sets of cardinality
two. Hence, {3, 5} is the optimal minimal sensor set to achieve
the error bound R. Similarly, Algorithm 2 returned the optimal
minimal sensor set for every other value of R in the feasible
region of P1 , [log det(Σz4 , [5]), log det(Σz4 , ∅)].
We also run Algorithm 4 for k ← 5, C(x0 ), C(wk′ ), C(vk′ )
← I, for all k ′ ∈ [0, k], and r being equal to 1, 2, . . . , 5, respectively. For all values of r the chosen set coincided with the one
of the same size that also minimizes log det(Σz4 , ·). Thereby,
we again observe optimal performance from our algorithms.
Finally, by increasing r from 0 to 5, the corresponding minimum value of log det(Σz4 , ·) decreases only linearly from 0
to −31. This is in agreement with Theorem 1, since for any
M ∈ Rm×m , log det(M ) ≤ tr(M ) − m (Lemma 6, Appendix
D in Weimer (2010)), and as a result, for M equal to Σzk−1 ,

Algorithm 4 Approximation Algorithm for P2 .

For h(S) = log det Σzk−1 , S , where S ⊆ [n], Algorithm 4
is the same as Algorithm 3.
Theorem 4 (A Submodular Set Coverage Optimization for P2 ).
Denote a solution to P2 as S ⋆ and the sequence of sets picked
by Algorithm 4 as S0 , S1 , . . . , Sl . Moreover, denote the maximum diagonal element of C(x0 ) and C(wk′ ), among all k ′ ∈
2
[0, k], as σ02 and σw
, respectively. Then, for all l ≥ r,


log det Σzk−1 , Sl ≤ (1−e−l/r ) log det Σzk−1 , S ⋆ +
(22)

e−l/r log det Σzk−1 , ∅ ,

2
where log det Σzk−1 , ∅ ≤ n(k+1) log max(σ02 , σw
). Finally,
the computational complexity of Algorithm 2 is O(n2 (nk)3 ).


Proof. log det Σzk−1 , S − log det Σzk−1 , ∅ is a supermodular, non-increasing and non-positive set function. Thus, from
Fact 2 we derive (22).

2
That log det Σzk−1 , ∅ ≤ n(k + 1) log max(σ02 , σw
), as
well as, the computational complexity of Algorithm 4, follows
as in the proof of Theorem 3.

log det(Σzk−1 ) ≤ mmse(zk−1 ) − n(k + 1),

(23)

while, for any k ≥ 0, mmse(x0 ) ≤ mmse(zk−1 ).

Algorithm 4 returns a sensor set of cardinality l ≥ r, and
achieves a near optimal value for increasing l. Moreover, the
2
dependence of its approximation level on n, r and max(σ02 , σw
)
is expected from a design perspective: increasing the network
size n, requesting a smaller sensor set by decreasing r, or incurring a noise of greater variance should all push the quality
of the approximation level downwards.
Finally, from a computational perspective, our comments
on Algorithm 2 apply here as well.

6.2. CO2 Sequestration Sites
We now illustrate the efficiency of Algorithms 2 and 4 using
the problem of surface-based monitoring of CO2 sequestration
sites introduced in Weimer et al. (2008), for an instance that includes 81 possible sensor placement locations. Moreover, we
exemplify the fundamental design limit presented in Theorem

Algorithm 3 Approximation Algorithm for P ′ .
Input: h, l.
Output: Approximate solution for P ′ .
S ← ∅, i ← 0
while i < l do
ai ← a′ ∈ arg maxa∈[n]\S (h(S) − h(S ∪ {a}))
S ← S ∪ {ai }, i ← i + 1
end while
9

Output of Algorithm 1

xk+1 = Ak xk ,
yk = [C, 0] xk + vk ,

Output of Algorithm 2

0

0

−10

−10

Achieved logdet error

Error bound R

1, that the estimation error of the optimal linear estimator decreases only linearly as the number of sensors increases.
CO2 sequestration sites are used so to reduce the emissions
of CO2 from the power generation plans that burn fossil fuels. In particular, the problem of monitoring CO2 sequestration
sites is important due to potential leaks, which we need to identify using a set of sensors. Specifically, since these sites cover
large areas, power and communication constrains necessitate
the minimal sensor placement for monitoring these leaks, as we
undertake next: following Weimer et al. (2008), we consider a)
that the sequestration sites form an 9×9 grid (81 possible sensor
locations), and b) the onset of constant unknown leaks. Then,
for all k ≥ 0, the CO2 concentration between the sequestration
sites is described with the linear time-variant system

−20
−30
−40
−50
−60

−20
−30
−40
−50
−60

0

20

40

60

80

Achieved number of sensors

(24)

0

20

40

60

80

Number of sensors r

Figure 2: Outputs of Algorithms 2 and 4 for the CO2 sequestration sites application of Section 6.2: In the left plot, the output of Algorithm 2 is depicted
for k ← 100, C(x̄0 ), C(vk′ ) ← I, for all k ′ ∈ [0, k], and R that ranged
from log det(Σz99 , [81]) ∼
= −62 to log det(Σz99 , ∅) = 0 with step size ten.
In the right plot, the output of Algorithm 4 is depicted for k ← 100, C(x̄0 ),
C(vk′ ) ← I, for all k ′ ∈ [0, k], as well, and r that ranged from 0 to 81 with
step size ten.

⊤ ⊤
81
where xk ≡ (d⊤
is the vector of the CO2
k , lk ) , dk ∈ R
concentrations in the grid, and lk ∈ R81 is the vector of the
corresponding leaks rates; Ak describes the dependence of the
CO2 concentrations among the adjacent sites in the grid, and
with relation to the occurring leaks —it is constructed as in the
Appendix C of Weimer (2010); finally, C ∈ R81×81 is as in Assumption 2. Hence, we run Algorithms 2 and 4 so to efficiently
estimate x0 of (24) using a small number of sensors.
In particular, we run Algorithm 2 for k ← 100, C(x0 ),
C(vk′ ) ← I, for all k ′ ∈ [0, k], and R that ranged from log
det(Σz99 , [81]) ∼
= −62 to log det(Σz99 , ∅) = 0 with step size
ten —since in (24) the process noise is zero, z99 = x0 . The corresponding number of sensors that Algorithm 2 achieved with
respect to R is shown in the left plot of Fig. 2: as R increases
the number of sensors decreases, as one would expect when the
estimation error bound of P1 is relaxed.
For the same values for k, C(x0 ) and C(vk′ ), for all k ′ ∈
[0, k], we also run Algorithm 4 for r that ranged from 0 to 81
with step size ten. The corresponding achieved values for Problem P2 with respect to r are found in the right plot of Fig. 2:
as the number of available sensors r increases the minimum
achieved value also decreases, as expected by the monotonicity and supermodularity of log det(Σz99 , ·). At the same plot,
we compared these values with the achieved minimums over a
random sample of 80, 000 sensor sets for the various r (10, 000
distinct sets for each r, where r ranged from 0 to 81 with step
size ten): the achieved minimum random values were larger or
at most equal to those of Algorithm 4. Therefore, we observe
effective performance from Algorithm 4.
Now, to compare the outputs of Algorithms 2 and 4, for
error bounds R larger than −20 Algorithm 2 returns a sensor
set that solves P1 , yet does not minimize the log det(Σz99 , ·);
notwithstanding, the difference in the achieved value with respect to the output of Algorithm 4 is small. Moreover, for R
less than −20, Algorithm 2 returns a sensor set that not only
satisfies this bound; it also minimizes log det(Σz99 , ·). Overall,
both Algorithms 2 and 4 outperform the theoretical guarantees
of Theorems 3 and 4, respectively.
Finally, as in the example of Section 6.1, the minimum

value of log det(Σz99 , ·) —right plot of Fig. 2— decreases only
linearly from 0 to −62 as the number of sensors r increases
from 0 to 81. This is in agreement with Theorem 1, in relation
to (23) and the fact that z99 = x0 . Specifically, both the example of this section and that of Section 6.1 exemplify the fundamental design limit presented in Theorem 1, that the estimation
error of the optimal linear estimator decreases only linearly as
the number of sensors increases. That is, adding extra sensors
so to reduce the minimum mean square estimation error of the
Kalman filter is ineffective, a fundamental design limit.
7. Concluding Remarks
We considered a linear time-variant system and studied the
properties of its Kalman estimator given an observation interval and a sensor set. Our contributions were threefold. First, in
Section 3 we presented several design limits. For example, we
proved that the minimum mean square error decreases only linearly as the number of sensors increases. That is, adding extra
sensors so to reduce the minimum mean square estimation error
of the Kalman filter is ineffective, a fundamental design limit.
Similarly, we proved that the number of sensors grows linearly
with the system’s size for fixed minimum mean square error;
this is another fundamental limit, especially for systems where
the system’s size is large. Second, in Section 4 we proved that
the log det estimation error of the system’s initial condition and
process noise is a supermodular and non-increasing set function
with respect to the choice of the sensor set. Third, in Section
5, we used this result to provide efficient approximation algorithms for the solution of P1 and P2 , along with their worst-case
performance guarantees. For example, for P1 , we provided an
efficient algorithm that returns a sensor set that has cardinality up to a multiplicative factor from that of the corresponding
optimal solutions; more importantly, this factor depends only
10

logarithmically on the problem’s parameters. For P2 , we provided an efficient algorithm that returns a sensor set of cardinality l ≥ r and achieves a near optimal value for increasing
l. Finally, in Section 6, we illustrated our analytical findings,
and tested the efficiency of our algorithms, using simulation
results from an integrator chain network and the problem of
surface-based monitoring of CO2 sequestration sites studied in
Weimer et al. (2008) —another application that fits the context
of minimal sensor placement for effective monitoring is that of
thermal control of indoor environments, such as large offices
and buildings (Oldewurtel (2011); Sturzenegger (2014)). Our
future work is focused on extending the results of this paper to
the problem of sensor scheduling.

Hero III, A. O., & Cochran, D. (2011). Sensor management: Past, present, and
future. IEEE Sensors Journal, 11, 3064–3075.
Jawaid, S. T., & Smith, S. L. (2015). Submodularity and greedy algorithms in
sensor scheduling for linear dynamical systems. Automatica, 61, 282–288.
Jiang, C., Chai Soh, Y., & Li, H. (2015). Sensor placement by maximal projection on minimum eigenspace for linear inverse problem. arXiv preprint
arXiv: 1506.00747, .
Joshi, S., & Boyd, S. (2009). Sensor selection via convex optimization. IEEE
Transactions on Signal Processing, 57, 451–462.
Kailath, T., Sayed, A. H., & Hassibi, B. (2000). Linear estimation volume 1.
Prentice Hall Upper Saddle River, NJ.
Kalman, R. E. (1960). A new approach to linear filtering and prediction problems. Journal of Fluids Engineering, 82, 35–45.
Krause, A., & Guestrin, C. (). Beyond convexity: Submodularity in machine
learning, .
Krause, A., Singh, A., & Guestrin, C. (2008). Near-optimal sensor placements
in gaussian processes: Theory, efficient algorithms and empirical studies.
The Journal of Machine Learning Research, 9, 235–284.
Lin, F., Fardad, M., & Jovanovic, M. R. (2013). Design of optimal sparse
feedback gains via the alternating direction method of multipliers. IEEE
Transactions on Automatic Control, 58, 2426–2431.
Madsen, H., & Holst, J. (1995). Estimation of continuous-time models for the
heat dynamics of a building. Energy and Buildings, 22, 67 – 79.
Matni, N., & Chandrasekaran, V. (2014). Regularization for design. In IEEE
53rd Annual Conference on Decision and Control (CDC) (pp. 1111–1118).
Minoux, M. (1978). Accelerated greedy algorithms for maximizing submodular
set functions. In Optimization Techniques (pp. 234–243). Springer.
Munz, U., Pfister, M., & Wolfrum, P. (2014). Sensor and actuator placement
for linear systems based on h2 and h∞ optimization. IEEE Transactions on
Automatic Control, 59, 2984–2989.
Nemhauser, G. L., & Wolsey, L. A. (1978). Best algorithms for approximating the maximum of a submodular set function. Mathematics of operations
research, 3, 177–188.
Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and Combinatorial Optimization. New York, NY, USA: Wiley-Interscience.
Oldewurtel, F. (2011). Stochastic model predictive control for energy efficient building climate control. Ph.D. thesis Eidgenössische Technische
Hochschule ETH Zürich, Switzerland.
Olshevsky, A. (2014). Minimal controllability problems. IEEE Transactions
on Control of Network Systems, 1, 249–258.
Pasqualetti, F., Zampieri, S., & Bullo, F. (2014). Controllability metrics, limitations and algorithms for complex networks. IEEE Transactions on Control
of Network Systems, 1, 40–52.
Pequito, S., Kar, S., & Aguiar, A. (2015). A framework for structural input/output and control configuration selection in large-scale systems. IEEE
Transactions on Automatic Control, PP, 1–1.
Pequito, S., Ramos, G., Kar, S., Aguiar, A. P., & Ramos, J. (2014). On the Exact Solution of the Minimal Controllability Problem. arXiv preprint arXiv:
1401.4209, .
Petersen, K. B., & Pedersen, M. S. (2012). The matrix cookbook.
Reusken, A. (2001). Approximation of the determinant of large sparse symmetric positive definite matrices. SIAM J. Matrix Anal. Appl., 23, 799–818.
Rowaihy, H., Eswaran, S., Johnson, M., Verma, D., Bar-Noy, A., Brown, T., &
La Porta, T. (2007). A survey of sensor selection schemes in wireless sensor networks. In Defense and Security Symposium (pp. 65621A–65621A).
International Society for Optics and Photonics.
Shamaiah, M., Banerjee, S., & Vikalo, H. (2010). Greedy sensor selection:
Leveraging submodularity. In 49th IEEE Conference on Decision and Control (CDC), (pp. 2572–2577).
Singh, A., Krause, A., Guestrin, C., & Kaiser, W. J. (2009). Efficient informative sensing using multiple robots. Journal of Artificial Intelligence Research, (pp. 707–755).
Sturzenegger, D. C. T. (2014). Model Predictive Building Climate Control - Steps Towards Practice. Ph.D. thesis Eidgenössische Technische
Hochschule ETH Zürich, Switzerland.
Summers, T. H., Cortesi, F. L., & Lygeros, J. (2014). On submodularity and controllability in complex dynamical networks. arXiv preprint
arXiv:1404.7665, .
Tzoumas, V., Jadbabaie, A., & Pappas, G. J. (2016). Sensor placement for optimal kalman filtering: Fundamental limits, submodularity, and algorithms.
In American Control Conference (ACC). To appear.

Acknowledgements
This work was supported in part by TerraSwarm, one of
six centers of STARnet, a Semiconductor Research Corporation program sponsored by MARCO and DARPA, in part by
AFOSR Complex Networks Program and in part by AFOSR
MURI CHASE.
References
References
Atanasov, N., Le Ny, J., Daniilidis, K., & Pappas, G. J. (2014). Information
acquisition with sensing robots: Algorithms and error bounds. In IEEE
International Conference on Robotics and Automation (ICRA) (pp. 6447–
6454).
Belabbas, M.-A. (2015). Geometric methods for optimal sensor design. arXiv
preprint arXiv: 1503.05968, .
Bernstein, D. S. (2009). Matrix mathematics: theory, facts, and formulas.
Princeton University Press.
Bertsekas, D. P. (2005). Dynamic Programming and Optimal Control, Vol. I.
(3rd ed.). Athena Scientific.
Chen, C.-T. (1998). Linear System Theory and Design. (3rd ed.). New York,
NY, USA: Oxford University Press, Inc.
Clark, A., Alomair, B., Bushnell, L., & Poovendran, R. (2014a). Minimizing
convergence error in multi-agent systems via leader selection: A supermodular optimization approach. IEEE Transactions on Automatic Control, 59,
1480–1494.
Clark, A., Bushnell, L., & Poovendran, R. (2012). On leader selection for performance and controllability in multi-agent systems. In IEEE 51st Annual
Conference on Decision and Control (CDC) (pp. 86–93).
Clark, A., Bushnell, L., & Poovendran, R. (2014b). A supermodular optimization framework for leader selection under link noise in linear multi-agent
systems. IEEE Transactions on Automatic Control, 59, 283–296.
Coppersmith, D., & Winograd, S. (1987). Matrix multiplication via arithmetic
progressions. In Proceedings of the nineteenth annual ACM symposium on
Theory of computing (pp. 1–6).
Das, A., & Kempe, D. (2008). Sensor selection for minimizing worst-case prediction error. In Information Processing in Sensor Networks, 2008. IPSN’08.
International Conference on (pp. 97–108).
Dhingra, N. K., Jovanovic, M. R., & Luo, Z.-Q. (2014). An admm algorithm
for optimal sensor and actuator selection. In IEEE 53rd Annual Conference
on Decision and Control (CDC) (pp. 4039–4044).
Fang, Y., Loparo, K., Feng, X. et al. (1994). Inequalities for the trace of matrix
product. IEEE Transactions on Automatic Control,, 39, 2489–2490.
Feige, U. (1998). A threshold of ln n for approximating set cover. J. ACM, 45,
634–652.
Gupta, V., Chung, T. H., Hassibi, B., & Murray, R. M. (2006). On a stochastic
sensor selection algorithm with applications in sensor scheduling and sensor
coverage. Automatica, 42, 251–260.

11

Tzoumas, V., Jadbabaie, A., & Pappas, G. J. (December 2015). Minimal reachability problems. In 54th IEEE Conference on Decision and Control (CDC).
Tzoumas, V., Rahimian, M. A., Pappas, G. J., & Jadbabaie, A. (2015). Minimal
actuator placement with bounds on control effort. IEEE Transactions on
Control of Network Systems, . In press.
Tzoumas, V., Rahimian, M. A., Pappas, G. J., & Jadbabaie, A. (July 2015).
Minimal actuator placement with optimal control constraints. In Proceedings of the American Control Conference (pp. 2081 – 2086).
Venkatesh, S. (2012). The Theory of Probability: Explorations and Applications. Cambridge University Press.
Weimer, J. E. (2010). Large-scale multiple-source detection using wireless sensor networks. Ph.D. thesis Carnegie Mellon University Pittsburgh, PA, USA.
Weimer, J. E., Sinopoli, B., & Krogh, B. H. (2008). A relaxation approach to
dynamic sensor selection in large-scale wireless networks. In Distributed
Computing Systems Workshops, 2008. ICDCS’08. 28th International Conference on (pp. 501–506).
Wolsey, L. A. (1982). An analysis of the greedy algorithm for the submodular
set covering problem. Combinatorica, 2, 385–393.
Yan, G., Tsekenis, G., Barzel, B., Slotine, J.-J., Liu, Y.-Y., & Barabási, A.-L.
(2015). Spectrum of controlling and observing complex networks. Nature
Physics, (pp. 779–786).
Zhang, H., Ayoub, R., & Sundaram, S. (2015). Sensor selection for optimal
filtering of linear dynamical systems: Complexity and approximation. In
IEEE Conference on Decision and Control (CDC).
Zhao, Y., & Cortés, J. (2015). Gramian-based reachability metrics for bilinear
networks. arXiv preprint arXiv:1509.02877, .

12

