Randomized Kaczmarz EM for Large-Scale State-Space Models

Abstract

The Expectation–Maximization (EM) algorithm is a standard tool for estimating linear state-space models, but its reliance on dense covariance matrices makes it difficult to use in large dimensions. We show that, for systems with sparse or banded dynamics and simple noise structures, EM can be run without ever forming these matrices. The key step is to replace the usual smoother with randomized Kaczmarz iterations in information form, reducing the covariance memory cost to ${{\mathcal{O}}}(n)$ and yielding a total footprint of ${{\mathcal{O}}}(Nn)$ for the state trajectory, versus ${{\mathcal{O}}}\left({N{n^2}}\right)$ for the classical smoother. The overall behavior of EM is preserved: the likelihood still improves up to a tolerance set by the iterative solver, and shrinking this tolerance recovers the classical updates. Experiments on large advection–diffusion models illustrate the payoff: RK-EM matches standard EM at moderate sizes and continues to operate at n = 65,536, where traditional methods run out of memory. When the system is sparse and reasonably well observed, this matrix-free version offers a practical alternative to ensemble smoothers, with no localization or inflation parameters to tune.