Comm, Control & Signal Pro Seminar: David Hartman, "Supermodular Solution in Kalman Filtering"
Communication, Control and Signal Processing Seminar
Supermodular Solution to the Non-Uniform Sampling Problem in Kalman Filtering
University of Maryland
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 (MMSE) 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 the assumption that the covariance matrix for the measurement noise is diagonal.