Randomized Matrix Factorization for Kalman Filtering

This paper discusses an application of randomized algorithms for matrix factorization to the classic Kalman filtering technique to estimate the state of a linear dynamical system. We consider the case when the state space is high dimensional leading to a high computational complexity in evaluating the state estimate and the estimation error covariance. We formalize two approaches based on the use of randomized matrix factorization - the first based on a singular value decomposition approach to Kalman filtering and the second based on approximating the prediction step using a randomized approach. We provide an analytic lower bound in the positive semidefinite sense on the estimation error covariance matrix for the first approach, and a lower and an upper bound for the same in the second approach, all of which hold with high probability. Finally, we provide numerical evidence validating the analytic results and also provide insight into the computational gain in the use of the two approaches on synthetically generated data.