# Fast Kalman Filter using Hierarchical-matrices and low-rank perturbative approach

Source: [Fast Kalman Filter using Hierarchical-matrices and low-rank perturbative approach](<https://www.sota2.com/research/paper/68fa51d31e209131ce9767b7>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2026-06-05T05:00:26.567Z

Authors: Arvind K. Saibaba, Eric Miller, Peter K. Kitanidis

Published: 2014-05-09T16:11:45.000Z

## Abstract

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.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/1405.2276>)

[PDF](<https://arxiv.org/pdf/1405.2276.pdf>)
