  We develop a fast algorithm for Kalman Filter applied to the random walk
forecast model. The key idea is an efficient representation of the estimate
covariance matrix at each time-step as a weighted sum of two contributions -
the process noise covariance matrix and a low rank term computed from a
generalized eigenvalue problem, which combines information from the noise
covariance matrix and the data. We describe an efficient algorithm to update
the weights of the above terms and the computation of eigenmodes of the
generalized eigenvalue problem (GEP). The resulting algorithm for the Kalman
filter with a random walk forecast model scales as $\bigO(N)$ in memory and
$\bigO(N \log N)$ in computational cost, where $N$ is the number of grid
points. We show how to efficiently compute measures of uncertainty and
conditional realizations from the state distribution at each time step. An
extension to the case with nonlinear measurement operators is also discussed.
Numerical experiments demonstrate the performance of our algorithms, which are
applied to a synthetic example from monitoring CO$_2$ in the subsurface using
travel time tomography.
