Extensions and Applications of the Paige-Saunders Kalman Filter and Smoother

Sivan Toledo
Tel-Aviv

In 1977 Chris Paige and Mike Saunders invented a QR factorization algorithm for a class of structured sparse matrices and showed how to use this algorithm to perform Kalman filtering and smoothing. These results exploit an earlier characterization of Kalman filtering as a linear least-squares problem by Duncan and Horn. The Kalman filtering and smoothing algorithms proposed by Page and Saunders are very different from all other variants. Unfortunately, they remained obscure, unused, and almost uncited until recently. In the talk I will describe their algorithm along with several extensions and applications. One extension allows the state vector that the filter or smoother estimates to grow and/or shrink between time steps. This mechanism also allows modeling parameters that only appear in a particular time step, like some sensor parameters. A second extension allows the state vectors to include parameters that are time invariant; this can be used for other sensor parameters, like sensor bias. One unusual application that the talk will present is non-linear Kalman smoothing; it turns out that when the Levenberg-Marquardt non-linear least-squares solver is applied to a Kalman smoothing problem, most of the work of every iteration can be efficiently performed by an invocation of the Paige-Saunders algorithm. Finally, the talk will describe a highly-parallel and work-efficient version of the Paige-Saunders algorithm, allowing (at least in principle) Kalman smoothing of very long dynamic systems on modern multicore processors and GPUs. Some of the algorithms and extensions have been implemented in a software library called UltimateKalman, which the talk will also mention.