  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 logdet 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).
