Stabilized BFGS approximate Kalman filter

Alexander  Bibov; Heikki Haario; Antti  Solonen

doi:10.3934/ipi.2015.9.1003

Article Contents

2015, Volume 9, Issue 4: 1003-1024. Doi: 10.3934/ipi.2015.9.1003

This issue Previous Article Application of mixed formulations of quasi-reversibility to solve ill-posed problems for heat and wave equations: The 1D case Next Article Homogenization of the transmission eigenvalue problem for periodic media and application to the inverse problem

Stabilized BFGS approximate Kalman filter

1.
LUT Mafy - Department of Mathematics and Physics, Lappeenranta University Of Technology, P.O. Box 20 FI-53851
2.
Department of Mathematics and Physics, Lappeenranta University of Technology, P.O.Box 20, FIN-53851 Lappeenranta
3.
Lappeenranta University of Technology, Department of Mathematics and Physics, Lappeenranta, P.O. Box 20 FI-53851

Received: July 31, 2014

Revised: April 30, 2015

Published: October 2015

Abstract Related Papers Cited by

Abstract

The Kalman filter (KF) and Extended Kalman filter (EKF) are well-known tools for assimilating data and model predictions. The filters require storage and multiplication of $n\times n$ and $n\times m$ matrices and inversion of $m\times m$ matrices, where $n$ is the dimension of the state space and $m$ is dimension of the observation space. Therefore, implementation of KF or EKF becomes impractical when dimensions increase. The earlier works provide optimization-based approximative low-memory approaches that enable filtering in high dimensions. However, these versions ignore numerical issues that deteriorate performance of the approximations: accumulating errors may cause the covariance approximations to lose non-negative definiteness, and approximative inversion of large close-to-singular covariances gets tedious. Here we introduce a formulation that avoids these problems. We employ L-BFGS formula to get low-memory representations of the large matrices that appear in EKF, but inject a stabilizing correction to ensure that the resulting approximative representations remain non-negative definite. The correction applies to any symmetric covariance approximation, and can be seen as a generalization of the Joseph covariance update.
We prove that the stabilizing correction enhances convergence rate of the covariance approximations. Moreover, we generalize the idea by the means of Newton-Schultz matrix inversion formulae, which allows to employ them and their generalizations as stabilizing corrections.

Keywords:

Mathematics Subject Classification: Primary: 60G35, 93E11; Secondary: 62M20.

Citation:

Related Papers

Cited by

References

[1]	J. L. Anderson, An adaptive covariance inflation error correction algorithm for ensemble filters, Tellus-A, 59 (2006), 210-224.
[2]	H. Auvinen, J. Bardsley, H. Haario and T. Kauranne, Large-scale Kalman filtering using the limited memory BFGS method, Electronic Transactions on Numerical Analysis, 35 (2009), 217-233.
[3]	H. Auvinen, J. Bardsley, H. Haario and T. Kauranne, The variational Kalman filter and an efficient implementation using limited memory BFGS, International Journal on Numerical methods in Fluids, 64 (2009), 314-335.doi: 10.1002/fld.2153.
[4]	J. Bardsley, A. Parker, A. Solonen and M. Howard, Krylov space approximate Kalman filtering, Numerical Linear Algebra with Applications, 20 (2013), 171-184.doi: 10.1002/nla.805.
[5]	A. Barth, A. Alvera-Azcárate, K.-W. Gurgel, J. Staneva, A. Port, J.-M. Beckers and E. Stanev, Ensemble perturbation smoother for optimizing tidal boundary conditions by assimilation of high-frequency radar surface currents - application to the German bight, Ocean Science, 6 (2010), 161-178.doi: 10.5194/os-6-161-2010.
[6]	A. Ben-Israel, A note on iterative method for generalized inversion of matrices, Math. Computation, 20 (1966), 439-440.doi: 10.1090/S0025-5718-66-99922-4.
[7]	G. J. Bierman, Factorization Methods for Discrete Sequential Estimation, Vol. 128, Academic Press, 1977.
[8]	R. Bucy and P. Joseph, Filtering for Stochastic Processes with Applications to Guidance, John Wiley & Sons, New York, 1968.
[9]	R. Byrd, J. Nocedal and R. Schnabel, Representations of quasi-Newton matrices and their use in limited memory methods, Mathematical Programming, 63 (1994), 129-156.doi: 10.1007/BF01582063.
[10]	M. Cane, A. Kaplan, R. Miller, B. Tang, E. Hackert and A. Busalacchi, Mapping tropical pacific sea level: Data assimilation via reduced state Kalman filter, Journal of Geophysical Research, 101 (1996), 22599-22617.doi: 10.1029/96JC01684.
[11]	L. Canino, J. Ottusch, M. Stalzer, J. Visher and S. Wandzura, Numerical solution of the Helmholtz equation in 2d and 3d using a high-order Nyström discretization, Journal of Computational Physics, 146 (1998), 627-663.doi: 10.1006/jcph.1998.6077.
[12]	J. L. Crassidis and J. L. Junkins, Optimal Estimation of Dynamic Systems, 2nd edition, CRC Press, 2012.
[13]	D. Dee, Simplification of the Kalman filter for meteorological data assimilation, Quarterly Journal of the Royal Meteorological Society, 117 (1991), 365-384.doi: 10.1002/qj.49711749806.
[14]	J. Dennis and J. Moré, Quasi-Newton methods, motivation and theory, SIAM Review, 19 (1977), 46-89.doi: 10.1137/1019005.
[15]	J. Dennis and R. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Review, 21 (1979), 443-459.doi: 10.1137/1021091.
[16]	J. Dennis and R. Schnabel, A new derivation of symmetric positive definite secant updates, in Nonlinear Programming (Madison, Wis., 1980), 4, Academic Press, New York-London, 1981, 167-199.
[17]	L. Evans, Partial Differential Equations, Graduate Studies in Mathematics, 19, American Mathematical Society, Providence, RI, 1998.
[18]	G. Evensen, Sequential data assimilation with a non-linear quasi-geostrophic model using monte carlo methods to forecast error statistics, Journal of Geophysical Research, 99 (1994), 143-162.
[19]	C. Fandry and L. Leslie, A two-layer quasi-geostrophic model of summer trough formation in the australian subtropical easterlies, Journal of the Atmospheric Sciences, 41 (1984), 807-818.
[20]	M. Fisher, Development of a Simplified Kalman Filter, ECMWF Technical Memorandum, 260, ECMWF, 1998.
[21]	M. Fisher, An Investigation of Model Error in a Quasi-Geostrophic, Weak-Constraint, 4D-Var Analysis System, Oral presentation, ECMWF, 2009.
[22]	M. Fisher and E. Adresson, Developments in 4D-var and Kalman Filtering, ECMWF Technical Memorandum, 347, ECMWF, 2001.
[23]	R. Kalman, A new approach to linear filtering and prediction problems, Transactions of the ASME - Journal of Basic Engineering, 82 (1960), 35-45.doi: 10.1115/1.3662552.
[24]	R. Leveque, Finite Difference Methods for Ordinary and Partial Differential Equations. Steady-State and Time-Dependent Problems, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2007.doi: 10.1137/1.9780898717839.
[25]	J. Nocedal and S. Wright, Limited-memory BFGS in Numerical Optimization, Springer-Verlag, New York, 1999, 224-227.
[26]	J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999.doi: 10.1007/b98874.
[27]	V. Pan and R. Schreiber, An improved newton iteration for the generalized inverse of a matrix, with applications, SIAM Journal on Scientific and Statistical Computing, 12 (1991), 1109-1130.doi: 10.1137/0912058.
[28]	J. Pedlosky, Geostrophic motion, in Geophysical Fluid Dynamics, Springer-Verlag, New York, 1987, 22-57.
[29]	K. Riley, M. Hobson and S. Bence, Partial differential equations: Separation of variables and other methods, in Mathematical Methods for Physics and Engineering, Cambridge University Press, Cambridge, 2004, 671-676.
[30]	D. Simon, The discrete-time Kalman filter, in Optimal State Estimation, Kalman, $H_\infty$, and Nonlinear Approaches, Wiley-Interscience, Hoboken, 2006, 123-145.
[31]	A. Staniforth and J. Côté, Semi-lagrangian integration schemes for atmospheric models review, Monthly Weather Review, 119 (1991), 2206-2223.doi: 10.1175/1520-0493(1991)119<2206:SLISFA>2.0.CO;2.
[32]	Y. Trémolet, Incremental 4d-var convergence study, Tellus, 59A (2007), 706-718.
[33]	Y. Tremolet and A. Hofstadler, OOPS as a common framework for Research and Operations, Presentation 14th Workshop on meteorological operational systems, ECMWF, 2013.
[34]	A. Voutilainen, T. Pyhälahti, K. Kallio, H. Haario and J. Kaipio, A filtering approach for estimating lake water quality from remote sensing data, International Journal of Applied Earth Observation and Geoinformation, 9 (2007), 50-64.doi: 10.1016/j.jag.2006.07.001.
[35]	D. Zupanski, A general weak constraint applicable to operational 4dvar data assimilation systems, Monthly Weather Review, 125 (1996), 2274-2292.doi: 10.1175/1520-0493(1997)125<2274:AGWCAT>2.0.CO;2.