Near-Optimal Solution to the Non-Uniform Sampling Problem in Kalman Filtering
Authors :
Hartman, David
Conference : 2019 IEEE Conference on Decision and Control (CDC) pp. 6404-6411 , Nice, France
Date: December 11 - December 13, 2019
In the optimal sampling problem, we are interested in selecting the optimal subset of times to sample a sensor such that the mean square estimation error (MSE) between the unobserved states and the estimated states is minimized. In this problem, the states evolve according to a discrete, LTI system and the sensor takes measurements according to a discrete, LTI system. A Kalman Filter recursively estimates the evolving states based on the sensor measurements. Ideally, we would select all available times (in the horizon of interest) to sample the sensor for estimating the states. However, there are communication and energy costs affiliated with sampling and therefore we aim to minimize the estimation error when the number of times we can sample is fixed. There have been multiple attempts to solve this problem by relaxing the original problem, which is NP-hard. Such relaxations allow for nice algorithms, but provide no guarantees on the gap between the solution of the relaxed problem and the solution of the original problem. We leverage the idea of supermodularity in discrete optimization to show a greedy solution to the sampling problem will produce a near-optimal solution with an approximation factor. To prove the supermodularity property for the mean squared estimation error as a function of samples, we make a few assumptions: the covariance matrices for the system and measurement noise are diagonal matrices of the form constant times identity with certain restrictions on the constant: C and A matrices only have positive elements.
Download Full Paper