Fast Kalman Filtering and Forward–Backward Smoothing via a Low-Rank Perturbative Approach

Kalman filtering-smoothing is a fundamental tool in statistical time-series analysis. However, standard implementations of the Kalman filter-smoother require <i>O</i>(<i>d</i>³) time and <i>O</i>(<i>d</i>²) space per time step, where <i>d</i> is the dimension of the state variable, and are therefore impractical in high-dimensional problems. In this article we note that if a relatively small number of observations 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 just <i>O</i>(<i>k</i>²<i>d</i>) or <i>O</i>(<i>k</i>²<i>d</i> + <i>kd</i>log <i>d</i>) time and space per time step, where <i>k</i> is the rank of the perturbation and in general <i>k</i> ≪ <i>d</i>), using fast methods from numerical linear algebra. We justify our approach and give bounds on the rank of the perturbation as a function of the desired accuracy. For the case of smoothing, we also quantify the error of our algorithm because of the low-rank approximation and show that it can be made arbitrarily low at the expense of a moderate computational cost. We describe applications involving smoothing of spatiotemporal neuroscience data. This article has online supplementary material.