Sensing-Constrained LQG Control

arXiv:1709.08826v1 [math.OC] 26 Sep 2017

Vasileios Tzoumas,1,2 Luca Carlone,2 George J. Pappas,1 Ali Jadbabaie2

Abstract—Linear-Quadratic-Gaussian (LQG) control is concerned with the design of an optimal controller and estimator
for linear Gaussian systems with imperfect state information.
Standard LQG assumes the set of sensor measurements, to be
fed to the estimator, to be given. However, in many problems,
arising in networked systems and robotics, one may not be able to
use all the available sensors, due to power or payload constraints,
or may be interested in using the smallest subset of sensors
that guarantees the attainment of a desired control goal. In this
paper, we introduce the sensing-constrained LQG control problem,
in which one has to jointly design sensing, estimation, and control,
under given constraints on the resources spent for sensing.
We focus on the realistic case in which the sensing strategy has to
be selected among a finite set of possible sensing modalities. While
the computation of the optimal sensing strategy is intractable,
we present the first scalable algorithm that computes a nearoptimal sensing strategy with provable sub-optimality guarantees.
To this end, we show that a separation principle holds, which
allows the design of sensing, estimation, and control policies in
isolation. We conclude the paper by discussing two applications
of sensing-constrained LQG control, namely, sensing-constrained
formation control and resource-constrained robot navigation.

I. I NTRODUCTION
Traditional approaches to control of systems with partially
observable state assume the choice of sensors used to observe
the system is given. The choice of sensors usually results from
a preliminary design phase in which an expert designer selects
a suitable sensor suite that accommodates estimation requirements (e.g., observability, desired estimation error) and system
constraints (e.g., size, cost). Modern control applications, from
large networked systems to miniaturized robotics systems,
pose serious limitations to the applicability of this traditional
paradigm. In large-scale networked systems (e.g., smart grids
or robot swarms), in which new nodes are continuously added
and removed from the network, a manual re-design of the
sensors becomes cumbersome and expensive, and it is simply
not scalable. In miniaturized robot systems, while the set of
onboard sensors is fixed, it may be desirable to selectively
activate only a subset of the sensors during different phases of
operation, in order to minimize power consumption. In both
application scenarios, one usually has access to a (possibly
large) list of potential sensors, but, due to resource constraints
(e.g., cost, power), can only utilize a subset of them. Moreover,
1 The authors are with the Department of Electrical and Systems Engineering, University of Pennsylvania, Philadelphia, PA 19104 USA (email:
{pappagsg, vtzoumas}@seas.upenn.edu).
2 The authors are with the Institute for Data, Systems and Society, and
the Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, MA 02139 USA (email: {jadbabai,
lcarlone, vtzoumas}@mit.edu).
This work was supported in part by TerraSwarm, one of six centers
of STARnet, a Semiconductor Research Corporation program sponsored by
MARCO and DARPA, and in part by AFOSR Complex Networks Program.

the need for online and large-scale sensor selection demands
for automated approaches that efficiently select a subset of
sensors to maximize system performance.
Motivated by these applications, in this paper we consider
the problem of jointly designing control, estimation, and
sensor selection for a system with partially observable state.
Related work. One body of related work is control over
band-limited communication channels, which investigates the
trade-offs between communication constraints (e.g., data rate,
quantization, delays) and control performance (e.g., stability)
in networked control systems. Early work provides results
on the impact of quantization [1], finite data rates [2], [3],
and separation principles for LQG design with communication constraints [4]; more recent work focuses on privacy
constraints [5]. We refer the reader to the surveys [6]–[8].
A second set of related work is sensor selection and scheduling, in which one has to select a (possibly time-varying) set of
sensors in order to monitor a phenomenon of interest. Related
literature includes approaches based on randomized sensor
selection [9], dual volume sampling [10], [11], convex relaxations [12], [13], and submodularity [14]–[16]. The third set
of related works is information-constrained (or informationregularized) LQG control [17], [18]. Shafieepoorfard and Raginsky [17] study rationally inattentive control laws for LQG
control and discuss their effectiveness in stabilizing the system.
Tanaka and Mitter [18] consider the co-design of sensing,
control, and estimation, propose to augment the standard LQG
cost with an information-theoretic regularizer, and derive an
elegant solution based on semidefinite programming. The main
difference between our proposal and [18] is that we consider
the case in which the choice of sensors, rather than being
arbitrary, is restricted to a finite set of available sensors.
Contributions. We extend the Linear-Quadratic-Gaussian
(LQG) control to the case in which, besides designing an optimal controller and estimator, one has to select a set of sensors
to be used to observe the system state. In particular, we formulate the sensing-constrained (finite-horizon) LQG problem
as the joint design of an optimal control and estimation policy,
as well as the selection of a subset of k out of N available
sensors, that minimize the LQG objective, which quantifies
tracking performance and control effort. We first leverage a
separation principle to show that the design of sensing, control,
and estimation, can be performed independently. While the
computation of the optimal sensing strategy is combinatorial
in nature, a key contribution of this paper is to provide the
first scalable algorithm that computes a near-optimal sensing
strategy with provable sub-optimality guarantees. We demonstrate the effectiveness of the proposed algorithm in numerical
experiments, and motivate the importance of the sensing-

constrained LQG problem, by considering two application
scenarios, namely, sensing-constrained formation control and
resource-constrained robot navigation.
Notation. Lowercase letters denote vectors and scalars, and
uppercase letters denote matrices. We use calligraphic fonts to
denote sets. The identity matrix of size n is denoted with In
(dimension is omitted when clear from the context). For a
matrix M and a vector v of appropriate dimension, we define
kvk2M , v T M v. For matrices M1 , M2 , . . . , Mk , we define
diag (M1 , M2 , . . . , Mk ) as the block diagonal matrix with
diagonal blocks the M1 , M2 , . . . , Mk .
II. S ENSING -C ONSTRAINED LQG C ONTROL
In this section we formalize the sensing-constrained LQG
control problem considered in this paper. We start by introducing the notions of system, sensors, and control policies.
a) System: We consider a standard discrete-time (possibly time-varying) linear system with additive Gaussian noise:
xt+1 = At xt + Bt ut + wt ,

t = 1, 2, . . . , T,

(1)

where xt ∈ Rnt represents the state of the system at time t,
ut ∈ Rmt represents the control action, wt represents the
process noise, and T is a finite time horizon. In addition,
we consider the system’s initial condition x1 to be a Gaussian
random variable with covariance Σ1|0 , and wt to be a Gaussian
random variable with mean zero and covariance Wt , such that
wt is independent of x1 and wt′ for all t′ = 1, 2, . . . , T , t′ 6= t.
b) Sensors: We consider the case where we have a
(potentially large) set of available sensors, which take noisy
linear observations of the system’s state. In particular, let V be
a set of indices such that each index i ∈ V uniquely identifies
a sensor that can be used to observe the state of the system.
We consider sensors of the form
yi,t = Ci,t xt + vi,t ,

i ∈ V,

(2)

where yi,t ∈ Rpi,t represents the measurement of sensor i at
time t, and vi,t represents the measurement noise of sensor i.
We assume vi,t to be a Gaussian random variable with mean
zero and positive definite covariance Vi,t , such that vi,t is
independent of x1 , and of wt′ for any t′ 6= t, and independent
of vi′ ,t′ for all t′ 6= t, and any i′ ∈ V, i′ 6= i.
In this paper we are interested in the case in which we
cannot use all the available sensors, and as a result, we need
to select a convenient subset of sensors in V to maximize our
control performance (formalized in Problem 1 below).
Definition 1 (Active sensor set and measurement model).
Given a set of available sensors V, we say that S ⊂ V is an
active sensor set if we can observe the measurements from each
sensor i ∈ S for all t = 1, 2, . . . , T . Given an active sensor
set S = {i1 , i2 . . . , i|S| }, we define the following quantities
yt (S)
Ct (S)
Vt (S)

,
,
,

[yiT1 ,t , yiT2 ,t , . . . , yiT|S| ,t ]T ,
[CiT1 ,t , CiT2 ,t , . . . , CiT|S| ,t ]T ,
diag[Vi1 ,t , Vi2 ,t , . . . , Vi|S| ,t ]

(3)

which lead to the definition of the measurement model:
yt (S) = Ct (S)xt + vt (S)

(4)

where vt (S) is a zero-mean Gaussian noise with covariance Vt (S). Despite the availability of a possibly large set
of sensors V, our observer will only have access to the
measurements produced by the active sensors.
The following paragraph formalizes how the choice of the
active sensors affects the control policies.
c) Control policies: We consider control policies ut for
all t = 1, 2, . . . , T that are only informed by the measurements
collected by the active sensors:
ut = ut (S) = ut (y1 (S), y2 (S), . . . , yt (S)),

t = 1, 2, . . . , T.

Such policies are called admissible.
In this paper, we want to find a small set of active sensors S,
and admissible controllers u1 (S), u2 (S), . . . , uT (S), to solve
the following sensing-constrained LQG control problem.
Problem 1 (Sensing-constrained LQG control). Find a sensor set S ⊂ V of cardinality at most k to be active across all
times t = 1, 2, . . . , T , and control policies u1:T (S) , {u1 (S),
u2 (S), . . . , uT (S)}, that minimize the LQG cost function:
min

S ⊆ V, |S|≤ k,
u1:T (S)

T
X
t=1



E kxt+1 (S)k2Qt +kut (S)k2Rt ,

(5)

where the state-cost matrices Q1 , Q2 , . . . , QT are positive
semi-definite, the control-cost matrices R1 , R2 , . . . , RT are
positive definite, and the expectation is taken with respect to
the initial condition x1 , the process noises w1 , w2 , . . . , wT ,
and the measurement noises v1 (S), v2 (S), . . . , vT (S).
Problem 1 generalizes the imperfect state-information LQG
control problem from the case where all sensors in V are
active, and only optimal control policies are to be found [19,
Chapter 5], to the case where only a few sensors in V can
be active, and both optimal sensors and control policies are
to be found jointly. While we already noticed that admissible
control policies depend on the active sensor set S, it is worth
noticing that this in turn implies that the state evolution also
depends on S; for this reason we write xt+1 (S) in eq. (5).
The intertwining between control and sensing calls for a joint
design strategy. In the following section we focus on the design
of a jointly optimal control and sensing solution to Problem 1.
III. J OINT S ENSING

AND

C ONTROL D ESIGN

In this section we first present a separation principle that decouples sensing, estimation, and control, and allows designing
them in cascade (Section III-A). We then present a scalable
algorithm for sensing and control design (Section III-B).
A. Separability of Optimal Sensing and Control Design
We characterize the jointly optimal control and sensing
solutions to Problem 1, and prove that they can be found in
two separate steps, where first the sensing design is computed,
and second the corresponding optimal control design is found.

Algorithm 1 Joint Sensing and Control design for Problem 1.
Input: Time horizon T , available sensor set V, covariance
matrix Σ1|0 of initial condition x1 ; for all t = 1, 2, . . . , T ,
system matrix At , input matrix Bt , LQG cost matrices Qt
and Rt , process noise covariance matrix Wt ; and for all
sensors i ∈ V, measurement matrix Ci,t , and measurement
noise covariance matrix Vi,t .
b and control matrices K1 , . . . , KT .
Output: Active sensors S,
b
1: S is returned by Algorithm 2 that finds a (possibly approximate) solution to the optimization problem in eq. (6);
2: K1 , . . . , KT are computed using the recursion in eq. (8).

Theorem 1 (Separability of optimal sensing and control design). Let the sensor set S ⋆ and the controllers u⋆1 , u⋆2 , . . . , u⋆T
be a solution to the sensing-constrained LQG Problem 1. Then,
S ⋆ and u⋆1 , u⋆2 , . . . , u⋆T can be computed in cascade as follows:
S ⋆ ∈ arg min

T
X

S⊆V,|S|≤k t=1

u⋆t = Kt x̂t,S ⋆ ,

tr[Θt Σt|t (S)],

t = 1, . . . , T

(6)
(7)

where x̂t (S) is the Kalman estimator of the state xt ,
i.e., x̂t (S) , E(xt |y1 (S), y2 (S), . . . , yt (S)), and Σt|t (S)
is x̂t (S)’s error covariance, i.e., Σt|t (S) , E[(x̂t (S) −
xt )(x̂t (S) − xt )T ] [19, Appendix E]. In addition, the matrices
Θt and Kt are independent of the selected sensor set S, and
they are computed as follows: the matrices Θt and Kt are the
solution of the backward Riccati recursion

Algorithm 2 Sensing design for Problem 1.
Input: Time horizon T , available sensor set V, covariance
matrix Σ1|0 of system’s initial condition x1 , and for
any time t = 1, 2, . . . , T , any sensor i ∈ V, process
noise covariance matrix Wt , measurement matrix Ci,t , and
measurement noise covariance matrix Vi,t .
b
Output: Sensor set S.
1: Compute Θ1 , Θ2 , . . . , ΘT using recursion in eq. (8);
b ← ∅; i ← 0;
2: S
3: while i < k do
4:
for all a ∈ V \ Sb do
5:
Sba ← Sb ∪ {a}; Σ1|0 (Sba ) ← Σ1|0 ;
6:
for all t = 1, . . . , T do
7:
Σt|t (Sba ) ←
8:
[Σt|t−1 (Sba )−1 + Ct (Sba )T Vt (Sba )−1 Ct (Sba )]−1 ;
9:
Σt+1|t (Sba ) ← At Σt|t (Sba )AT
t + Wt ;
10:
end for P
T
11:
costa ← t=1 tr[Θt Σt|t (Sba )];
12:
end for
13:
ai ← arg mina∈V\S costa ;
14:
Sb ← Sb ∪ {ai }; i ← i + 1;
15: end while
vide more insight on the cost function in (6), we rewrite it as:
T
X

tr[Θt Σt|t (S)] =

t=1

T
X
t=1

=

T
X
t=1

St
Nt
Mt
Kt
Θt

= Qt + Nt+1 ,
−1
= AT
+ Bt Rt−1 BtT )−1 At ,
t (St
T
= Bt St Bt + Rt ,
= −Mt−1 BtT St At ,
= KtT Mt Kt ,

(8)

with boundary condition NT +1 = 0.
Remark 1 (Certainty equivalence principle). The control
gain matrices K1 , K2 , . . . , KT are the same as the ones that
make the controllers (K1 x1 , K1 x2 , . . . , KT xT ) optimal for
the perfect state-information version of Problem 1, where the
state xt is known to the controllers [19, Chapter 4].
Theorem 1 decouples the design of the sensing from the
controller design. Moreover, it suggests that once an optimal
sensor set S ⋆ is found, then the optimal controllers are equal
to Kt x̂t (S), which correspond to the standard LQG control
policy. This should not come as a surprise, since for a given
sensing strategy, Problem 1 reduces to standard LQG control.
We conclude this section with a remark providing a more
intuitive interpretation of the sensor design step in eq. (6).
Remark 2 (Control-aware sensor design). In order to pro-

E tr{[xt − x̂t (S)]T Θt [xt − x̂t (S)]}

E kKt xt − Kt x̂t (S)k2Mt ,



(9)

where
in the first line we used
the fact that Σt|t (S) =


E (xt − x̂t (S))(xt − x̂t (S))T , and in the second line we
substituted the definition of Θt = KtT Mt Kt from eq. (8).
From eq. (9), it is clear that each term tr[Θt Σt|t (S)]
captures the expected control mismatch between the imperfect
state-information controller ut (S) = Kt x̂t (S) (which is only
aware of the measurements from the active sensors) and the
perfect state-information controller Kt xt . This is an important
distinction from the existing sensor selection literature. In particular, while standard sensor selection attempts to minimize
the estimation covariance, for instance by minimizing
T
X
t=1

tr[Σt|t (S)] ,

T
X
t=1


E kxt − x̂t (S)k22 ,

(10)

the proposed LQG cost formulation attempts to minimize the
estimation error of only the informative states to the perfect
state-information controller: for example, the contribution of
all xt − x̂t (S) in the null space of Kt to the total control
mismatch in eq. (9) is zero. Hence, in contrast to minimizing
the cost function in eq. (10), minimizing the cost function in
eq. (9) results to a control-aware sensing design.

B. Scalable Near-optimal Sensing and Control Design
This section proposes a practical design algorithm for
Problem 1. The pseudo-code of the algorithm is presented in
Algorithm 1. Algorithm 1 follows the result of Theorem 1,
and jointly designs sensing and control by first computing an
active sensor set (line 1 in Algorithm 1) and then computing
the control policy (line 2 in Algorithm 1). We discuss each
step of the design process in the rest of this section.
1) Near-optimal Sensing design: The optimal sensor design
can be computed by solving the optimization problem in
eq. (6). The problem is combinatorial in nature, since it
requires to select a subset of elements of cardinality k out
of all the available sensors that induces the smallest cost.
In this section we propose a greedy algorithm, whose
pseudo-code is given in Algorithm 2, that computes a (possibly
approximate) solution to the problem in eq. (6). Our interest
towards this greedy algorithm is motivated by the fact that
it is scalable (in Section IV we show that its complexity is
linear in the number of available sensors) and is provably
close to the optimal solution of the problem in eq. (6)
(we provide suboptimality bounds in Section IV).
Algorithm 2 computes the matrices Θt (t = 1, 2, . . . , T )
which appear in the cost function in eq. (6) (line 1).
Note that these matrices are independent on the choice of
sensors. The set of active sensors Sb is initialized to the
empty set (line 2). The “while loop” in line 3 will be
executed k times and at each time a sensor is greedily
b In particular, the
added to the set of active sensors S.
“for loop” in lines 4-12 computes the estimation covariance
resulting by adding a sensor to the current active sensor
set and the corresponding cost (line 11). Finally, the sensor
inducing the smallest cost is selected (line 13) and added
to the current set of active sensors (line 14).
2) Control policy design: The optimal control design is
computed as in eq. (7), where the control policy matrices
K1 , K2 , . . . , KT are obtained from the recursion in eq. (8).
In the following section we characterize the approximation
and running-time performance of Algorithm 1.
IV. P ERFORMANCE G UARANTEES FOR J OINT S ENSING
AND C ONTROL D ESIGN
We prove that Algorithm 1 is the first scalable algorithm
for the joint sensing and control design Problem 1, and that it
achieves a value for the LQG cost function in eq. (5) that is
finitely close to the optimal. We start by introducing the notion
of supermodularity ratio (Section IV-A), which will enable to
bound the sub-optimality gap of Algorithm 1 (Section IV-B).
A. Supermodularity ratio of monotone functions
We define the supermodularity ratio of monotone functions.
We start with the notions of monotonicity and supermodularity.
Definition 2 (Monotonicity). Consider any finite ground
set V. The set function f : 2V 7→ R is non-increasing if and
only if for any A ⊆ A′ ⊆ V, f (A) ≥ f (A′ ).

Definition 3 (Supermodularity [20, Proposition 2.1]). Consider any finite ground set V. The set function f : 2V 7→ R is
supermodular if and only if for any A ⊆ A′ ⊆ V and x ∈ V,
f (A) − f (A ∪ {x}) ≥ f (A′ ) − f (A′ ∪ {x}).
In words, a set function f is supermodular if and only if it
satisfies the following intuitive diminishing returns property:
for any x ∈ V, the marginal drop f (A) − f (A ∪ {x})
diminishes as A grows; equivalently, for any A ⊆ V and
x ∈ V, the marginal drop f (A)−f (A∪{x}) is non-increasing.
Definition 4 (Supermodularity ratio). Consider any finite
ground set V, and a non-increasing set function f : 2V 7→ R.
We define the supermodularity ratio of f as
γf =

min

A⊆V,x,x′ ∈V\A

f (A) − f (A ∪ {x})
.
f (A ∪ {x′ }) − f [(A ∪ {x′ }) ∪ {x}]

In words, the supermodularity ratio of a monotone set
function f measures how far f is from being supermodular.
In particular, per the Definition 4 of supermodularity ratio, the
supermodularity ratio γf takes values in [0, 1], and
• γf = 1 if and only if f is supermodular, since if γf = 1,
then Definition 4 implies f (A) − f (A ∪ {x}) ≥ f (A ∪
{x′ }) − f [(A ∪ {x′ }) ∪ {x}], i.e., the drop f (A) − f (A ∪
{x}) is non-increasing as new elements are added in A.
• γf < 1 if and only if f is approximately supermodular, in
the sense that if γf < 1, then Definition 4 implies f (A)−
f (A ∪ {x}) ≥ γf {f (A ∪ {x′ }) − f [(A ∪ {x′ }) ∪ {x}]},
i.e., the drop f (A) − f (A ∪ {x}) is approximately nonincreasing as new elements are added in A; specifically,
the supermodularity ratio γf captures how much ones
needs to discount the drop f (A ∪ {x′ }) − f [(A ∪ {x′ }) ∪
{x}], such that f (A) − f (A ∪ {x}) remains greater then,
or equal to, f (A ∪ {x′ }) − f [(A ∪ {x′ }) ∪ {x}].
We next use the notion of supermodularity ratio Definition 4
to quantify the sub-optimality gap of Algorithm 1.
B. Performance Analysis for Algorithm 1
We quantify Algorithm 1’s running time, as well as, Algorithm 1’s approximation performance, using the notion of
supermodularity ratio introduced in Section IV-A. We conclude the section by showing that for appropriate LQG cost
matrices Q1 , Q2 , . . . , QT and R1 , R2 , . . . , RT , Algorithm 1
achieves near-optimal approximate performance.
Theorem 2 (Performance of Algorithm 1). For any active
sensor set S ⊆ V, and admissible control policies u1:T (S) ,
{u1 (S), u2 (S), . . . , uT (S)}, let h[S, u1:T (S)] be Problem 1’s
cost function, i.e.,
PT
h[S, u1:T (S)] , t=1 E(kxt+1 (S)k2Qt +kut(S)k2Rt );
Further define the following set-valued function and scalar:
g(S) , minu1:T (S) h[S, u1:T (S)],
g ⋆ , minS⊆V,|S|≤k, h[S, u1:T (S)].
u1:T (S)

The following results hold true:

(11)

1) (Approximation quality) Algorithm 1 returns an active
sensor set Sb ⊂ V of cardinality k, and gain matrices K1 ,
b u1:T (S)]
b attained by
K2 , . . . , KT , such that the cost h[S,
b
the sensor set S and the corresponding control policies
b , {K1 x̂1 (S),
b . . . , KT x̂T (S)}
b satisfies
u1:T (S)
b u1:T (S))
b − g⋆
h(S,
≤ exp(−γg )
g(∅) − g ⋆


T
= 1, and that
norm of each C̄i,t is 1, i.e., tr C̄i,t C̄i,t
tr[Σt|t (∅)] ≤ λ2max [Σt|t (∅)], γg ’s lower bound is
γg ≥

(12)

where γg is the supermodularity ratio of g(S) in eq. (11).
2) (Running time) Algorithm 1 runs in O(k|V|T n2.4 ) time,
where n , maxt=1,2,...,T (nt ) is the maximum system size
in eq. (1).
Theorem 2 ensures that Algorithm 1 is the first scalable
algorithm for the sensing-constrained LQG control Problem 1.
In particular, Algorithm 1’s running time O(k|V|T n2.4 ) is linear both in the number of available sensors |V|, and the sensor
set cardinality constraint k, as well as, linear in the Kalman
filter’s running time across the time horizon {1, 2 . . . , T }.
Specifically, the contribution n2.4 T in Algorithm 1’s running
time comes from the computational complexity of using the
Kalman filter to compute the state estimation error covariances
Σt|t for each t = 1, 2, . . . , T [19, Appendix E].
Theorem 2 also guarantees that for non-zero ratio γg
Algorithm 1 achieves a value for Problem 1 that is finitely
close to the optimal. In particular, the bound in ineq. (12)
improves as γg increases, since it is decreasing in γg , and
is characterized by the following extreme behaviors: for
γg = 1, the bound in ineq. (12) is e−1 ≃ .37, which
is the minimum for any γg ∈ [0, 1], and hence, the best
bound on Algorithm 1’s approximation performance among
all γg ∈ [0, 1] (ideally, the bound in ineq. (12) would be 0
for γg = 1, in which case Algorithm 1 would be exact,
b u1:T (S))
b = g ⋆ ; however,
since it would be implied h(S,
even for supermodular functions, the best bound one can
achieve in the worst-case is e−1 [21]); for γg = 0, ineq. (12)
b u1:T (S))
b ≤ g(∅) =
is uninformative since it simplifies to h(S,
h(∅, u1:T (∅)), which is trivially satisfied.1
In the remaining
PT of the section, we first prove that if the
strict inequality t=1 Θt ≻ 0 holds, where each Θt is defined
as in eq. (8), then the ratio γg in ineq. (12) is non-zero, and as
result Algorithm 1 achieves a near-optimal approximation performance
(Theorem 3). Then, we prove that the strict inequalP
ity Tt=1 Θt ≻ 0 is equivalent to a verifiable condition (Proposition 1) that holds for appropriate cost matrices Qt and Rt .
Theorem 3 (Lower bound for supermodularity ratio γg ).
Let Θt for all t = 1, 2, . . . , T be defined as in eq. (8), g(S)
be defined as in eq. (11), and for any sensor i ∈ V, C̄i,t be
−1/2
the normalized measurement matrix Vi,t Ci,t .
PT
If t=1 Θt ≻ 0, the supermodularity ratio γg is non-zero.
In addition, if we consider for simplicity that the Frobenius
1 The inequality h(S,
b u1:T (S))
b ≤ h(∅, u1:T (∅)) simply states that a control policy that is informed by the active sensor set S has better performance
than a policy that does not use any sensor; for a more formal proof we refer
the reader to Appendix B.

P
λmin ( Tt=1 Θt ) mint∈{1,2,...,T } λ2min [Σt|t (V)]
PT
λmax ( t=1 Θt ) maxt∈{1,2,...,T } λ2max [Σt|t (∅)]
1 + mini∈V,t∈{1,2...,T } λmin [C̄i Σt|t (V)C̄iT ]
.
2 + maxi∈V,t∈{1,2...,T } λmax [C̄i Σt|t (∅)C̄iT ]

(13)

The supermodularity ratio bound in ineq. (13) suggests two
cases under which γg can increase, and correspondingly, the
performance bound of Algorithm 1 in eq. (12) can improve:
a) Case 1 where γg ’s bound in ineq. (13) increases:
P
P
When the fraction λmin ( Tt=1 Θt )/λmax ( Tt=1 Θt ) increases
to 1, then the right-hand-side in ineq. (13) increases. Equivalently, the right-hand-side in ineq. (13) increases when on
(i)
(i)
average all the directions xt − x̂t of the estimation errors
(1)
(1)
(2)
(2)
(n )
(n )
xt − x̂t = (xt − x̂t , xt − x̂t , . . . , xt t − x̂t t ) become
equally important in selecting the active sensor set. To see this,
consider for example that λmax (Θt ) = λmin (Θt ) = λ; then,
the cost function in eq. (6) that Algorithm 1 minimizes to
select the active sensor set becomes
T
X

tr[Θt Σt|t (S)] = λ

t=1

=λ

T
X



E tr(kxt − x̂t (S)k22 )

t=1
nt
T X
X
t=1 i=1

i
h
(i)
(i)
E tr(kxt − x̂t (S)|22 ) .

Overall, it is easier for Algorithm 1 to approximate a solution
to Problem 1 as the cost function in eq. (6) becomes the cost
function in the standard sensor selection problems where one
minimizes the total estimation covariance as in eq. (10).
b) Case 2 where γg ’s bound in ineq. (13) increases:
When either the numerators of the last two fractions in the
right-hand-side of ineq. (13) increase or the denominators
of the last two fractions in the right-hand-side of ineq. (13)
decrease, then the right-hand-side in ineq. (13) increases.
In particular, the numerators of the last two fractions in righthand-side of ineq. (13) capture the estimation quality when
all available sensors in V are used, via the terms of the
T
form λmin [Σt|t (V)] and λmin [C̄i,t Σt|t (V)C̄i,t
]. Interestingly,
this suggests that the right-hand-side of ineq. (13) increases
when the available sensors in V are inefficient in achieving
low estimation error, that is, when the terms of the form
T
λmin [Σt|t (V)] and λmin [C̄i,t Σt|t (V)C̄i,t
] increase. Similarly,
the denominators of the last two fractions in right-handside of ineq. (13) capture the estimation quality when no
sensors are used, via the terms of the form λmax [Σt|t (∅)] and
T
λmax [C̄i,t Σt|t (∅)C̄i,t
]. This suggests that the right-hand-side of
ineq. (13) increases when the measurement noise increases.
We next give a P
control-level equivalent condition to TheoT
rem 3’s condition t=1 Θt ≻ 0 for non-zero ratio γg .
Theorem 4 (Control-level condition for near-optimal sensor
selection). Consider the LQG problem where for any time t =
1, 2, . . . , T , the state xt is known to each controller ut and

9

the process noise wt is zero, i.e., the optimization problem
PT
(14)
minu1:T t=1 [kxt+1 k2Qt +kut (xt )k2Rt ] Σ =W =0 .

7
6
5
4
3

t

Let At to
PTbe invertible for all t = 1, 2, . . . , T ; the strict
inequality t=1 Θt ≻ 0 holds if and only if for all non-zero
initial conditions x1 ,
PT
0∈
/ arg minu1:T t=1 [kxt+1 k2Qt +kut (xt )k2Rt ] Σ =W =0 .
t|t

t

4 suggests that Theorem 3’s sufficient condition
PTheorem
T
Θ
≻
0 for non-zero ratio γg holds if and only if for
t
t=1
any non-zero initial condition x1 the all-zeroes control policy
u1:T = (0, 0, . . . , 0) is suboptimal for the noiseless perfect
state-information LQG problem in eq. (14).
The all-zeroes control policy is always suboptimal for the
noiseless perfect state-information LQG problem in eq. (14)
for appropriate LQG cost matrices Q1 , Q2 , . . . , QT and
R1 , R2 , . . . , RT , as implied by Proposition 1 below.
Proposition 1 (System-level condition for near-optimal
sensor selection). Let N1 be defined as in eq. (8). The control
policy u1:T , (0, 0, . . . , 0) is suboptimal for the LQG problem
in eq. (14) for all non-zero initial conditions x1 if and only if
PT
T
T
(15)
t=1 A1 · · · At Qt At · · · A1 ≻ N1 .

The strict ineq. (15) holds for appropriate LQG cost matrices Qt and Rt , as, for example, the control cost matrices
Rt are closer to zero than the state cost matrices Qt , that
is, as the LQG cost function penalizes the state vector values
more than the control vector values. For example, consider
the case where the LQG cost matrix R1 tends to zero, i.e.,
consider ǫ such that R1  ǫI, and ǫ −→ 0; then, for
any Q1 , the strict ineq. (15) holds for ǫ small, since N1 
−1
T −1
ǫAT
A1 −→ 0 for ǫ −→ 0. In particular,
1 (ǫS1 + B1 B1 )
R1  ǫI, and [22, Proposition 8.5.5],2 imply R1−1  I/ǫ, and
as a result, S1−1 + B1 R1−1 B1T  (ǫS1−1 + B1 B1T )/ǫ, which
in turn implies (S1−1 + B1 R1−1 B1T )−1  ǫ(ǫS1−1 + B1 B1T )−1 ,
−1
T −1
and consequently, N1  ǫAT
A1 .
1 (ǫS1 + B1 B1 )
Overall, Algorithm 1 is the first scalable algorithm for the
sensing-constrained LQG control Problem 1, and for appropriate LQG cost matrices Q1 , Q2 , . . . , QT and R1 , R2 , . . . , RT ,
Algorithm 1 achieves near-optimal approximate performance.
V. N UMERICAL E XPERIMENTS
We consider two application scenarios for the proposed sensing-constrained LQG control framework: sensingconstrained formation control and resource-constrained robot
navigation. We present a Monte Carlo analysis for both scenarios, which demonstrates that (i) the proposed sensor selection
strategy is near-optimal, and in particular, the resulting LQGcost (tracking performance) matches the optimal selection in
all tested instances for which the optimal selection could
be computed via a brute-force approach, (ii) a more naive
selection which attempts to minimize the state estimation
2 [22, Proposition 8.5.5] states that for any positive definite matrices M
1
and M2 such that M1  M2 , M2−1  M1−1 .

2

y [meters]

t|t

8

1
0
-1
-2
-3
-4
-5
-6
-7
-8
-9
-9

-8

-7

-6

-5

-4

-3

-2

-1

0

1

2

3

4

5

6

7

8

9

x [meters]

(a) formation control

(b) unmanned aerial robot

Fig. 1. Examples of applications of the proposed sensing-constrained LQG
control framework: (a) sensing-constrained formation control and (b) resourceconstrained robot navigation.

covariance [15] (rather than the LQG cost) has degraded LQG
tracking performance, often comparable to a random selection,
(iii) in the considered instances, a clever selection of a small
subset of sensors can ensure an LQG cost that is close to the
one obtained by using all available sensors, hence providing an
effective alternative for control under sensing constraints [23].
VI. S ENSING - CONSTRAINED

FORMATION CONTROL

Simulation setup. The first application scenario is illustrated in Fig. 1(a). A team of n agents (blue triangles) moves
in a 2D scenario. At time t = 1, the agents are randomly
deployed in a 10m × 10m square and their objective is to
reach a target formation shape (red stars); in the example of
Fig. 1(a) the desired formation has an hexagonal shape, while
in general for a formation of n, the desired formation is an
equilateral polygon with n vertices. Each robot is modeled as
a double-integrator, with state xi = [pi vi ]T ∈ R4 (pi is the 2D
position of agent i, while vi is its velocity), and can control
its own acceleration ui ∈ R2 ; the process noise is chosen

as a diagonal matrix W = diag [1e−2 , 1e−2 , 1e−4 , 1e−4 ] .
Each robot i is equipped with a GPS receiver, which can
measure the agent position pi with a covariance Vgps,i = 2·I2 .
Moreover, the agents are equipped with lidar sensors allowing
each agent i to measure the relative position of another agent j
with covariance Vlidar,ij = 0.1 · I2 . The agents have very
limited on-board resources, hence they can only activate a
subset of k sensors. Hence, the goal is to select the subset of
k sensors, as well as to compute the control policy that ensure
best tracking performance, as measured by the LQG objective.
For our tests, we consider two problem setups. In the first
setup, named homogeneous formation control, the LQG weigh
matrix Q is a block diagonal matrix with 4 × 4 blocks, with
each block i chosen as Qi = 0.1 · I4 ; since each 4 × 4 block
of Q weights the tracking error of a robot, in the homogeneous
case the tracking error of all agents is equally important.
In the second setup, named heterogeneous formation control,
the matrix Q is chose as above, except for one of the agents,
say robot 1, for which we choose Q1 = 10 · I4 ; this setup
models the case in which each agent has a different role or
importance, hence one weights differently the tracking error
of the agents. In both cases the matrix R is chosen to be the

identity matrix. The simulation is carried on over T time steps,
and T is also chosen as LQG horizon. Results are averaged
over 100 Monte Carlo runs: at each run we randomize the
initial estimation covariance Σ1|0 .
Compared techniques. We compare five techniques. All
techniques use an LQG-based estimator and controller, and
they only differ by the selections of the sensors used.
The first approach is the optimal sensor selection, denoted
as optimal, which attains the minimum of the cost function
in eq. (6), and that we compute by enumerating all possible
subsets; this brute-force approach is only viable when the
number of available sensors is small. The second approach
is a pseudo-random sensor selection, denoted as random∗ ,
which selects all the GPS measurements and a random subset
of the lidar measurements; note that we do not consider a
fully random selection since in practice this often leads to an
unobservable system, hence causing divergence of the LQG
cost. The third approach, denoted as logdet, selects sensors
so to minimize the average log det of the estimation covariance
over the horizon; this approach resembles [15] and is agnostic
to the control task. The fourth approach is the proposed sensor
selection strategy, described in Algorithm 2, and is denoted as
s-LQG. Finally, we also report the LQG performance when all
sensors are selected; this is clearly infeasible in practice, due to
the sensing constraints, and it is only reported for comparison
purposes. This approach is denoted as allSensors.
Results. The results of our numerical analysis are reported
in Fig. 2. When not specified otherwise, we consider a
formation of n = 4 agents, which can only use a total of
k = 6 sensors, and a control horizon T = 20. Fig. 2(a)
shows the LQG cost attained by the compared techniques for
increasing control horizon and for the homogeneous case. We
note that, in all tested instance, the proposed approach s-LQG
matches the optimal selection optimal, and both approaches
are relatively close to allSensors, which selects all the
2
available sensors ( n+n
2 ). On the other hand logdet leads
to worse tracking performance, and it is often close to the
pseudo-random selection random∗ . These considerations are
confirmed by the heterogeneous setup, shown in Fig. 2(b).
In this case the separation between the proposed approach
and logdet becomes even larger; the intuition here is that
the heterogeneous case rewards differently the tracking errors
at different agents, hence while logdet attempts to equally
reduce the estimation error across the formation, the proposed
approach s-LQG selects sensors in a task-oriented fashion,
since the matrices Θt for all t = 1, 2, . . . , T in the cost
function in eq. (6) incorporate the LQG weight matrices.
Fig. 2(c) shows the LQG cost attained by the compared
techniques for increasing number of selected sensors k and for
the homogeneous case. We note that for increasing number of
sensors all techniques converge to allSensors (the entire
ground set is selected). As in the previous case, the proposed
approach s-LQG matches the optimal selection optimal.
Interestingly, while the performance of logdet is in general
inferior with respect to s-LQG, when the number of selected
sensors k decreases (for k < n the problem becomes unob-

servable) the approach logdet performs similarly to s-LQG.
Fig. 2(d) shows the same statistics for the heterogeneous case.
We note that in this case logdet is inferior to s-LQG even
in the case with small k. Moreover, an interesting fact is that
s-LQG matches allSensors already for k = 7, meaning
that the LQG performance of the sensing-constraint setup is
indistinguishable from the one using all sensors; intuitively,
in the heterogeneous case, adding more sensors may have
marginal impact on the LQG cost (e.g., if the cost rewards
a small tracking error for robot 1, it may be of little value
to take a lidar measurement between robot 3 and 4). This
further stresses the importance of the proposed framework as a
parsimonious way to control a system with minimal resources.
Fig. 2(e) and Fig. 2(f) show the LQG cost attained by the
compared techniques for increasing number of agents, in the
homogeneous and heterogeneous case, respectively. To ensure
observability, we consider k = round (1.5n), i.e., we select a
number of sensors 50% larger than the smallest set of sensors
that can make the system observable. We note that optimal
quickly becomes intractable to compute, hence we omit values
beyond n = 4. In both figures, the main observation is that
the separation among the techniques increases with the number
of agents, since the set of available sensors quickly increases
with n. Interestingly, in the heterogeneous case s-LQG remains relatively close to allSensors, implying that for the
purpose of LQG control, using a cleverly selected small subset
of sensors still ensures excellent tracking performance.
VII. R ESOURCE - CONSTRAINED

ROBOT NAVIGATION

Simulation setup. The second application scenario is illustrated in Fig. 1(b). An unmanned aerial robot (UAV) moves
in a 3D scenario, starting from a randomly selected initial
location. The objective of the UAV is to land, and more
specifically, it has to reach the position [0, 0, 0] with zero
velocity. The UAV is modeled as a double-integrator, with
state xi = [pi vi ]T ∈ R6 (pi is the 3D position of agent i,
while vi is its velocity), and can control its own acceleration
ui ∈ R3 ; the process noise is chosen as W = I6 . The UAV
is equipped with multiple sensors. It has an on-board GPS
receiver, measuring the UAV position pi with a covariance
2 · I3 , and an altimeter, measuring only the last component
of pi (altitude) with standard deviation 0.5m. Moreover, the
UAV can use a stereo camera to measure the relative position
of ℓ landmarks on the ground; for the sake of the numerical
example, we assume the location of each landmark to be
known only approximately, and we associate to each landmark
an uncertainty covariance (red ellipsoids in Fig. 1(b)), which is
randomly generated at the beginning of each run. The UAV has
limited on-board resources, hence it can only activate a subset
of k sensors. For instance, the resource-constraints may be due
to the power consumption of the GPS and the altimeter, or
may be due to computational constraints that prevent to run
multiple object-detection algorithms to detect all landmarks
on the ground. Similarly to the previous case, we phrase the
problem as a sensing-constraint LQG problem,
 and we use
Q = diag [1e−3 , 1e−3 , 10, 1e−3 , 1e−3 , 10] and R = I3 .

12

random*
optimal
logdet
s-LQG
allSensors

6

2450

150

120
random*
optimal
logdet
s-LQG
allSensors

110

100

100

LQG cost

200

random*
optimal
logdet
s-LQG
allSensors

130

LQG cost / T

8

LQG cost

10

LQG cost

2500

250

random*
optimal
logdet
s-LQG
allSensors

4

2400

2350

2300

90

2

50

10

15

20

25

30

10

15

20

30

300

12
10

random*
optimal
logdet
s-LQG
allSensors

250

LQG cost

random*
optimal
logdet
s-LQG
allSensors

14

200

150

8
100

6
4

50

4

5

6

7

8

9

10

4

6

7

8

9

10

(d) heterogeneous

(c) homogeneous
25

180

random*
optimal
logdet
s-LQG
allSensors

15

random*
optimal
logdet
s-LQG
allSensors

160
140

LQG cost

20

LQG cost

5

maxNrUsedSensors

maxNrUsedSensors

10

120

0

100

60
40

3

5

7

nrRobots

(e) homogeneous

9

11

3

5

7

20

30

40

50

2250

4

horizon

6

8

10

maxNrUsedSensors

(b) heterogeneous

Fig. 3. LQG cost for increasing (a)-(b) control horizon T , (c)-(d) number of
selected sensors k, and (e)-(f) number of agents n. Statistics are reported for
the homogeneous formation control setup (left column), and the heterogeneous
setup (right column). Results are averaged over 100 Monte Carlo runs.

optimal selection optimal, while logdet and random∗
have suboptimal performance.
Fig. 3(b) shows the LQG cost attained by the compared
techniques for increasing number of selected sensors k.
Clearly, all techniques converge to allSensors for increasing k, but in the regime in which few sensors are used s-LQG
still outperforms alternative sensor selection schemes, and
matches in all cases the optimal selection optimal.
VIII. C ONCLUDING R EMARKS

80

5

10

(a) homogeneous

(b) heterogeneous

(a) homogeneous
16

LQG cost

25

horizon

horizon

9

11

nrRobots

(f) heterogeneous

Fig. 2. LQG cost for increasing (a)-(b) control horizon T , (c)-(d) number of
selected sensors k, and (e)-(f) number of agents n. Statistics are reported for
the homogeneous formation control setup (left column), and the heterogeneous
setup (right column). Results are averaged over 100 Monte Carlo runs.

Note that the structure of Q reflects the fact that during
landing we are particularly interested in controlling the vertical
direction and the vertical velocity (entries with larger weight
in Q), while we are less interested in controlling accurately the
horizontal position and velocity (assuming a sufficiently large
landing site). In the following, we present results averaged
over 100 Monte Carlo runs: in each run, we randomize the
covariances describing the landmark position uncertainty.
Compared techniques. We consider the five techniques
discussed in the previous section. As in the formation control
case, the pseudo-random selection random∗ always includes
the GPS measurement (which alone ensures observability) and
a random selection of the other available sensors.
Results. The results of our numerical analysis are reported
in Fig. 3. When not specified otherwise, we consider a total of
k = 3 sensors to be selected, and a control horizon T = 20.
Fig. 3(a) shows the LQG cost attained by the compared
techniques for increasing control horizon. For visualization
purposes we plot the cost normalized by the horizon, which
makes more visible the differences among the techniques. Similarly to the formation control example, s-LQG matches the

In this paper, we introduced the sensing-constrained LQG
control Problem 1, which is central in modern control applications that range from large-scale networked systems to
miniaturized robotics networks. While the computation of
the optimal sensing strategy is intractable, We provided the
first scalable algorithm for Problem 1, Algorithm 1, and
under mild conditions on the system and LQG matrices,
proved that Algorithm 1 computes a near-optimal sensing
strategy with provable sub-optimality guarantees. To this end,
we showed that a separation principle holds, which allows the
design of sensing, estimation, and control policies in isolation.
We motivated the importance of the sensing-constrained LQG
Problem 1, and demonstrated the effectiveness of Algorithm 1,
by considering two application scenarios: sensing-constrained
formation control, and resource-constrained robot navigation.
R EFERENCES
[1] N. Elia and S. Mitter, “Stabilization of linear systems with limited
information,” IEEE Trans. on Automatic Control, vol. 46, no. 9, pp.
1384–1400, 2001.
[2] G. Nair and R. Evans, “Stabilizability of stochastic linear systems with
finite feedback data rates,” SIAM Journal on Control and Optimization,
vol. 43, no. 2, pp. 413–436, 2004.
[3] S. Tatikonda and S. Mitter, “Control under communication constraints,”
IEEE Trans. on Automatic Control, vol. 49, no. 7, pp. 1056–1068, 2004.
[4] V. Borkar and S. Mitter, “LQG control with communication constraints,”
Comm., Comp., Control, and Signal Processing, pp. 365–373, 1997.
[5] J. L. Ny and G. Pappas, “Differentially private filtering,” IEEE Trans.
on Automatic Control, vol. 59, no. 2, pp. 341–354, 2014.
[6] G. Nair, F. Fagnani, S. Zampieri, and R. Evans, “Feedback control under
data rate constraints: An overview,” Proceedings of the IEEE, vol. 95,
no. 1, pp. 108–137, 2007.
[7] J. Hespanha, P. Naghshtabrizi, and Y.Xu, “A survey of results in networked control systems,” Pr. of the IEEE, vol. 95, no. 1, p. 138, 2007.
[8] J. Baillieul and P. Antsaklis, “Control and communication challenges in
networked real-time systems,” Proceedings of the IEEE, vol. 95, no. 1,
pp. 9–28, 2007.

12

[9] V. Gupta, T. H. Chung, B. Hassibi, and R. M. Murray, “On a stochastic
sensor selection algorithm with applications in sensor scheduling and
sensor coverage,” Automatica, vol. 42, no. 2, pp. 251–260, 2006.
[10] H. Avron and C. Boutsidis, “Faster subset selection for matrices and
applications,” SIAM Journal on Matrix Analysis and Applications,
vol. 34, no. 4, pp. 1464–1499, 2013.
[11] C. Li, S. Jegelka, and S. Sra, “Polynomial Time Algorithms for Dual
Volume Sampling,” ArXiv e-prints: 1703.02674, 2017.
[12] S. Joshi and S. Boyd, “Sensor selection via convex optimization,” IEEE
Transactions on Signal Processing, vol. 57, no. 2, pp. 451–462, 2009.
[13] J. L. Ny, E. Feron, and M. A. Dahleh, “Scheduling continuous-time
kalman filters,” IEEE Trans. on Aut. Control, vol. 56, no. 6, pp. 1381–
1394, 2011.
[14] M. Shamaiah, S. Banerjee, and H. Vikalo, “Greedy sensor selection:
Leveraging submodularity,” in Proceedings of the 49th IEEE Conference
on Decision and control, 2010, pp. 2572–2577.
[15] S. T. Jawaid and S. L. Smith, “Submodularity and greedy algorithms in
sensor scheduling for linear dynamical systems,” Automatica, vol. 61,
pp. 282–288, 2015.
[16] V. Tzoumas, A. Jadbabaie, and G. J. Pappas, “Sensor placement for
optimal Kalman filtering,” in Amer. Contr. Conf., 2016, pp. 191–196.
[17] E. Shafieepoorfard and M. Raginsky, “Rational inattention in scalar LQG
control,” in Proceedings of the 52th IEEE Conference in Decision and
Control, 2013, pp. 5733–5739.
[18] T. Tanaka and H. Sandberg, “SDP-based joint sensor and controller
design for information-regularized optimal LQG control,” in 54th IEEE
Conference on Decision and Control, 2015, pp. 4486–4491.
[19] D. P. Bertsekas, Dynamic programming and optimal control, Vol. I.
Athena Scientific, 2005.
[20] G. Nemhauser, L. Wolsey, and M. Fisher, “An analysis of approximations
for maximizing submodular set functions – I,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978.
[21] U. Feige, “A threshold of ln(n) for approximating set cover,” Journal
of the ACM, vol. 45, no. 4, pp. 634–652, 1998.
[22] D. S. Bernstein, Matrix mathematics. Princeton University Press, 2005.
[23] L. Carlone and S. Karaman, “Attention and anticipation in fast visualinertial navigation,” in Proceeding of the IEEE International Conference
on Robotics and Automation, 2017, pp. 3886–3893.
[24] P. R. Kumar and P. Varaiya, Stochastic systems: Estimation, identification and adaptive control. Prentice-Hall, Inc., 1986.
[25] 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, 2016.
[26] L. F. Chamon and A. Ribeiro, “Near-optimality of greedy set selection
in the sampling of graph signals,” in Proceedings of the IEEE Global
Conference on Signal and Information Processing, 2016, pp. 1265–1269.
[27] D. Coppersmith and S. Winograd, “Matrix multiplication via arithmetic
progressions,” J. of Symbolic Comp., vol. 9, no. 3, pp. 251–280, 1990.

A PPENDIX A: P RELIMINARY

FACTS

This appendix contains a set of lemmata that will be used
to support the proofs in this paper (Appendices B–F).
Lemma 1 ([22, Proposition 8.5.5]). Consider two positive
definite matrices M1 and M2 . If M1  M2 then M2−1  M1−1.
Lemma 2 (Trace inequality [22, Proposition 8.4.13]). Consider a symmetric matrix A, and a positive semi-definite matrix
B of appropriate dimension. Then,
λmin (A)tr (B) ≤ tr (AB) ≤ λmax (A)tr (B) .
Lemma 3 (Woodbury identity [22, Corollary 2.8.8]). Consider matrices A, C, U and V of appropriate dimensions, such
that A, C, and A + U CV are invertible. Then,
(A + U CV )−1 = A−1 − A−1 U (C −1 + V A−1 U )−1 V A−1.
Lemma 4 ([22, Proposition 8.5.12]). Consider two symmetric
matrices A1 and A2 , and a positive semi-definite matrix B.
If A1  A2 , then tr (A1 B) ≤ tr (A2 B).

Lemma 5 ([19, Appendix E]). For any sensor set S ⊆ V,
and for all t = 1, 2, . . . , T , let x̂t (S) be the Kalman estimator
of the state xt , i.e., x̂t (S), and Σt|t (S) be x̂t (S)’s error
covariance, i.e., Σt|t (S) , E[(x̂t (S) − xt )(x̂t (S) − xt )T ].
Then, Σt|t (S) is the solution of the Kalman filtering recursion
Σt|t (S) = [Σt|t−1 (S)−1 + Ct (S)T Vt (S)−1 Ct (S)]−1,
Σt+1|t (S) = At Σt|t (S)AT
t + Wt ,
(16)
with boundary condition the Σ1|0 (S) = Σ1|0 .
Lemma 6. For any sensor set S ⊆ V, let Σ1|1 (S) be defined as
in eq. (16), and consider two sensor sets S1 , S2 ⊆ V. If S1 ⊆
S2 , then Σ1|1 (S1 )  Σ1|1 (S2 ).
Proof of Lemma 6: Let D = S2 \ S1 , and observe that
for all t = 1, 2, . . . , T , the notation in Definition 1 implies
X
T
Ct (S2 )T Vt (S2 )−1 Ct (S2 ) =
Ci,t
Vi,t Ci,t
i∈S2

=

X

T
Ci,t
Vi,t Ci,t +

i∈S1

=

X

X

T
Ci,t
Vi,t Ci,t

i∈D
T
Ci,t
Vi,t Ci,t

i∈S1

 Ct (S1 )T Vt (S1 )−1 Ct (S1 ).

(17)

Therefore, Lemma 1 and ineq. (17) imply
T
−1
Σ1|1 (S2 ) = [Σ−1
Ct (S2 )]−1 
1|0 + C1 (S2 ) Vt (S2 )
T
−1
[Σ−1
Ct (S1 )]−1 = Σ1|1 (S1 ).
1|0 + C1 (S1 ) Vt (S1 )

Lemma 7. Let Σt|t be defined as in eq. (16) with boundary
condition the Σ1|0 ; similarly, let Σ̄t|t be defined as in eq. (16)
with boundary condition the Σ̄1|0 . If Σt|t  Σ̄t|t , then
Σt+1|t  Σ̄t+1|t .
Proof of Lemma 7: We complete the proof in two
steps: first, from eq. (16), it its Σt+1|t = At Σt|t AT
t + Wt 
+
W
=
Σ̄
.
Then,
from
Σ

Σ̄
,
At Σ̄t|t AT
t
t+1|t
t|t
t|t it follows
t
T
Σ̄
A
.
At Σt|t AT

A
t t|t t
t
Lemma 8. Let Σt|t−1 be defined as in eq. (16) with boundary
condition the Σ1|0 ; similarly, let Σ̄t|t−1 be defined as in
eq. (16) with boundary condition the Σ̄1|0 . If Σt|t−1  Σ̄t|t−1 ,
then Σt|t  Σ̄t|t .
Proof of Lemma 8: From eq. (16), it is Σt|t =
T −1
−1
T −1
−1
(Σ−1
 (Σ̄−1
= Σ̄t|t ,
t|t−1 + Ct Vt Ct )
t|t−1 + Ct Vt Ct )
since Lemma 1 and the condition Σt|t−1  Σ̄t|t−1 imply
−1
T −1
T −1
Σ−1
t|t−1 + Ct Vt Ct  Σ̄t|t−1 + Ct Vt Ct , which in turn
−1
T −1
−1
T −1
−1
implies (Σt|t−1 + Ct Vt Ct )
 (Σ̄−1
t|t−1 + Ct Vt Ct ) .
Corollary 1. Let Σt|t be defined as in eq. (16) with boundary
condition the Σ1|0 ; similarly, let Σ̄t|t be defined as in eq. (16)
with boundary condition the Σ̄1|0 . If Σt|t  Σ̄t|t , then
Σt+i|t+i  Σ̄t+i|t+i for any positive integer i.
Proof of Corollary 1: If Σt|t  Σ̄t|t , from Lemma 7,
we get Σt+1|t  Σ̄t+1|t , which, from Lemma 8, implies

Σt+1|t+1  Σ̄t+1|t+1 . By repeating the previous argument
another (i − 1) times, the proof is complete.
Corollary 2. Let Σt|t be defined as in eq. (16) with boundary
condition the Σ1|0 ; similarly, let Σ̄t|t be defined as in eq. (16)
with boundary condition the Σ̄1|0 . If Σt|t  Σ̄t|t , then
Σt+i|t+i−1  Σ̄t+i|t+i−1 for any positive integer i.
Proof of Corollary 2: If Σt|t  Σ̄t|t , from Corollary 1,
we get Σt+i−1|t+i−1  Σ̄t+i−1|t+i−1 , which, from Lemma 7,
implies Σt+i|t+i−1  Σ̄t+i|t+i−1 .
A PPENDIX B: P ROOF

OF

T HEOREM 1

The proof of Theorem 1 follows from the following lemma.
Lemma 9. For any active sensor set S ⊆ V, and admissible
control policies u1:T (S) , {u1 (S), u2 (S), . . . , uT (S)}, let
h[S, u1:T (S)] be Problem 1’s cost function, i.e.,
PT
h[S, u1:T (S)] , t=1 E(kxt+1 (S)k2Qt +kut (S)k2Rt );
Further define the following set-valued function:
g(S) , minu1:T (S) h[S, u1:T (S)],
Consider any sensor set S ⊆ V, and let u⋆1:T,S be the vector of control policies (K1 x̂1,S , K2 x̂2,S , . . . , KT x̂T,S ). Then
u⋆1:T,S is an optimal control policy:
u⋆1:T,S ∈ arg min h[S, u1:T (S)],

(18)

u1:T (S)

i.e., g(S) = h[S, u⋆1:T (S)], and in particular, u⋆1:T,S attains a
(sensor-dependent) LQG cost equal to:
g(S) = E(kx1 kN1 )+

T
X


tr[Θt Σt|t (S)] + tr (Wt St ) . (19)

t=1

Proof of Lemma 9: Let ht [S, ut:T (S)] be the LQG cost
in Problem 1 from time t up to time T , i.e.,
ht [S, ut:T (S)] ,

T
X

E(kxk+1 (S)k2Qt +kuk (S)k2Rt ).

k=t

and define gt (S) , minut:T (S) ht [S, ut:T (S)]. Clearly, g1 (S)
matches the LQG cost in eq. (19).
We complete the proof inductively. In particular, we first
prove Lemma 9 for t = T , and then for any other t ∈
{1, 2, . . . , T − 1}. To this end, we use the following observation: given any sensor set S, and any time t ∈ {1, 2, . . . , T },


gt (S) = min E(kxt+1 (S)k2Qt +kut (S)k2Rt ) + gt+1 (S) ,
ut (S)

(20)
with boundary condition the gT +1 (S) = 0. In particular,
eq. (20) holds since

gt (S) = min E kxt+1 (S)k2Qt +kut (S)k2Rt )+
ut (S)

min

ut+1:T (S)

ht+1 [S, ut+1:T (S)]} ,

where one can easily recognize the second summand to match
the definition of gt+1 (S).

We prove Lemma 9 for t = T . From eq. (20), for t = T ,


gT (S) = minuT (S) E(kxT +1 (S)k2QT +kuT (S)k2RT )
2
= minuT (S) E(kA
T xT + BT uT (S) + wT kQT +

2
kuT (S)kRT ) ,
(21)
since xT +1 (S) = AT xT + BT uT (S) + wT , as per eq. (1);
we note that for notational simplicity we drop henceforth the
dependency of xT on S since xT is independent of uT (S),
which is the variable under optimization in the optimization
problem in (21). Developing eq. (21) we get:
gT (S) 
= minuT (S) E(uT (S)T BTT QT BT uT (S) + wTT QT wT +
T
T T
xT
T AT QT AT xT + 2xT AT QT BT uT (S)+

T T
2xT AT QT wT + 2uT (S)T BTT QT wT + kuT (S)k2RT )
= minuT (S) E(uT (S)T BTT QT BT uT (S) + kwT k2QT + 
2
T T
T
xT
T AT QT AT xT + 2xT AT QT BT uT (S) + kuT kRT ) ,
(22)
where the latter equality holds since wT has zero mean
and wT , xT , and uT (S) are independent. From eq. (22),
rearranging the terms, and using the notation in eq. (8),
gT (S) 
= minuT (S) E(uT (S)T (BTT QT BT + RT )uT (S)+

T T
T
kwT k2QT +xT
T AT QT AT xT + 2xT AT QT BT uT (S)
T
= minuT (S) E(kuT (S)k2MT +kwT k2QT +xT
T AT QT AT xT +
T T
2xT AT QT BT uT (S)
T
= minuT (S) E(kuT (S)k2MT +kwT k2QT +xT
T AT QT AT xT −
−1
T
T
2xT (−AT QT BT MT )MT uT (S)
2
2
T T
= minuT (S) E(kuT (S)k
 MT +kwT kQT +xT AT QT AT xT −
T
T
2xT KT M
 T uT (S)
= minuT (S) E(kuT (S) − KT xT k2MT +kwT k2QT +
T
T
xT
T (AT QT AT − KT MT KT )xT
= minuT (S) E(kuT (S) − KT xT k2MT +kwT k2QT +
T
xT
T (AT QT AT − ΘT )xT

= minuT (S) E(kuT (S) − KT xT k2MT +kwT k2QT +kxT k2NT
= minuT (S) E(kuT (S) − KT xT k2MT ) + tr (WT QT ) +
E(kxT k2NT ),
(23)
2
)
=
where
the
latter
equality
holds
since
E(kw
k
T QT



T
T
E tr wT QT wT = tr E(wT wT )QT = tr (WT QT ). Now
we note that
min E(kuT (S) − KT xT k2MT )

uT (S)

= E(kKT x̂T (S) − KT xT k2MT )

= tr ΘT ΣT |T (S) ,

(24)

since x̂T (S) is the Kalman estimator of the state xT , i.e.,
the minimum mean square estimator of xT , which implies
that KT x̂T (S) is the minimum mean square estimator of
KT xT (S) [19, Appendix E]. Substituting (24) back into
eq. (23), we get:

gT (S) = E(kxT k2NT ) + tr ΘT ΣT |T (S) + tr (WT QT ) ,
which proves that Lemma 9 holds for t = T .

We now prove that if Lemma 9 holds for t = l + 1, it
also holds for t = l. To this end, assume eq. (20) holds for
t = l + 1. Using the notation in eq. (8),


gl (S) = minul (S) E(kxl+1 (S)k2Ql +kul (S)k2Rl ) + gl+1 (S)
= minul (S) E(kxl+1 (S)k2Ql +kul (S)k2Rl )+


P
E(kxl+1 (S)k2Nl+1 ) + Tk=l+1 tr Θk Σk|k (S) +
tr (Wk Sk )]}
= minul (S) E(kxl+1 (S)k2Sl +kul (S)k2Rl )+
o

PT
k=l+1 [tr Θk Σk|k (S) + tr (Wk Sk )]

PT
= k=l+1 [tr Θk Σk|k (S) + tr (Wk Sk )]+
minul (S) E(kxl+1 (S)k2Sl +kul (S)k2Rl ).
(25)
In eq. (25), for the last summand in the last right-hand-side,
by following the same steps as for the proof of Lemma 9 for
t = T , we have:
2
minul (S) E(kxl+1 (S)k2Sl +ku
l (S)kRl ) =

E(kxl k2Nl ) + tr Θl Σl|l (S) + tr (Wl Ql ) ,

(26)

and ul (S) = Kl x̂l (S). Therefore, by substituting eq. (26) back
to eq. (25), we get:

PT
gl (S) = E(kxl k2Nl ) + k=l [tr Θk Σk|k (S) + tr (Wk Sk )].
(27)
which proves that if Lemma 9 holds for t = l +1, it also holds
for t = l. By induction, this also proves that Lemma 9 holds
for l = 1, and we already observed that g1 (S) matches the
original LQG cost in eq. (19), hence concluding the proof.
Proof of Theorem 1: The proof easily follows from
Lemma 9. Eq. (6) is a direct consequence
eq. (19), since

Pof
T
and
both E(xT
N
x
)
=
tr
Σ
N
1|1 1
1 1 1
t=1 tr (Wt St ) are
independent of the choice of the sensor set S. Second, (7)
directly follows from eq. (18).
A PPENDIX C: P ROOF

OF

T HEOREM 2

The following result is used in the proof of Theorem 2.
Proposition 2 (Monotonicity of cost function in eq. (6)).
Consider the cost function in eq.P
(6), namely, for any
 sensor
T
set S ⊆ V the set function
tr
Θ
Σ
(S)
. Then,
t t|t
t=1
for
any
sensor
sets
such
that
S
⊆
S
⊆
V,
it
holds
1
2 
 PT
PT
tr
Θ
Σ
(S
)
≥
tr
Θ
Σ
(S
)
.
t
1
t
2
t|t
t|t
t=1
t=1

Proof: Lemma 6 implies Σ1|1 (S1 )  Σ1|1 (S2 ), and
then, Corollary 1 implies Σt|t (S1 )  Σt|t (S2 ). Finally, for
any t = 1, 2,. . . , T , Lemma 4 implies tr Θt Σt|t (S1 ) ≥
tr Θt Σt|t (S2 ) , since each Θt is symmetric.
Proof of part (1) of Theorem 2 (Algorithm 2’s approximation quality): Using Proposition 2, and the supermodularity
ratio Definition 4, the proof of the upper bound exp(−γg )
in ineq. (12) follows the same steps as the proof of [26,
Theorem 1].
Proof of part (2) of Theorem 2 (Algorithm 1’s running
time): We compute Algorithm 1’s running time by adding the
running times of Algorithm 1’s lines 1 and 2:

a) Running time of Algorithm 1’s line 1: Algorithm 1’s
line 1 needs O(k|V|T n2.4 ) time. In particular, Algorithm 1’s
line 2 running time is the running time of Algorithm 2, whose
running time we show next to be O(k|V|T n2.4 ). To this end,
we first compute the running time of Algorithm 2’s line 1,
and then the running time of Algorithm 2’s lines 3–15. Algorithm 2’s line 1 needs O(n2.4 ) time, using the Coppersmith
algorithm for both matrix inversion and multiplication [27].
Then, Algorithm 2’s lines 3–15 are repeated k times, due to the
“while loop” between lines 3 and 15. We now need to find the
running time of Algorithm 2’s lines 4–14; to this end, we first
find the running time of Algorithm 2’s lines 4–12, and then the
running time of Algorithm 2’s lines 13 and 14. In more detail,
the running time of Algorithm 2’s lines 4–12 is O(|V|T n2.4 ),
since Algorithm 2’s lines 5–11 are repeated at most |V|
times and Algorithm 2’s lines 6–10, as well as line 11 need
O(T n2.4 ) time, using the Coppersmith-Winograd algorithm
for both matrix inversion and multiplication [27]. Moreover,
Algorithm 2’s lines 13 and 14 need O[|V|log(|V|)] time, since
line 13 asks for the minimum among at most |V| values of the
cost(·) , which takes O[|V|log(|V|)] time to be found, using,
e.g., the merge sort algorithm. In sum, Algorithm 2’s running
time is O[n2.4 + k|V|T n2.4 + k|V|log(|V|)] = O(k|V|T n2.4 ).
b) Running time of Algorithm 1’s line 2: Algorithm 1’s
line 2 needs O(n2.4 ) time, using the Coppersmith algorithm
for both matrix inversion and multiplication [27].
In sum, Algorithm 1’s running time is O(k|V|T n2.4 +
2.4
n ) = O(k|V|T n2.4 ).
A PPENDIX D: P ROOF

OF

T HEOREM 3

Proof of Theorem 3: We complete the proof by first
deriving a lower bound for the numerator of the supermodularity ratio γg , and then, by deriving an upper bound for the
denominator of the supermodularity ratio γg .
use the following notation: c , E(xT
1 N1 x1 ) +
PWe
T
⊆
V,
and time
t=1 tr (Wt St ), and for any sensor set S

t = 1, 2, . . . , T , ft (S) , tr Θt Σt|t (S) . Then, the cost
P
function g(S) in eq. (11) is written as g(S) = c+ Tt=1 ft (S),
due to eq. (19) in Lemma 9.
a) Lower bound for the numerator of the supermodularity ratio γg : Per the supermodularity ratio Definition 4, the
numerator of the submodularity ratio γg is of the form
T
X

[ft (S) − ft (S ∪ {v})],

(28)

t=1

for some sensor set S ⊆ V, and sensor v ∈ V; to lower bound
the sum in (28), we lower bound each ft (S) − ft (S ∪ {v}).
To this end, from eq. (16) in Lemma 5, observe
X
T
C̄i,t
C̄i,t ]−1.
Σt|t (S ∪ {v}) = [Σ−1
t|t−1 (S ∪ {v}) +
i∈S∪{v}

PT

T
=
Define Ωt = Σ−1
i∈S C̄i,t C̄i,t , and Ω̄t
t|t−1 (S) +
P
T
−1
T
Σt|t−1 (S ∪{v})+ i∈S C̄i,t C̄i,t ; using the Woodbury identity

Lemmata 4 and 2,

in Lemma 3,
ft (S ∪ {v}) =
tr



−
tr Θt Ω̄−1
t
−1 T
Θt Ω̄t C̄v,t (I

g(S) − g(S ∪ {v}) ≥ l

T −1
.
) C̄v,t Ω̄−1
+ C̄v,t Ω̄t−1 C̄v,t
t

≥l

T
X

= ltr Φ


−1 T −1
T
C̄v,t Ω̄t−1 ≥
tr Θt Ω̄−1
t C̄v,t (I + C̄v,t Ω̄t C̄v,t )

−1 T −1
T
C̄v,t Ω̄t−1 ,
tr Θt Ω̄−1
t C̄v,t (I + C̄v,t Ω̄t C̄v,t )

≥ lλmin



≥ tr Θt Ω̄−1
where ineq. (29) holds because tr Θt Ω−1
t .
t
≥ tr Θt Ω̄t−1
In particular, the inequality tr Θt Ω−1
t
is implied as follows: Lemma 6 implies Σ1|1 (S) 
Σ1|1 (S ∪ {u}). Then, Corollary 2 implies Σt|t−1 (S) 
Σt|t−1 (S ∪ {v}), and as a result, Lemma 1 implies
Σt|t−1 (S)−1  Σt|t−1 (S ∪ {u})−1. Now, Σt|t−1 (S)−1 
Σt|t−1 (S ∪ {u})−1 and the definition of Ωt and of Ω̄t
imply Ωt  Ω̄t . Next, Lemma 1 implies Ωt−1  Ω̄−1
t .
As a result, since also Θt is a symmetric
matrix,
Lem

ma 4 gives the desired inequality tr Θt Ω−1
≥ tr Θt Ω̄−1
.
t
t
Continuing from the ineq. (29),
ft (S) − ft (S ∪ {v}) ≥


−1 T −1
−1 T
≥
tr C̄v,t Ω̄−1
t Θt Ω̄t C̄v,t (I + C̄v,t Ω̄t C̄v,t )


−1 T
T −1
)tr C̄v,t Ω̄−1
λmin ((I + C̄v,t Ω̄−1
t Θt Ω̄t C̄v,t , (30)
t C̄v,t )

where ineq. (30) holds due to Lemma 2. From ineq. (30),



−1 T
−1
T
≥ λ−1
max (I + C̄v,t Σt|t (∅)C̄v,t )tr C̄v,t Ω̄t Θt Ω̄t C̄v,t

T
X

Θt

t=1
T
X
t=1

(29)




−1
−1 T
T
,
= λ−1
max (I + C̄v,t Σt|t (∅)C̄v,t )tr Θt Ω̄t C̄v,t C̄v,t Ω̄t
(31)
where we used Ω̄−1
 Σt|t (∅), which holds because of the
t
−1
following: the definition of Ω̄t implies Ω̄t  Σt|t−1
(S ∪ {v}),
−1
and as a result, from Lemma 1 we get Ω̄t  Σt|t−1 (S ∪{v}).
In addition, Corollary 2 and the fact that Σ1|1 (S ∪ {v}) 
Σ1|1 (∅), which holds due to Lemma 6, imply Σt|t−1 (S ∪
{v})  Σt|t−1 (∅). Finally, from eq. (16) in Lemma 5 it is
Σt|t−1 (∅) = Σt|t (∅). Overall, the desired inequality Ω̄−1

t
Σt|t (∅) holds.
Consider a time t′ ∈ {1, 2 . . . , T } such that for any time
−1
−1
−1 T
T
t ∈ {1, 2, . . . , T } it is Ω̄−1
t′ C̄v,t′ C̄v,t′ Ω̄t′  Ω̄t C̄v,t C̄v,t Ω̄t ,
−1 T
−1
and let Φ be the matrix Ω̄t′ C̄v,t′ C̄v,t′ Ω̄t′ ; similarly, let l be
T
the mint∈{1,2...,T },u∈V λ−1
max (I + C̄v,t Σt|t (∅)C̄v,t ). Summing
ineq. (31) across all times t ∈ {1, 2 . . . , T }, and using



tr (Θt Φ)

t=1

ft (S) − ft (S ∪ {v}) =


+
− tr Θt Ω̄−1
tr Θt Ω−1
t
t

−1 T
−1
−1 T
= λ−1
max (I + C̄v,t Ω̄t C̄v,t )tr C̄v,t Ω̄t Θt Ω̄t C̄v,t

−1
T
tr Θt Ω̄−1
t C̄v,t C̄v,t Ω̄t

t=1

Therefore, for any time t ∈ {1, 2 . . . , T },

ft (S) − ft (S ∪ {v}) ≥

T
X

!

Θt

!

tr (Φ)

> 0,
PT
which is non-zero because t=1 Θt ≻ 0 and Φ is a non-zero
positive semi-definite matrix.
Finally, we lower bound tr (Φ), using Lemma 2:

−1
T
tr (Φ) = tr Ω̄−1
t′ C̄v,t′ C̄v,t′ Ω̄t′

T
= tr Ω̄−2
t′ C̄v,t′ C̄v,t′

T
≥ λmin (Ω̄−2
t′ )tr C̄v,t′ C̄v,t′

T
= λ2min (Ω̄−1
t′ )tr C̄v,t′ C̄v,t′

T
(32)
≥ λ2min (Σt′ |t′ (V))tr C̄v,t
′ C̄v,t′ ,
where ineq. (32) holds because Ω̄−1
t′  Σt′ |t′ (V). In particular,
′
′
the inequality Ω̄−1

Σ
(S
∪
{v}) is derived by applying
t |t
t′
T
T
′
= Σ−1
C̄v,t
Lemma 1 to the inequality Ω̄t  Ω̄t′ + C̄v,t
t′ |t′ (S ∪
{v}), where the equality holds by the definition of Ω̄t′ . In addition, due to Lemma 6 it is Σ1|1 (S ∪ {v})  Σ1|1 (V), and as
a result, from Corollary 1 it also is Σt′ |t′ (S ∪{v})  Σt′ |t′ (V).
Overall, the desired inequality Ω̄−1
t′  Σt′ |t′ (V) holds.
b) Upper bound for the denominator of the supermodularity ratio γg : The denominator of the submodularity ratio γg
is of the form
T
X
[ft (S ′ ) − ft (S ′ ∪ {v})],
t=1

for some sensor set S ′ ⊆ V, and sensor v ∈ V; to upper bound
it, from eq. (16) in Lemma 5 of Appendix A, observe
X
T
′
C̄i,t
C̄i,t ]−1,
Σt|t (S ′ ∪ {v}) = [Σ−1
t|t−1 (S ∪ {v}) +
i∈S ′ ∪{v}

PT

′
T
and let Ht = Σ−1
i∈S ′ C̄i,t C̄i,t , and H̄t =
t|t−1 (S ) +
P
T
T
′
Σ−1
i∈S ′ C̄i,t C̄i,t ; using the Woodbury ident|t−1 (S ∪ {v}) +
tity in Lemma 3,

ft (S ′ ∪ {v}) = tr Θt H̄t−1 −

T −1
T
) C̄v,t H̄t−1 .
(I + C̄v,t H̄t−1 C̄v,t
tr Θt H̄t−1 C̄v,t

Therefore,

T
X

t=1
T
X
t=1

[ft (S ′ ) − ft (S ′ ∪ {v})] =


[tr Θt Ht−1 − tr Θt H̄t−1 +


T
T −1
tr Θt H̄t−1 C̄v,t
(I + C̄v,t H̄t−1 C̄v,t
) C̄v,t H̄t−1 ] ≤
T
X


[tr Θt Ht−1 +

t=1

T −1
T
) C̄v,t H̄t−1 ],
(I + C̄v,t H̄t−1 C̄v,t
tr Θt H̄t−1 C̄v,t
(33)

where ineq. (33) holds since tr Θt H̄t−1 is non-negative. In
eq. (33), the second term in the sum is upper bounded as
follows, using Lemma 2:

T −1
T
) C̄v,t H̄t−1 =
(I + C̄v,t H̄t−1 C̄v,t
tr Θt H̄t−1 C̄v,t

T −1
T
≤
)
(I + C̄v,t H̄t−1 C̄v,t
tr C̄v,t H̄t−1 Θt H̄t−1 C̄v,t

−1 T −1
−1 T
−1
tr C̄v,t H̄t Θt H̄t C̄v,t λmax [(I + C̄v,t H̄t C̄v,t ) ] =
 −1
T
T
)≤
λmin (I + C̄v,t H̄t−1 C̄v,t
tr C̄v,t H̄t−1 Θt H̄t−1 C̄v,t

−1
−1 T
−1
T
), (34)
tr C̄v,t H̄t Θt H̄t C̄v,t λmin (I + C̄v,t Σt|t (V)C̄v,t

T
T
since λmin (I + C̄v,t H̄t−1 C̄v,t
) ≥ λmin (I + C̄v,t Σt|t (V)C̄v,t
),
−1
−1
because H̄t  Σt|t (V). In particular, the inequality H̄t 
T
Σt|t (V) is derived as follows: first, it is H̄t  H̄t + C̄v,t
C̄v,t =
′
−1
Σt|t (S ∪ {v}) , where the equality holds by the definition of
H̄t , and now Lemma 1 implies H̄t−1  Σt|t (S ′ ∪ {v}). In addition, Σt|t (S ′ ∪ {v})  Σt|t (V) is implied from Corollary 1,
since Lemma 6 implies Σ1|1 (S ′ ∪ {v})  Σ1|1 (V). Overall,
the desired inequality H̄t−1  Σt|t (V) holds.
T
Let l′ = maxt∈{1,2...,T },v∈V λ−1
min (I + C̄v,t Σt|t (V)C̄v,t ).
From ineqs. (33) and (34),
PT
[ft (S ′ ) − ft (S ′ ∪ {v})] ≤


Pt=1
(35)
T
−1
T
C̄v,t H̄t−1 ].
+ l′ tr Θt H̄t−1 C̄v,t
t=1 [tr Θt Ht

Consider times t′ ∈ {1, 2 . . . , T } and t′′ ∈ {1, 2 . . . , T } such
that for any time t ∈ {1, 2, . . . , T }, it is Ht−1
 Ht−1 and
′
−1 T
−1
−1
−1 T
H̄t′′ C̄v,t′′ C̄v,t′′ H̄t′′  H̄t C̄v,t C̄v,t H̄t , and let Ξ = Ht−1
′
−1
T
and Φ′ = H̄t−1
′ C̄v,t′ C̄v,t′ H̄t′ . From ineq. (35), and Lemma 4,
T
X

[ft (S ′ ) − ft (S ′ ∪ {v})] ≤

t=1

T
X

[tr (Θt Ξ) + l′ tr (Θt Φ′ )] ≤

t=1

tr Ξ

T
X

Θt

t=1

!

′

+ l tr Φ

′

T
X

t=1
T
X

(tr (Ξ) + l′ tr (Φ′ ))λmax (

Θt

!

≤

Θt ).

(36)

t=1

Finally, we upper bound tr (Ξ)+l′ tr (Φ′ ) in ineq. (36), using
Lemma 2:
tr (Ξ) + l′ tr (Φ′ ) ≤

tr Ht−1
+
′

l′ λ2max (H̄t−1
′′ )tr


tr Σt′ |t′ (∅) +



T
≤
C̄v,t
′′ C̄v,t′′
′ 2
l λmax (Σt′′ |t′′ (∅))tr

(37)

T
C̄v,t
′′ C̄v,t′′ ,

(38)

where ineq. (38) holds because Ht−1
 Σt′ |t′ (∅), and simi′
larly, H̄t−1
 Σt′′ |t′′ (∅). In particular, the inequality Ht−1

′′
′
Σt′ |t′ (∅) is implied as follows: first, by the definition of Ht′ ,
it is Ht−1
= Σt′ |t′ (S ′ ); and finally, Corollary 1 and the fact
′
that Σ1|1 (S ′ )  Σ1|1 (∅), which holds due to Lemma 6, imply
Σt′ |t′ (S ′ )  Σt′ |t′ (∅). In addition, the inequality H̄t−1

′′
Σt′′ |t′′ (∅) is implied as follows: first, by the definition of H̄t′′ ,
′
it is H̄t′′  Σ−1
t′′ |t′′ −1 (S ∪ {v}), and as a result, Lemma 1
−1
implies H̄t′′  Σt′′ |t′′ −1 (S ′ ∪ {v}). Moreover, Corollary 2
and the fact that Σ1|1 (S ∪ {v})  Σ1|1 (∅), which holds due to
Lemma 6, imply Σt′′ |t′′ −1 (S ′ ∪ {v})  Σt′′ |t′′ −1 (∅). Finally,
from eq. (16) in Lemma 5 it is Σt′′ |t′′ −1 (∅) = Σt′′ |t′′ (∅).
Overall, the desired inequality H̄t−1
′′  Σt′′ |t′′ (∅) holds.
A PPENDIX E: P ROOF

OF

T HEOREM 4

For the proof of Theorem 4, we use Proposition 1, which
we prove in Appendix E, and Lemmata 10, 11, and 12 below.
Lemma 10. For any t = 1, 2, . . . , T ,
Θt = AT
t St At + Qt−1 − St−1 .
Proof of Lemma 10: Using the Woobury identity in
Lemma 3, and the notation in eq. (8),
−1
+ Bt Rt−1 BtT )−1 At
Nt = AT
t (St
−1 T
= AT
t (St − St Bt Mt Bt St )At

= AT
t St At − Θt .
The latter, gives Θt = AT
t St At −Nt . In addition, from eq. (8),
−Nt = Qt−1 − St−1 , since St = Qt + Nt+1 .
PT
T
T
Lemma 11. t=1 AT
1 A2 · · · At Qt At At−1 · · · A1 ≻ N1 if
and only if
T
X

T
T
AT
1 A2 · · · At−1 Θt At−1 At−2 · · · A1 ≻ 0.

t=1

Proof of Lemma 11: For i = t − 1, t − 2, . . . , 1, we preand post-multiply the identity in Lemma 10 with AT
i and Ai ,
respectively:
Θt = AT
t St At + Qt−1 − St−1 ⇒
T
T
T
AT
t−1 Θt At−1 = At−1 At St At At−1 + At−1 Qt−1 At−1 −
T
At−1 St−1 At−1 ⇒
T
T
T
AT
t−1 Θt At−1 = At−1 At St At At−1 + At−1 Qt−1 At−1 −
Θt−1 + Qt−2 − St−2 ⇒
T
T
Θt−1 + AT
t−1 Θt At−1 = At−1 At St At At−1 +
T
At−1 Qt−1 At−1 + Qt−2 − St−2 ⇒
... ⇒
T
T
Θ2 + AT
2 Θ3 A2 + . . . + A2 · · · At−1 Θt At−1 · · · A2 =
T
T
T
A2 · · · At St At · · · A2 + A2 · · · AT
t−1 Qt−1 At−1 · · · A2 +
. . . + AT
2 Q2 A2 + Q1 − S1 ⇒
T
T
Θ1 + AT
1 Θ2 A1 + . . . + A1 · · · At−1 Θt At−1 · · · A1 =
T
T
T
A1 · · · At St At · · · A1 + A1 · · · AT
t−1 Qt−1 At−1 · · · A1 +
. . . + AT
Q1 A1 − N1 ⇒
1
PT
AT · · · AT
t−1 Θt At−1 · · · A1 =
t=1
PT1
T
T
A
·
t=1 1 · · At Qt At · · · A1 − N1 .
(39)

The last equality in eq. (39) implies Lemma 11.

A PPENDIX F: P ROOF

Lemma 12.
for any t = 1, 2, . . . , T that At is
PConsider
T
T T
T
invertible.
A
A
t=1 1 2 · · · At−1 Θt At−1 At−2 · · · A1 ≻ 0 if
and only if
T
X
Θt ≻ 0.
t=1

Proof of Lemma 12: Let Ut = At−1 At−2 · · · A1 .
We Pfirst prove that for any non-zero vector z, if
T
T T
T
it is
t=1 A1 A2 · · · At−1 Θt At−1 At−2 · · · A1 ≻ 0, then
PT
T
t=1 z Θt z > 0. In particular, since Ut is invertible, —
because for any t ∈ {1, 2, . . . , T }, At is,—
PT
PT
T −⊤ T
T
Ut Θt Ut Ut−1 z
t=1 z Θt z = Pt=1 z Ut

(40)
T
T
= t=1 tr φt φT
t Ut Θ t Ut ,

where we let φt = Ut−1 z. Consider a time t′ such that for any
T
time t ∈ {1, 2 . . . , T }, φt′ φT
t′  φt φt . From eq. (40), using
Lemmata 4 and 2,
T
X

z T Θt z ≥

t=1

T
X

T
tr φt′ φT
t′ Ut Θt Ut

t=1

≥ tr φt′ φT
t′

T
X



UtT Θt Ut

t=1

finally provePthat for any non-zero vector z, if
PWe
T
T
T
T
t=1 Θt ≻ 0, then
t=1 zA1 · · · At−1 Θt At−1 · · · A1 z ≻ 0.
In particular,

tr ξtT Θt ξt ,

(41)

where we let ξt = Ut z. Consider time t′ such that for any
time t ∈ {1, 2 . . . , T }, ξt′ ξtT′  ξt ξtT . From eq. (40), using
Lemmata 4 and 2,
!
T
T
X
X

T
T
tr ξt Θt ξt ≥ tr ξt′ ξt′
Θt
t=1

t=1

T
X
Θt )
≥ tr ξt′ ξt′ λmin (


T

t=1

T
X

= kξt′ k22 λmin (

t=1

Σt|t =Wt =0

= xT
1 N1 x1 ,

(42)
since E(kx1 k2N1 ) = xT
N
x
,
because
x
is
known
(Σ
=
0),
1
1
1
1|1
1
and Σt|t and Wt are zero. In addition, for u1:T = (0, 0, . . . , 0),
the objective function in the noiseless perfect state information
LQG problem in eq. (14) is
PT
2
2
t=1 [kxt+1 kQt +kut (xt )kRt ] Σt|t =Wt =0
PT
(43)
= t=1 xT
Qx
PT t+1 T t Tt+1 T
T
= x1 t=1 A1 A2 · · · At Qt At At−1 · · · A1 x1 ,
since xt+1 = At xt = At At−1 xt−1 = . . . = At At−1 · · · A1 x1
when all u1 , u2 , . . . , uT are zero.
From eqs. (42) and (43), the inequality
T
X

T
X
t=1

t=1

t=1

[kxt+1 k2Qt +kut (xt )k2Rt ]

N1 ≺

> 0.

t=1

u1:T

T
X

T
T
AT
1 A2 · · · At Qt At At−1 · · · A1 x1

holds for any non-zero x1 if and only if

t=1

T
X

P ROPOSITION 1

t=1

!

T
X
UtT Θt Ut )
= kφt′ k22 λmin (

z T UtT Θt Ut z =

min

T
xT
1 N1 x1 < x1

T
X

UtT Θt Ut )
≥ tr φt′ φT
t′ λmin (

T
X

OF

Proof of Proposition 1: For any initial condition x1 ,
eq. (19) in Lemma 9 implies for the noiseless perfect state
information LQG problem in eq. (14):

Θt )

t=1

> 0.
Proof of Theorem 4: Theorem 4 follows from the sequential application of Proposition 1 and Lemmata 11, and 12.

T
AT
1 · · · At Qt At At−1 · · · A1 .

