Sensor placement minimizing the state estimation mean square error: Performance guarantees of greedy solutions

This paper studies selecting a subset of the system’s output to minimize the state estimation mean square error (MSE). This results in the maximization problem of a set function defined on possible sensor selections subject to a cardinality constraint. We consider to solve it approximately by a greedy search. Since the MSE function is not submodular nor supermodular, the well-known performance guarantees for the greedy solutions do not hold in the present case. Thus, we use the quantities—the submodularity ratio and the curvature— to evaluate the degrees of submodularity and supermodularity of the objective function. By using the properties of the MSE function, we approximately compute these quantities and derive a performance guarantee for the greedy solutions. It is shown that the guarantee is less conservative than those in the existing results.