• Previous Article
    Homogenization of the transmission eigenvalue problem for periodic media and application to the inverse problem
  • IPI Home
  • This Issue
  • Next Article
    Application of mixed formulations of quasi-reversibility to solve ill-posed problems for heat and wave equations: The 1D case
November  2015, 9(4): 1003-1024. doi: 10.3934/ipi.2015.9.1003

Stabilized BFGS approximate Kalman filter

1. 

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

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, Finland

Received  August 2014 Revised  May 2015 Published  October 2015

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.
Citation: Alexander Bibov, Heikki Haario, Antti Solonen. Stabilized BFGS approximate Kalman filter. Inverse Problems & Imaging, 2015, 9 (4) : 1003-1024. doi: 10.3934/ipi.2015.9.1003
References:
[1]

J. L. Anderson, An adaptive covariance inflation error correction algorithm for ensemble filters, Tellus-A, 59 (2006), 210-224. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

G. J. Bierman, Factorization Methods for Discrete Sequential Estimation, Vol. 128, Academic Press, 1977.  Google Scholar

[8]

R. Bucy and P. Joseph, Filtering for Stochastic Processes with Applications to Guidance, John Wiley & Sons, New York, 1968.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

J. L. Crassidis and J. L. Junkins, Optimal Estimation of Dynamic Systems, 2nd edition, CRC Press, 2012.  Google Scholar

[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.  Google Scholar

[14]

J. Dennis and J. Moré, Quasi-Newton methods, motivation and theory, SIAM Review, 19 (1977), 46-89. doi: 10.1137/1019005.  Google Scholar

[15]

J. Dennis and R. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Review, 21 (1979), 443-459. doi: 10.1137/1021091.  Google Scholar

[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.  Google Scholar

[17]

L. Evans, Partial Differential Equations, Graduate Studies in Mathematics, 19, American Mathematical Society, Providence, RI, 1998.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

M. Fisher, Development of a Simplified Kalman Filter, ECMWF Technical Memorandum, 260, ECMWF, 1998. Google Scholar

[21]

M. Fisher, An Investigation of Model Error in a Quasi-Geostrophic, Weak-Constraint, 4D-Var Analysis System, Oral presentation, ECMWF, 2009. Google Scholar

[22]

M. Fisher and E. Adresson, Developments in 4D-var and Kalman Filtering, ECMWF Technical Memorandum, 347, ECMWF, 2001. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

J. Nocedal and S. Wright, Limited-memory BFGS in Numerical Optimization, Springer-Verlag, New York, 1999, 224-227. Google Scholar

[26]

J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874.  Google Scholar

[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.  Google Scholar

[28]

J. Pedlosky, Geostrophic motion, in Geophysical Fluid Dynamics, Springer-Verlag, New York, 1987, 22-57. Google Scholar

[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. Google Scholar

[30]

D. Simon, The discrete-time Kalman filter, in Optimal State Estimation, Kalman, $H_\infty$, and Nonlinear Approaches, Wiley-Interscience, Hoboken, 2006, 123-145. Google Scholar

[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.  Google Scholar

[32]

Y. Trémolet, Incremental 4d-var convergence study, Tellus, 59A (2007), 706-718. Google Scholar

[33]

Y. Tremolet and A. Hofstadler, OOPS as a common framework for Research and Operations, Presentation 14th Workshop on meteorological operational systems, ECMWF, 2013. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

J. L. Anderson, An adaptive covariance inflation error correction algorithm for ensemble filters, Tellus-A, 59 (2006), 210-224. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

G. J. Bierman, Factorization Methods for Discrete Sequential Estimation, Vol. 128, Academic Press, 1977.  Google Scholar

[8]

R. Bucy and P. Joseph, Filtering for Stochastic Processes with Applications to Guidance, John Wiley & Sons, New York, 1968.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[12]

J. L. Crassidis and J. L. Junkins, Optimal Estimation of Dynamic Systems, 2nd edition, CRC Press, 2012.  Google Scholar

[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.  Google Scholar

[14]

J. Dennis and J. Moré, Quasi-Newton methods, motivation and theory, SIAM Review, 19 (1977), 46-89. doi: 10.1137/1019005.  Google Scholar

[15]

J. Dennis and R. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Review, 21 (1979), 443-459. doi: 10.1137/1021091.  Google Scholar

[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.  Google Scholar

[17]

L. Evans, Partial Differential Equations, Graduate Studies in Mathematics, 19, American Mathematical Society, Providence, RI, 1998.  Google Scholar

[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. Google Scholar

[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. Google Scholar

[20]

M. Fisher, Development of a Simplified Kalman Filter, ECMWF Technical Memorandum, 260, ECMWF, 1998. Google Scholar

[21]

M. Fisher, An Investigation of Model Error in a Quasi-Geostrophic, Weak-Constraint, 4D-Var Analysis System, Oral presentation, ECMWF, 2009. Google Scholar

[22]

M. Fisher and E. Adresson, Developments in 4D-var and Kalman Filtering, ECMWF Technical Memorandum, 347, ECMWF, 2001. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[25]

J. Nocedal and S. Wright, Limited-memory BFGS in Numerical Optimization, Springer-Verlag, New York, 1999, 224-227. Google Scholar

[26]

J. Nocedal and S. Wright, Numerical Optimization, Springer-Verlag, New York, 1999. doi: 10.1007/b98874.  Google Scholar

[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.  Google Scholar

[28]

J. Pedlosky, Geostrophic motion, in Geophysical Fluid Dynamics, Springer-Verlag, New York, 1987, 22-57. Google Scholar

[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. Google Scholar

[30]

D. Simon, The discrete-time Kalman filter, in Optimal State Estimation, Kalman, $H_\infty$, and Nonlinear Approaches, Wiley-Interscience, Hoboken, 2006, 123-145. Google Scholar

[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.  Google Scholar

[32]

Y. Trémolet, Incremental 4d-var convergence study, Tellus, 59A (2007), 706-718. Google Scholar

[33]

Y. Tremolet and A. Hofstadler, OOPS as a common framework for Research and Operations, Presentation 14th Workshop on meteorological operational systems, ECMWF, 2013. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Russell Johnson, Carmen Núñez. The Kalman-Bucy filter revisited. Discrete & Continuous Dynamical Systems, 2014, 34 (10) : 4139-4153. doi: 10.3934/dcds.2014.34.4139

[2]

Andreas Bock, Colin J. Cotter. Learning landmark geodesics using the ensemble Kalman filter. Foundations of Data Science, 2021  doi: 10.3934/fods.2021020

[3]

Junyoung Jang, Kihoon Jang, Hee-Dae Kwon, Jeehyun Lee. Feedback control of an HBV model based on ensemble kalman filter and differential evolution. Mathematical Biosciences & Engineering, 2018, 15 (3) : 667-691. doi: 10.3934/mbe.2018030

[4]

Mojtaba F. Fathi, Ahmadreza Baghaie, Ali Bakhshinejad, Raphael H. Sacho, Roshan M. D'Souza. Time-resolved denoising using model order reduction, dynamic mode decomposition, and kalman filter and smoother. Journal of Computational Dynamics, 2020, 7 (2) : 469-487. doi: 10.3934/jcd.2020019

[5]

Wawan Hafid Syaifudin, Endah R. M. Putri. The application of model predictive control on stock portfolio optimization with prediction based on Geometric Brownian Motion-Kalman Filter. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021119

[6]

Neil K. Chada, Claudia Schillings, Simon Weissmann. On the incorporation of box-constraints for ensemble Kalman inversion. Foundations of Data Science, 2019, 1 (4) : 433-456. doi: 10.3934/fods.2019018

[7]

Jiangqi Wu, Linjie Wen, Jinglai Li. Resampled ensemble Kalman inversion for Bayesian parameter estimation with sequential data. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021045

[8]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2021, 3 (3) : 371-411. doi: 10.3934/fods.2020018

[9]

Anugu Sumith Reddy, Amit Apte. Stability of non-linear filter for deterministic dynamics. Foundations of Data Science, 2021, 3 (3) : 647-675. doi: 10.3934/fods.2021025

[10]

Marc Bocquet, Alban Farchi, Quentin Malartic. Online learning of both state and dynamics using ensemble Kalman filters. Foundations of Data Science, 2021, 3 (3) : 305-330. doi: 10.3934/fods.2020015

[11]

K. F. C. Yiu, K. Y. Chan, S. Y. Low, S. Nordholm. A multi-filter system for speech enhancement under low signal-to-noise ratios. Journal of Industrial & Management Optimization, 2009, 5 (3) : 671-682. doi: 10.3934/jimo.2009.5.671

[12]

Gerasimos G. Rigatos, Efthymia G. Rigatou, Jean Daniel Djida. Change detection in the dynamics of an intracellular protein synthesis model using nonlinear Kalman filtering. Mathematical Biosciences & Engineering, 2015, 12 (5) : 1017-1035. doi: 10.3934/mbe.2015.12.1017

[13]

Sebastian Reich, Seoleun Shin. On the consistency of ensemble transform filter formulations. Journal of Computational Dynamics, 2014, 1 (1) : 177-189. doi: 10.3934/jcd.2014.1.177

[14]

Jin-Won Kim, Amirhossein Taghvaei, Yongxin Chen, Prashant G. Mehta. Feedback particle filter for collective inference. Foundations of Data Science, 2021, 3 (3) : 543-561. doi: 10.3934/fods.2021018

[15]

Z. G. Feng, Kok Lay Teo, N. U. Ahmed, Yulin Zhao, W. Y. Yan. Optimal fusion of sensor data for Kalman filtering. Discrete & Continuous Dynamical Systems, 2006, 14 (3) : 483-503. doi: 10.3934/dcds.2006.14.483

[16]

Ye Sun, Daniel B. Work. Error bounds for Kalman filters on traffic networks. Networks & Heterogeneous Media, 2018, 13 (2) : 261-295. doi: 10.3934/nhm.2018012

[17]

Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial & Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038

[18]

Qiyu Jin, Ion Grama, Quansheng Liu. Convergence theorems for the Non-Local Means filter. Inverse Problems & Imaging, 2018, 12 (4) : 853-881. doi: 10.3934/ipi.2018036

[19]

Hai Huyen Dam, Kok Lay Teo. Variable fractional delay filter design with discrete coefficients. Journal of Industrial & Management Optimization, 2016, 12 (3) : 819-831. doi: 10.3934/jimo.2016.12.819

[20]

Xiaoying Han, Jinglai Li, Dongbin Xiu. Error analysis for numerical formulation of particle filter. Discrete & Continuous Dynamical Systems - B, 2015, 20 (5) : 1337-1354. doi: 10.3934/dcdsb.2015.20.1337

2020 Impact Factor: 1.639

Metrics

  • PDF downloads (160)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]