• Previous Article
    Application of mixed formulations of quasi-reversibility to solve ill-posed problems for heat and wave equations: The 1D case
  • IPI Home
  • This Issue
  • Next Article
    Homogenization of the transmission eigenvalue problem for periodic media and application to the inverse problem
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.

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

[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. 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. 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. 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. 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, (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. 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. 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. doi: 10.1006/jcph.1998.6077.

[12]

J. L. Crassidis and J. L. Junkins, Optimal Estimation of Dynamic Systems,, 2nd edition, (2012).

[13]

D. Dee, Simplification of the Kalman filter for meteorological data assimilation,, Quarterly Journal of the Royal Meteorological Society, 117 (1991), 365. doi: 10.1002/qj.49711749806.

[14]

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

[15]

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

[16]

J. Dennis and R. Schnabel, A new derivation of symmetric positive definite secant updates,, in Nonlinear Programming (Madison, (1980), 167.

[17]

L. Evans, Partial Differential Equations,, Graduate Studies in Mathematics, (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.

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

[20]

M. Fisher, Development of a Simplified Kalman Filter,, ECMWF Technical Memorandum, (1998).

[21]

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

[22]

M. Fisher and E. Adresson, Developments in 4D-var and Kalman Filtering,, ECMWF Technical Memorandum, (2001).

[23]

R. Kalman, A new approach to linear filtering and prediction problems,, Transactions of the ASME - Journal of Basic Engineering, 82 (1960), 35. 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), (2007). doi: 10.1137/1.9780898717839.

[25]

J. Nocedal and S. Wright, Limited-memory BFGS, in Numerical Optimization, (1999), 224.

[26]

J. Nocedal and S. Wright, Numerical Optimization,, Springer-Verlag, (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. doi: 10.1137/0912058.

[28]

J. Pedlosky, Geostrophic motion,, in Geophysical Fluid Dynamics, (1987), 22.

[29]

K. Riley, M. Hobson and S. Bence, Partial differential equations: Separation of variables and other methods,, in Mathematical Methods for Physics and Engineering, (2004), 671.

[30]

D. Simon, The discrete-time Kalman filter,, in Optimal State Estimation, (2006), 123.

[31]

A. Staniforth and J. Côté, Semi-lagrangian integration schemes for atmospheric models review,, Monthly Weather Review, 119 (1991), 2206. 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.

[33]

Y. Tremolet and A. Hofstadler, OOPS as a common framework for Research and Operations,, Presentation 14th Workshop on meteorological operational systems, (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. 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. doi: 10.1175/1520-0493(1997)125<2274:AGWCAT>2.0.CO;2.

show all references

References:
[1]

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

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

[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. 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. 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. 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. 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, (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. 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. 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. doi: 10.1006/jcph.1998.6077.

[12]

J. L. Crassidis and J. L. Junkins, Optimal Estimation of Dynamic Systems,, 2nd edition, (2012).

[13]

D. Dee, Simplification of the Kalman filter for meteorological data assimilation,, Quarterly Journal of the Royal Meteorological Society, 117 (1991), 365. doi: 10.1002/qj.49711749806.

[14]

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

[15]

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

[16]

J. Dennis and R. Schnabel, A new derivation of symmetric positive definite secant updates,, in Nonlinear Programming (Madison, (1980), 167.

[17]

L. Evans, Partial Differential Equations,, Graduate Studies in Mathematics, (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.

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

[20]

M. Fisher, Development of a Simplified Kalman Filter,, ECMWF Technical Memorandum, (1998).

[21]

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

[22]

M. Fisher and E. Adresson, Developments in 4D-var and Kalman Filtering,, ECMWF Technical Memorandum, (2001).

[23]

R. Kalman, A new approach to linear filtering and prediction problems,, Transactions of the ASME - Journal of Basic Engineering, 82 (1960), 35. 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), (2007). doi: 10.1137/1.9780898717839.

[25]

J. Nocedal and S. Wright, Limited-memory BFGS, in Numerical Optimization, (1999), 224.

[26]

J. Nocedal and S. Wright, Numerical Optimization,, Springer-Verlag, (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. doi: 10.1137/0912058.

[28]

J. Pedlosky, Geostrophic motion,, in Geophysical Fluid Dynamics, (1987), 22.

[29]

K. Riley, M. Hobson and S. Bence, Partial differential equations: Separation of variables and other methods,, in Mathematical Methods for Physics and Engineering, (2004), 671.

[30]

D. Simon, The discrete-time Kalman filter,, in Optimal State Estimation, (2006), 123.

[31]

A. Staniforth and J. Côté, Semi-lagrangian integration schemes for atmospheric models review,, Monthly Weather Review, 119 (1991), 2206. 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.

[33]

Y. Tremolet and A. Hofstadler, OOPS as a common framework for Research and Operations,, Presentation 14th Workshop on meteorological operational systems, (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. 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. doi: 10.1175/1520-0493(1997)125<2274:AGWCAT>2.0.CO;2.

[1]

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

[2]

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

[3]

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

[4]

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

[5]

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

[6]

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 - A, 2006, 14 (3) : 483-503. doi: 10.3934/dcds.2006.14.483

[7]

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

[8]

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

[9]

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

[10]

Michael Basin, Mark A. Pinsky. Control of Kalman-like filters using impulse and continuous feedback design. Discrete & Continuous Dynamical Systems - B, 2002, 2 (2) : 169-184. doi: 10.3934/dcdsb.2002.2.169

[11]

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

[12]

Valerii Maltsev, Michael Pokojovy. On a parabolic-hyperbolic filter for multicolor image noise reduction. Evolution Equations & Control Theory, 2016, 5 (2) : 251-272. doi: 10.3934/eect.2016004

[13]

Kody Law, Abhishek Shukla, Andrew Stuart. Analysis of the 3DVAR filter for the partially observed Lorenz'63 model. Discrete & Continuous Dynamical Systems - A, 2014, 34 (3) : 1061-1078. doi: 10.3934/dcds.2014.34.1061

[14]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193

[15]

Abdel-Rahman Hedar, Alaa Fahim. Filter-based genetic algorithm for mixed variable programming. Numerical Algebra, Control & Optimization, 2011, 1 (1) : 99-116. doi: 10.3934/naco.2011.1.99

[16]

Andrea Arnold, Daniela Calvetti, Erkki Somersalo. Vectorized and parallel particle filter SMC parameter estimation for stiff ODEs. Conference Publications, 2015, 2015 (special) : 75-84. doi: 10.3934/proc.2015.0075

[17]

Jianling Li, Chunting Lu, Youfang Zeng. A smooth QP-free algorithm without a penalty function or a filter for mathematical programs with complementarity constraints. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 115-126. doi: 10.3934/naco.2015.5.115

[18]

Laura Martín-Fernández, Gianni Gilioli, Ettore Lanzarone, Joaquín Míguez, Sara Pasquali, Fabrizio Ruggeri, Diego P. Ruiz. A Rao-Blackwellized particle filter for joint parameter estimation and biomass tracking in a stochastic predator-prey system. Mathematical Biosciences & Engineering, 2014, 11 (3) : 573-597. doi: 10.3934/mbe.2014.11.573

[19]

Chunlin Hao, Xinwei Liu. A trust-region filter-SQP method for mathematical programs with linear complementarity constraints. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1041-1055. doi: 10.3934/jimo.2011.7.1041

[20]

Qifeng Cheng, Xue Han, Tingting Zhao, V S Sarma Yadavalli. Improved particle swarm optimization and neighborhood field optimization by introducing the re-sampling step of particle filter. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-22. doi: 10.3934/jimo.2018038

2016 Impact Factor: 1.094

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]