Extended Kalman filter

Last updated

In estimation theory, the extended Kalman filter (EKF) is the nonlinear version of the Kalman filter which linearizes about an estimate of the current mean and covariance. In the case of well defined transition models, the EKF has been considered [1] the de facto standard in the theory of nonlinear state estimation, navigation systems and GPS. [2]

Contents

History

The papers establishing the mathematical foundations of Kalman type filters were published between 1959 and 1961. [3] [4] [5] The Kalman filter is the optimal linear estimator for linear system models with additive independent white noise in both the transition and the measurement systems. Unfortunately, in engineering, most systems are nonlinear, so attempts were made to apply this filtering method to nonlinear systems; most of this work was done at NASA Ames. [6] [7] The EKF adapted techniques from calculus, namely multivariate Taylor series expansions, to linearize a model about a working point. If the system model (as described below) is not well known or is inaccurate, then Monte Carlo methods, especially particle filters, are employed for estimation. Monte Carlo techniques predate the existence of the EKF but are more computationally expensive for any moderately dimensioned state-space.

Formulation

In the extended Kalman filter, the state transition and observation models don't need to be linear functions of the state but may instead be differentiable functions.

Here wk and vk are the process and observation noises which are both assumed to be zero mean multivariate Gaussian noises with covariance Qk and Rk respectively. uk is the control vector.

The function f can be used to compute the predicted state from the previous estimate and similarly the function h can be used to compute the predicted measurement from the predicted state. However, f and h cannot be applied to the covariance directly. Instead a matrix of partial derivatives (the Jacobian) is computed.

At each time step, the Jacobian is evaluated with current predicted states. These matrices can be used in the Kalman filter equations. This process essentially linearizes the non-linear function around the current estimate.

See the Kalman Filter article for notational remarks.

Discrete-time predict and update equations

Notation represents the estimate of at time n given observations up to and including at time mn.

Predict

Predicted state estimate
Predicted covariance estimate

Update

Innovation or measurement residual
Innovation (or residual) covariance
Near-optimal Kalman gain
Updated state estimate
Updated covariance estimate

where the state transition and observation matrices are defined to be the following Jacobians

Disadvantages and alternatives

Unlike its linear counterpart, the extended Kalman filter in general is not an optimal estimator (it is optimal if the measurement and the state transition model are both linear, as in that case the extended Kalman filter is identical to the regular one). In addition, if the initial estimate of the state is wrong, or if the process is modeled incorrectly, the filter may quickly diverge, owing to its linearization. Another problem with the extended Kalman filter is that the estimated covariance matrix tends to underestimate the true covariance matrix and therefore risks becoming inconsistent in the statistical sense without the addition of "stabilising noise" [8] .

More generally one should consider the infinite dimensional nature of the nonlinear filtering problem and the inadequacy of a simple mean and variance-covariance estimator to fully represent the optimal filter. It should also be noted that the extended Kalman filter may give poor performances even for very simple one-dimensional systems such as the cubic sensor, [9] where the optimal filter can be bimodal [10] and as such cannot be effectively represented by a single mean and variance estimator, having a rich structure, or similarly for the quadratic sensor. [11] In such cases the projection filters have been studied as an alternative, having been applied also to navigation. [12] Other general nonlinear filtering methods like full particle filters may be considered in this case.

Having stated this, the extended Kalman filter can give reasonable performance, and is arguably the de facto standard in navigation systems and GPS.

Generalizations

Continuous-time extended Kalman filter

Model

Initialize

Predict-Update

Unlike the discrete-time extended Kalman filter, the prediction and update steps are coupled in the continuous-time extended Kalman filter. [13]

Discrete-time measurements

Most physical systems are represented as continuous-time models while discrete-time measurements are frequently taken for state estimation via a digital processor. Therefore, the system model and measurement model are given by

where .

Initialize

Predict

where

Update

where

The update equations are identical to those of discrete-time extended Kalman filter.

Higher-order extended Kalman filters

The above recursion is a first-order extended Kalman filter (EKF). Higher order EKFs may be obtained by retaining more terms of the Taylor series expansions. For example, second and third order EKFs have been described. [14] However, higher order EKFs tend to only provide performance benefits when the measurement noise is small.

Non-additive noise formulation and equations

The typical formulation of the EKF involves the assumption of additive process and measurement noise. This assumption, however, is not necessary for EKF implementation. [15] Instead, consider a more general system of the form:

Here wk and vk are the process and observation noises which are both assumed to be zero mean multivariate Gaussian noises with covariance Qk and Rk respectively. Then the covariance prediction and innovation equations become

where the matrices and are Jacobian matrices:

The predicted state estimate and measurement residual are evaluated at the mean of the process and measurement noise terms, which is assumed to be zero. Otherwise, the non-additive noise formulation is implemented in the same manner as the additive noise EKF.

Implicit extended Kalman filter

In certain cases, the observation model of a nonlinear system cannot be solved for , but can be expressed by the implicit function:

where are the noisy observations.

The conventional extended Kalman filter can be applied with the following substitutions: [16] [17]

where:

Here the original observation covariance matrix is transformed, and the innovation is defined differently. The Jacobian matrix is defined as before, but determined from the implicit observation model .

Modifications

Iterated extended Kalman filter

The iterated extended Kalman filter improves the linearization of the extended Kalman filter by recursively modifying the centre point of the Taylor expansion. This reduces the linearization error at the cost of increased computational requirements. [17]

Robust extended Kalman filter

The robust extended Kalman filter arises by linearizing the signal model about the current state estimate and using the linear Kalman filter to predict the next estimate. This attempts to produce a locally optimal filter, however, it is not necessarily stable because the solutions of the underlying Riccati equation are not guaranteed to be positive definite. One way of improving performance is the faux algebraic Riccati technique [18] which trades off optimality for stability. The familiar structure of the extended Kalman filter is retained but stability is achieved by selecting a positive definite solution to a faux algebraic Riccati equation for the gain design.

Another way of improving extended Kalman filter performance is to employ the H-infinity results from robust control. Robust filters are obtained by adding a positive definite term to the design Riccati equation. [19] The additional term is parametrized by a scalar which the designer may tweak to achieve a trade-off between mean-square-error and peak error performance criteria.

Invariant extended Kalman filter

The invariant extended Kalman filter (IEKF) is a modified version of the EKF for nonlinear systems possessing symmetries (or invariances). It combines the advantages of both the EKF and the recently introduced symmetry-preserving filters. Instead of using a linear correction term based on a linear output error, the IEKF uses a geometrically adapted correction term based on an invariant output error; in the same way the gain matrix is not updated from a linear state error, but from an invariant state error. The main benefit is that the gain and covariance equations converge to constant values on a much bigger set of trajectories than equilibrium points as it is the case for the EKF, which results in a better convergence of the estimation.

Unscented Kalman filters

A nonlinear Kalman filter which shows promise as an improvement over the EKF is the unscented Kalman filter (UKF). In the UKF, the probability density is approximated by a deterministic sampling of points which represent the underlying distribution as a Gaussian. The nonlinear transformation of these points are intended to be an estimation of the posterior distribution, the moments of which can then be derived from the transformed samples. The transformation is known as the unscented transform. The UKF tends to be more robust and more accurate than the EKF in its estimation of error in all the directions.

"The extended Kalman filter (EKF) is probably the most widely used estimation algorithm for nonlinear systems. However, more than 35 years of experience in the estimation community has shown that is difficult to implement, difficult to tune, and only reliable for systems that are almost linear on the time scale of the updates. Many of these difficulties arise from its use of linearization." [1]

A 2012 paper includes simulation results which suggest that some published variants of the UKF fail to be as accurate as the Second Order Extended Kalman Filter (SOEKF), also known as the augmented Kalman filter. [20] The SOEKF predates the UKF by approximately 35 years with the moment dynamics first described by Bass et al. [21] The difficulty in implementing any Kalman-type filters for nonlinear state transitions stems from the numerical stability issues required for precision, [22] however the UKF does not escape this difficulty in that it uses linearization as well, namely linear regression. The stability issues for the UKF generally stem from the numerical approximation to the square root of the covariance matrix, whereas the stability issues for both the EKF and the SOEKF stem from possible issues in the Taylor Series approximation along the trajectory.

Ensemble Kalman Filter

The UKF was in fact predated by the Ensemble Kalman filter, invented by Evensen in 1994. It has the advantage over the UKF that the number of ensemble members used can be much smaller than the state dimension, allowing for applications in very high-dimensional systems, such as weather prediction, with state-space sizes of a billion or more.

Fuzzy Kalman Filter

Fuzzy Kalman filter with a new method to represent possibility distributions was recently proposed to replace probability distributions by possibility distributions in order to obtain a genuine possibilistic filter, enabling the use of non-symmetric process and observation noises as well as higher inaccuracies in both process and observation models. [23]

See also

Related Research Articles

Bra–ket notation, also called Dirac notation, is a notation for linear algebra and linear operators on complex vector spaces together with their dual space both in the finite-dimensional and infinite-dimensional case. It is specifically designed to ease the types of calculations that frequently come up in quantum mechanics. Its use in quantum mechanics is quite widespread.

<span class="mw-page-title-main">Curvature</span> Mathematical measure of how much a curve or surface deviates from flatness

In mathematics, curvature is any of several strongly related concepts in geometry that intuitively measure the amount by which a curve deviates from being a straight line or by which a surface deviates from being a plane. If a curve or surface is contained in a larger space, curvature can be defined extrinsically relative to the ambient space. Curvature of Riemannian manifolds of dimension at least two can be defined intrinsically without reference to a larger space.

In statistics, maximum likelihood estimation (MLE) is a method of estimating the parameters of an assumed probability distribution, given some observed data. This is achieved by maximizing a likelihood function so that, under the assumed statistical model, the observed data is most probable. The point in the parameter space that maximizes the likelihood function is called the maximum likelihood estimate. The logic of maximum likelihood is both intuitive and flexible, and as such the method has become a dominant means of statistical inference.

<span class="mw-page-title-main">Kalman filter</span> Algorithm that estimates unknowns from a series of measurements over time

In statistics and control theory, Kalman filtering is an algorithm that uses a series of measurements observed over time, including statistical noise and other inaccuracies, to produce estimates of unknown variables that tend to be more accurate than those based on a single measurement, by estimating a joint probability distribution over the variables for each time-step. The filter is constructed as a mean squared error minimiser, but an alternative derivation of the filter is also provided showing how the filter relates to maximum likelihood statistics. The filter is named after Rudolf E. Kálmán.

<span class="mw-page-title-main">Covariance matrix</span> Measure of covariance of components of a random vector

In probability theory and statistics, a covariance matrix is a square matrix giving the covariance between each pair of elements of a given random vector.

<span class="mw-page-title-main">Expectation–maximization algorithm</span> Iterative method for finding maximum likelihood estimates in statistical models

In statistics, an expectation–maximization (EM) algorithm is an iterative method to find (local) maximum likelihood or maximum a posteriori (MAP) estimates of parameters in statistical models, where the model depends on unobserved latent variables. The EM iteration alternates between performing an expectation (E) step, which creates a function for the expectation of the log-likelihood evaluated using the current estimate for the parameters, and a maximization (M) step, which computes parameters maximizing the expected log-likelihood found on the E step. These parameter-estimates are then used to determine the distribution of the latent variables in the next E step. It can be used, for example, to estimate a mixture of gaussians, or to solve the multiple linear regression problem.

In statistics, propagation of uncertainty is the effect of variables' uncertainties on the uncertainty of a function based on them. When the variables are the values of experimental measurements they have uncertainties due to measurement limitations which propagate due to the combination of variables in the function.

In mathematics and computing, the Levenberg–Marquardt algorithm, also known as the damped least-squares (DLS) method, is used to solve non-linear least squares problems. These minimization problems arise especially in least squares curve fitting. The LMA interpolates between the Gauss–Newton algorithm (GNA) and the method of gradient descent. The LMA is more robust than the GNA, which means that in many cases it finds a solution even if it starts very far off the final minimum. For well-behaved functions and reasonable starting parameters, the LMA tends to be slower than the GNA. LMA can also be viewed as Gauss–Newton using a trust region approach.

<span class="mw-page-title-main">Nonlinear regression</span> Regression analysis

In statistics, nonlinear regression is a form of regression analysis in which observational data are modeled by a function which is a nonlinear combination of the model parameters and depends on one or more independent variables. The data are fitted by a method of successive approximations (iterations).

Estimation theory is a branch of statistics that deals with estimating the values of parameters based on measured empirical data that has a random component. The parameters describe an underlying physical setting in such a way that their value affects the distribution of the measured data. An estimator attempts to approximate the unknown parameters using the measurements. In estimation theory, two approaches are generally considered:

In statistics, generalized least squares (GLS) is a method used to estimate the unknown parameters in a linear regression model. It is used when there is a non-zero amount of correlation between the residuals in the regression model. GLS is employed to improve statistical efficiency and reduce the risk of drawing erroneous inferences, as compared to conventional least squares and weighted least squares methods. It was first described by Alexander Aitken in 1935.

In directional statistics, the von Mises–Fisher distribution, is a probability distribution on the -sphere in . If the distribution reduces to the von Mises distribution on the circle.

The ensemble Kalman filter (EnKF) is a recursive filter suitable for problems with a large number of variables, such as discretizations of partial differential equations in geophysical models. The EnKF originated as a version of the Kalman filter for large problems, and it is now an important data assimilation component of ensemble forecasting. EnKF is related to the particle filter but the EnKF makes the assumption that all probability distributions involved are Gaussian; when it is applicable, it is much more efficient than the particle filter.

In the theory of stochastic processes, filtering describes the problem of determining the state of a system from an incomplete and potentially noisy set of observations. While originally motivated by problems in engineering, filtering found applications in many fields from signal processing to finance.

GPS/INS is the use of GPS satellite signals to correct or calibrate a solution from an inertial navigation system (INS). The method is applicable for any GNSS/INS system.

Linear least squares (LLS) is the least squares approximation of linear functions to data. It is a set of formulations for solving statistical problems involved in linear regression, including variants for ordinary (unweighted), weighted, and generalized (correlated) residuals. Numerical methods for linear least squares include inverting the matrix of the normal equations and orthogonal decomposition methods.

In mathematics, Symmetry-preserving observers, also known as invariant filters, are estimation techniques whose structure and design take advantage of the natural symmetries of the considered nonlinear model. As such, the main benefit is an expected much larger domain of convergence than standard filtering methods, e.g. Extended Kalman Filter (EKF) or Unscented Kalman Filter (UKF).

The invariant extended Kalman filter (IEKF) (not to be confused with the iterated extended Kalman filter) was first introduced as a version of the extended Kalman filter (EKF) for nonlinear systems possessing symmetries (or invariances), then generalized and recast as an adaptation to Lie groups of the linear Kalman filtering theory. Instead of using a linear correction term based on a linear output error, the IEKF uses a geometrically adapted correction term based on an invariant output error; in the same way the gain matrix is not updated from a linear state error, but from an invariant state error. The main benefit is that the gain and covariance equations have reduced dependence on the estimated value of the state. In some cases they converge to constant values on a much bigger set of trajectories than is the case for the EKF, which results in a better convergence of the estimation.

The unscented transform (UT) is a mathematical function used to estimate the result of applying a given nonlinear transformation to a probability distribution that is characterized only in terms of a finite set of statistics. The most common use of the unscented transform is in the nonlinear projection of mean and covariance estimates in the context of nonlinear extensions of the Kalman filter. Its creator Jeffrey Uhlmann explained that "unscented" was an arbitrary name that he adopted to avoid it being referred to as the “Uhlmann filter.”

SAMV is a parameter-free superresolution algorithm for the linear inverse problem in spectral estimation, direction-of-arrival (DOA) estimation and tomographic reconstruction with applications in signal processing, medical imaging and remote sensing. The name was coined in 2013 to emphasize its basis on the asymptotically minimum variance (AMV) criterion. It is a powerful tool for the recovery of both the amplitude and frequency characteristics of multiple highly correlated sources in challenging environments. Applications include synthetic-aperture radar, computed tomography scan, and magnetic resonance imaging (MRI).

References

  1. 1 2 Julier, S.J.; Uhlmann, J.K. (2004). "Unscented filtering and nonlinear estimation" (PDF). Proceedings of the IEEE. 92 (3): 401–422. doi:10.1109/jproc.2003.823141. S2CID   9614092.
  2. Courses, E.; Surveys, T. (2006). "Sigma-Point Filters: An Overview with Applications to Integrated Navigation and Vision Assisted Control". 2006 IEEE Nonlinear Statistical Signal Processing Workshop. pp. 201–202. doi:10.1109/NSSPW.2006.4378854. ISBN   978-1-4244-0579-4. S2CID   18535558.
  3. R.E. Kalman (1960). "Contributions to the theory of optimal control". Bol. Soc. Mat. Mexicana: 102–119. CiteSeerX   10.1.1.26.4070 .
  4. R.E. Kalman (1960). "A New Approach to Linear Filtering and Prediction Problems" (PDF). Journal of Basic Engineering. 82: 35–45. doi:10.1115/1.3662552. S2CID   1242324.
  5. R.E. Kalman; R.S. Bucy (1961). "New results in linear filtering and prediction theory" (PDF). Journal of Basic Engineering. 83: 95–108. doi:10.1115/1.3658902. S2CID   8141345.
  6. Bruce A. McElhoe (1966). "An Assessment of the Navigation and Course Corrections for a Manned Flyby of Mars or Venus". IEEE Transactions on Aerospace and Electronic Systems. 2 (4): 613–623. Bibcode:1966ITAES...2..613M. doi:10.1109/TAES.1966.4501892. S2CID   51649221.
  7. G.L. Smith; S.F. Schmidt and L.A. McGee (1962). "Application of statistical filter theory to the optimal estimation of position and velocity on board a circumlunar vehicle". National Aeronautics and Space Administration.
  8. Huang, Guoquan P; Mourikis, Anastasios I; Roumeliotis, Stergios I (2008). "Analysis and improvement of the consistency of extended Kalman filter based SLAM". Robotics and Automation, 2008. ICRA 2008. IEEE International Conference on. pp. 473–479. doi:10.1109/ROBOT.2008.4543252.
  9. M. Hazewinkel, S.I. Marcus, H.J. Sussmann (1983). Nonexistence of finite-dimensional filters for conditional statistics of the cubic sensor problem. Systems & Control Letters 3(6), Pages 331-340, https://doi.org/10.1016/0167-6911(83)90074-9.
  10. Brigo, Damiano; Hanzon, Bernard; LeGland, Francois (1998). "A differential geometric approach to nonlinear filtering: the projection filter" (PDF). IEEE Transactions on Automatic Control. 43 (2): 247–252. doi:10.1109/9.661075.
  11. Armstrong, John; Brigo, Damiano (2016). "Nonlinear filtering via stochastic PDE projection on mixture manifolds in L2 direct metric". Mathematics of Control, Signals and Systems. 28 (1): 1–33. Bibcode:2016MCSS...28....5A. doi:10.1007/s00498-015-0154-1. hdl: 10044/1/30130 . S2CID   42796459.
  12. Azimi-Sadjadi, Babak; Krishnaprasad, P.S. (2005). "Approximate nonlinear filtering and its application in navigation". Automatica. 41 (6): 945–956. doi:10.1016/j.automatica.2004.12.013.
  13. Brown, Robert Grover; Hwang, Patrick Y.C. (1997). Introduction to Random Signals and Applied Kalman Filtering (3 ed.). New York: John Wiley & Sons. pp.  289–293. ISBN   978-0-471-12839-7.
  14. Einicke, G.A. (2019). Smoothing, Filtering and Prediction: Estimating the Past, Present and Future (2nd ed.). Amazon Prime Publishing. ISBN   978-0-6485115-0-2.
  15. Simon, Dan (2006). Optimal State Estimation. Hoboken, NJ: John Wiley & Sons. ISBN   978-0-471-70858-2.
  16. Quan, Quan (2017). Introduction to multicopter design and control. Singapore: Springer. ISBN   978-981-10-3382-7.
  17. 1 2 Zhang, Zhengyou (1997). "Parameter estimation techniques: a tutorial with application to conic fitting" (PDF). Image and Vision Computing. 15 (1): 59–76. doi:10.1016/s0262-8856(96)01112-2. ISSN   0262-8856.
  18. Einicke, G.A.; White, L.B.; Bitmead, R.R. (September 2003). "The Use of Fake Algebraic Riccati Equations for Co-channel Demodulation". IEEE Trans. Signal Process. 51 (9): 2288–2293. Bibcode:2003ITSP...51.2288E. doi:10.1109/tsp.2003.815376. hdl: 2440/2403 .
  19. Einicke, G.A.; White, L.B. (September 1999). "Robust Extended Kalman Filtering". IEEE Trans. Signal Process. 47 (9): 2596–2599. Bibcode:1999ITSP...47.2596E. doi:10.1109/78.782219.
  20. Gustafsson, F.; Hendeby, G.; "Some Relations Between Extended and Unscented Kalman Filters," Signal Processing, IEEE Transactions on, vol.60, no.2, pp.545-555, Feb. 2012
  21. R. Bass, V. Norum, and L. Schwartz, “Optimal multichannel nonlinear filtering(optimal multichannel nonlinear filtering problem of minimum variance estimation of state of n- dimensional nonlinear system subject to stochastic disturbance),” J. Mathematical Analysis and Applications, vol. 16, pp. 152–164, 1966
  22. Mohinder S. Grewal; Angus P. Andrews (2 February 2015). Kalman Filtering: Theory and Practice with MATLAB. John Wiley & Sons. ISBN   978-1-118-98496-3.
  23. Matía, F.; Jiménez, V.; Alvarado, B.P.; Haber, R. (January 2021). "The fuzzy Kalman filter: Improving its implementation by reformulating uncertainty representation". Fuzzy Sets Syst. 402: 78–104. doi:10.1016/j.fss.2019.10.015. S2CID   209913435.

Further reading