  Given a linear dynamical system, we consider the problem of constructing an
approximate system using only a subset of the sensors out of the total set such
that the observability Gramian of the new system is approximately equal to that
of the original system. Our contributions are as follows. First, we present a
randomized algorithm that samples the sensors with replacement as per specified
distributions. For specific metrics of the observability Gramian such as the
trace or the maximum eigenvalue, we derive novel bounds on the number of
samples required to yield a high probability lower bound on the metric
evaluated on the approximate Gramian. Second, with a different distribution, we
derive high probability bounds on other standard metrics used in sensor
selection, including the minimum eigenvalue or the trace of the Gramian
inverse. This distribution requires a number of samples which is larger than
the one required for the trace and the maximum eigenvalue, but guarantees
non-singularity of the approximate Gramian if the original system is observable
with high probability. Third, we demonstrate how the randomized procedure can
be used for recursive state estimation using fewer sensors than the original
system and provide a high probability upper bound on the initial error
covariance. We supplement the theoretical results with several insightful
numerical studies and comparisons with competing greedy approaches.
