# American Institute of Mathematical Sciences

• 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] 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 [8] 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 [9] 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 [10] 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 [11] 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 [12] 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 [13] 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 [14] 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 [15] 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 [16] 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 [17] 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 [18] 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 [19] Josep M. Olm, Xavier Ros-Oton. Approximate tracking of periodic references in a class of bilinear systems via stable inversion. Discrete & Continuous Dynamical Systems - B, 2011, 15 (1) : 197-215. doi: 10.3934/dcdsb.2011.15.197 [20] Duarte Jorge, JanuÁrio Cristina, Martins Nuno. A chaotic bursting-spiking transition in a pancreatic beta-cells system: Observation of an interior glucose-induced crisis. Mathematical Biosciences & Engineering, 2017, 14 (4) : 821-842. doi: 10.3934/mbe.2017045

2016 Impact Factor: 1.094

## Metrics

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

[Back to Top]