Fast Kalman filter using hierarchical matrices and a low-rank perturbative approach. (6th January 2015)

• Record Type: Journal Article
• Authors: Saibaba, Arvind K; Miller, Eric L; Kitanidis, Peter K
• Is Part Of: Inverse problems. Volume 31:Number 1(2015:Jan.)
• Publication Date: 2015-01-06
• Subjects: Kalman filter -- hierarchical matrices -- uncertainty quantification -- random walk forecast model; Inverse problems (Differential equations) -- Periodicals; 515.357
• DOI: 10.1088/0266-5611/31/1/015009
• Languages: English
• ISSNs: 0266-5611

Abstract

Abstract: We develop a fast algorithm for a 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 preceding terms and the computation of eigenmodes of the generalized eigenvalue problem. The resulting algorithm for the Kalman filter with a random walk forecast model scales as in memory and 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 CO2 in the subsurface using travel-time tomography.