Nested bounds for the constrained sensor placement problem

The objective of this paper is to find numerical upper bounds on the optimal solution to the sensor placement problem. Given noisy measurements and knowledge of the state correlation matrix, the sensor placement problem can be formulated as an integer programming problem using a linear minimum mean squared error estimator. Since finding the optimal placements of a fixed number of sensors in a large network is computationally infeasible, finding bounds for the optimal solution is a fundamental task. In this paper we present a family of nested bounds using matrix pencils and their generalized eigenvalues that upper bound the optimal performance. In the analysis we consider nodes that we want to place sensors and other nodes where we cannot or do not want to place sensors. Finally we compare the upper bounds with the optimal solution using simulations on a 5 by 5 grid network.