Fast Kalman filtering via a low-rank perturbative approach
Liam Paninski, Kamiar Rahnama Rad, Jonathan H. Huggins · 2011
Kalman filtering is a fundamental tool in statistical time series analysis: it is computationally tractable in many real-world situations, implements the optimal Bayesian filter in the linear-Gaussian setting, and serves as a key step in the inference algorithms for a wide variety of nonlinear and non-Gaussian models. However, standard implementations of the Kalman filter require O(N 3 ) time and O(N 2 ) space per timestep, where N is the dimension of the state variable, and are therefore impractical in many high-dimensional problems. In this paper we note that if a relatively small number of observations with low signal-to-noise (SNR) are available per time step, the Kalman equations may be approximated in terms of a low-rank perturbation of the prior state covariance matrix in the absence of any observations. In many cases this approximation may be computed and updated very efficiently (often in justO(N) or O(N log N) time and space per timestep), using fast methods from numerical linear algebra. This opens up the possibility of real-time adaptive experimental design and optimal control in systems of much larger dimension than was previously feasible. We describe an application involving smoothing of spatiotemporal neuroscience data.