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 ${O(d^3)}$ time and ${O(d^2)}$ space per time step, where ${d}$ 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 ${O(k^2d)}$ or ${O(k^2d + kd \log d)}$ time and space per time step, where k is the rank of the perturbation and in general ${k \ll d}$), 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.

Journal of Computational and Graphical Statistics, 23(2): 316–339