Kalman-Filter

The Kalman filter is a named after its discoverer Rudolf E. Kálmán set of mathematical equations. This filter is in the presence of faulty observations to draw conclusions about the state of many of the art, science or the economy associated systems possible. Put simply, the Kalman filter is used to remove the interference caused by the measuring instruments. Both the mathematical structure of the underlying dynamic system as well as the measurement errors have to be known.

Within the framework of the mathematical theory of estimation is also called a Bayesian minimum variance estimator for linear stochastic systems in state space representation.

A special feature of 1960 with the presentation of Kalman filter makes its special mathematical structure which allows its use in real-time systems of different technical areas. These include the analysis of radar signals for position tracking of moving objects (tracking) but also the use in electronic control circuits ubiquitous communication systems such as radio and computer.

• 3.1 prediction
• 3.2 correction
• 3.3 Notes to the continuous-time Kalman filter
• 3.4 initialization
• 3.5 properties
• 3.6 Applicability and Extensions

• 5.1 German -language literature
• 5.2 English-language literature

Historical

Although the wording of the filter after Rudolf E. Kálmán was previously almost identical method by Thorvald N. Thiele and Peter Swerling have been published. Also exist at the same time this more general, non-linear filter of Ruslan L. Stratonovich containing the Kalman filter and other linear filter as special cases. Also worth mentioning are preliminary and joint publications by Kálmán with Richard S. Bucy, especially for the case of continuous-time dynamical systems. Hence the term Kalman-Bucy filter, and occasionally Stratonovich Kalman-Bucy filter in the literature is often used.

The first notable and successful use of the filter was performed in real-time navigation and control systems, which were developed as part of the Apollo Program, NASA led by Stanley F. Schmidt.

Meanwhile, there is a wide range of Kalman filters for various applications. These are in addition to the original formulation, the extended Kalman filter, the Unscented Kalman Filter, the filter information and a plurality of numerically stable variants, such as the root of implementation or the Bierman UD - Thornton algorithm. The most widely used variant, however, is the control theory that were found phase-locked loop, an essential component of most modern means of communication.

Basics

In contrast to the classical FIR and IIR filters the signal and time series analysis, the Kalman filter is based on a state space modeling, a distinction is made explicitly between the dynamics of the system state and the process of its measurement in the.

State space modeling

As a state of a system is understood to be often the smallest, the system is fully descriptive set of defining pieces. This is in the context of modeling in the form of a multidimensional vector X with the corresponding equation of motion, the so-called equation of state represented. This equation is often a difference equation, since the states = t0 k ·? T in many cases only to certain, separated by fixed time intervals DELTA.t time points tk k is a natural number of interest. It has become common, the discrete time points tk a simple notation sake shortened equations to write down as a index k of the relevant size, tk -1 as an index k-1, etc., etc. With this notation and for the special case considered by Kálmán a purely linear function of the states to each other, the state equation simplifies to the linear difference equation

The matrix Fk -1 describes the transitions between successive states of Xk -1 and Xk. Besides expressed by the transition matrix Fk -1 actual dynamics, the equation of state also modeled more external influences on the system. A distinction is made between deterministic, that is completely determinable influences and such random in nature. The deterministic component is represented by the disturbance acting UK-1 and their dynamics in a matrix Bk -1; the random, non- detectable components by a noise term, the stochastic variable wk -1. The temporally uncorrelated noise wk- 1 follows a multivariate normal distribution with mean vector 0 and covariance matrix Qk -1, in the usual shorthand notation:

Due to the unpredictability of the noise term and the state vector contains a certain amount of "chance" and is thus itself a stochastic variable, a random variable. The set of all state vectors form a special stochastic process, a Markov chain or a first-order Markov model, ie the state at a time k depends only on the immediate predecessor of time k-1.

The process of observation of the true system states Xk, Xk -1, ... must reflect the characteristics of the observer or the measuring apparatus. This includes modeled distortion and unpredictable measurement noise. In the case of the Kalman filter, the distortion is assumed to be linear and the noise as temporally uncorrelated and normally distributed. The appropriate modeling of the measurement process, the observation equation is,

With the observation matrix Hk and the measurement noise

Dynamic noise w and measurement noise v should be independent of each other at all times.

The totality of state equation and observation equation is called state space model [A 1]. Due to the "hidden " or by a second stochastic process, the measurement, covered Markov model is called the state space model is also often of a hidden Markov model ( engl. Hidden Markov Model).

The filter problem

An application running in practice measurement results at a time often only a single realization of zk of the normally distributed random variable Zk. This begs the inverse problem, namely on the basis of information from a series of measurements with the values ​​z1, z2, z3, z4, ... to the corresponding X1, X2, X3, X4 ... to be able to draw conclusions. Since the desired states w, due to the linearity of the model and the assumptions made for the noise terms and remain v is normally distributed for all times and a normal distribution is completely described by its mean and covariance, the filter problem limited to the estimation of these two determining factors. A possible solution to this exact inverse problem is the time-discrete Kalman filter is a set of equations, then, the estimates for the mean and covariance of the state

Often, the task is to solve the filtering problem for continuous-time systems. The difference equations of state space model merge into differential equations by a mathematical limit education. The equations of continuous-time Kalman filter arise from the corresponding discrete-time filter by applying the same limit value education. For this reason, and in order of presentation, a will be discussed only to the equations of the discrete-time filter in the following.

Equations

The estimate of the state should be possible based on the knowledge of all previous observations. In this case, a minimum estimation error should be required, which should not be to improve by the observations already made. For a long series of measurements, the corresponding mathematical minimization problem is unwieldy since the entire series of measurements must be evaluated for each estimate. The idea of the Kalman filter is now to formulate the estimate at time k as a linear combination of the previous estimate with the new measurement zk. This is possible because the estimate at time k -1 contains the information of the measurement series zk -1, zk -2 ... z1. This recursive formulation of the estimation problem allows an efficient computational implementation.

The Kalman filter also besides its manageable via a recursive predictor-corrector structure.

Prediction

The first step of the filtering process the time of the previous estimate dynamic state is subjected, in order to obtain a prediction for the current time. For the mean results

And covariance

The indexing notation k | k-1 suppressed the conditional nature of the estimates at time points k and k -1 from each other. The superscript T denotes the transpose of the matrix marked accordingly.

Correction

Forecasts are finally corrected with the new information of the current measured value and yield the desired estimates

As well as

With the auxiliary variables Innovation

Residualkovarianz

And the corresponding Kalman matrix

The auxiliary variable innovation describes how accurate the predicted mean value to describe the current measured value by means of the observation equation is capable of. For a poor predictor the corresponding innovation is big, be small for an accurate prediction about it. Corresponding corrections have to be large or small. The correction to be applied can thus be regarded as proportional to the size of the innovation. In addition to innovations of measured values ​​that are subject to greater uncertainty than their estimates, go with less weight in the correction as those in which the opposite is the case. These properties are to be required just full of the Kalman matrix as the sought proportionality. This is from the equivalent formulation

Seen that, speaking in the context of this rather intuitive approach and thus simplistic, as the required ratio of the uncertainties of the predictions Pk to the associated measurement uncertainties Rk can be considered. [A 2] The elements of the Kalman matrix can analytically in many cases, calculated, or at least approximately determined before the start of the estimation process. In less time-critical applications, the Kalman matrix is ​​co-estimated, ie always recalculated during the estimation process from the current forecast of the covariance.

The exact derivation and justification of the prediction and correction equations is usually carried out in the framework of probabilistic considerations using the Bayestheorems.

Notes to the continuous-time Kalman filter

In the continuous-time case, we no longer speak of a recursive formulation and not even by a predictor - correction structure. Rather, one has to deal with a set of differential equations that describe the estimates of mean and covariance. In order to make statements about the estimate at a particular time, the mentioned differential equations must be solved. Due to a non-linear term in the co-variance equation, the so-called matrix Riccati equation is an exact solution and thus optimal estimation possible only in a few cases.

Initialization

For the initial estimate is often used

With the identity matrix I and a suitable constant c.

Properties

As is evident from the correction equation, the estimation of the mean value depends in a linear manner on the observation that the Kalman filter is a linear filter accordingly. As the length of the measurement series, the estimates for the mean and variance of the actual values ​​approximate with arbitrary precision. We therefore speak in statistical jargon of an expectant faithful and consistent estimator with minimum variance. Due to this estimation properties corresponding to a minimization of the mean square error here, the Kalman filter is an optimal linear filter. Even generalized nonlinear filters provide for the here considered nonlinear state space model with normally distributed variables to yield better results. Unlike other ( recursive ) linear estimators that minimize as squares, the Kalman filter also allows the treatment of problems with correlated noise components, as they are frequently encountered in practice.

Applicability and Extensions

The assumptions made in the derivation of the Kalman filter can be only approximately satisfied in practice at best. For example, in many cases, the exact structure of the linear state and observation equation unknown or too large for it to be computationally manageable in the context of the Kalman filter. The user must thus make a limitation to be used model classes. The associated inaccuracies can lead to deviating from optimal, a divergent behavior of the filter. Therefore, studies on the dependence of the estimation results of the modeling errors (and their compensation) are necessary in the context of a sensitivity analysis before use.

For a further limitation of the estimation quality lead caused by the use of digital computer technology rounding error. Similar to the model inaccuracies can lead to a drastic divergence of the Kalman filter. The remedy here is algebraic reformulations ( factorizations ) of the covariance matrices, but at the cost of increased computational complexity. The best known numerically stable variants of the Kalman filter implementation are the root by Potter et al. and their refinement in the form of the Bierman - Thornton UD algorithm.

In addition to these problems, the Kalman filter is not generally used in many cases, since it is limited to linear state space models. Even simple tasks of navigation technology or the important topic of parameter estimation, however, always lead to nonlinear state or observation equations. The remedy here, for example, nonlinear extensions of the Kalman filter as the already developed in the 60s Extended Kalman Filter ( EKF Abbr ) or the newer unscented Kalman filter ( UKF Abbr ). These Kalman filter approach, the non-linear variations problem with a linear, either analytical ( EKF ) techniques, or random ( UKF ) can be used. In terms of a simple language use, these extensions are often referred to for short as well as a Kalman filter, as they have well over a recursive and a predictor-corrector structure. In contrast to simple Kalman filter, the Kalman matrix is now a random variable and needs to be co-estimated, which increases the demands on the equipment during the whole filter element.

Since the advent of powerful digital computer technology practice has been to treat the most challenging non-linear filtering problems by simulations ( sequential Monte Carlo methods ) or other approximation methods ( quadrature filter Gaußsummenfilter, projection filter).

Sample Applications

The Kalman filter is now probably the most widely used algorithm for the state estimation of linear and nonlinear systems.

• Has been widely used in the Kalman filter, for example, inertial navigation of aircraft: During the flight of the aircraft acceleration and rate of rotation of an inertial measurement unit can be measured at high frequencies to provide a short-term navigation. Other sensors, especially satellite-based positioning (eg GPS ) provide supporting data. These different measurements must be linked ( " fused " ) in order to ensure the best possible estimate of the current position and orientation.

• Increasingly, tracking methods, and thus the Kalman filter as a typical representative of a tracking filter a role in the automotive industry. Security or convenience applications, which are based on environment discerning systems are based on reliable information (eg position, velocity ) with respect to the dependent objects in their environment.

• One type is also often used a Kalman filter, the PLL filter has found widespread use today in radios, radios, computers, and almost all other types of video and communications equipment.

• In macroeconomics Kalman filters are used for the estimation of dynamic stochastic general equilibrium models ( DSGE models).