For
statistics
Statistics (from German: '' Statistik'', "description of a state, a country") is the discipline that concerns the collection, organization, analysis, interpretation, and presentation of data. In applying statistics to a scientific, indust ...
and
control theory
Control theory is a field of mathematics that deals with the control system, control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive ...
, Kalman filtering, also known as linear quadratic estimation (LQE), is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
that uses a series of measurements observed over time, including
statistical noise and other inaccuracies, and produces estimates of unknown variables that tend to be more accurate than those based on a single measurement alone, by estimating a
joint probability distribution
Given two random variables that are defined on the same probability space, the joint probability distribution is the corresponding probability distribution on all possible pairs of outputs. The joint distribution can just as well be considered ...
over the variables for each timeframe. The filter is named after
Rudolf E. Kálmán, who was one of the primary developers of its theory.
This digital filter is sometimes termed the ''Stratonovich–Kalman–Bucy filter'' because it is a special case of a more general, nonlinear filter developed somewhat earlier by the Soviet
mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems.
Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change.
History
On ...
Ruslan Stratonovich. In fact, some of the special case linear filter's equations appeared in papers by Stratonovich that were published before summer 1960, when Kalman met with Stratonovich during a conference in Moscow.
Kalman filtering has numerous technological applications. A common application is for
guidance, navigation, and control
Guidance, navigation and control (abbreviated GNC, GN&C, or G&C and within the context of NASA operations, often pronounced 'Gintsee' or (IPA) ʤɪnsiː) is a branch of engineering dealing with the design of systems to control the movement ...
of vehicles, particularly aircraft, spacecraft and ships
positioned dynamically.
Furthermore, Kalman filtering is a concept much applied in
time series
In mathematics, a time series is a series of data points indexed (or listed or graphed) in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. Thus it is a sequence of discrete-time data. Ex ...
analysis used for topics such as
signal processing
Signal processing is an electrical engineering subfield that focuses on analyzing, modifying and synthesizing '' signals'', such as sound, images, and scientific measurements. Signal processing techniques are used to optimize transmissions, ...
and
econometrics
Econometrics is the application of statistical methods to economic data in order to give empirical content to economic relationships. M. Hashem Pesaran (1987). "Econometrics," '' The New Palgrave: A Dictionary of Economics'', v. 2, p. 8 p. ...
. Kalman filtering is also one of the main topics of robotic
motion planning
Motion planning, also path planning (also known as the navigation problem or the piano mover's problem) is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is use ...
and control and can be used for
trajectory optimization. Kalman filtering also works for modeling the
central nervous system
The central nervous system (CNS) is the part of the nervous system consisting primarily of the brain and spinal cord. The CNS is so named because the brain integrates the received information and coordinates and influences the activity of all p ...
's control of movement. Due to the time delay between issuing motor commands and receiving
sensory feedback, the use of Kalman filters provides a realistic model for making estimates of the current state of a motor system and issuing updated commands.
The algorithm works by a two-phase process. For the prediction phase, the Kalman filter produces estimates of the current
state variable
A state variable is one of the set of variables that are used to describe the mathematical "state" of a dynamical system. Intuitively, the state of a system describes enough about the system to determine its future behaviour in the absence of a ...
s, along with their uncertainties. Once the outcome of the next measurement (necessarily corrupted with some error, including random noise) is observed, these estimates are updated using a
weighted average, with more weight being given to estimates with greater certainty. The algorithm is
recursive. It can operate in
real time, using only the present input measurements and the state calculated previously and its uncertainty matrix; no additional past information is required.
Optimality of Kalman filtering assumes that errors have a
normal (Gaussian) distribution. In the words of
Rudolf E. Kálmán: "In summary, the following assumptions are made about random processes: Physical random phenomena may be thought of as due to primary random sources exciting dynamic systems. The primary sources are assumed to be independent gaussian random processes with zero mean; the dynamic systems will be linear." Though regardless of Gaussianity, if the process and measurement covariances are known, the Kalman filter is the best possible ''
linear
Linearity is the property of a mathematical relationship ('' function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear ...
'' estimator in the
minimum mean-square-error sense.
Extensions and
generalization
A generalization is a form of abstraction whereby common properties of specific instances are formulated as general concepts or claims. Generalizations posit the existence of a domain or set of elements, as well as one or more common character ...
s of the method have also been developed, such as the
extended Kalman filter and the
unscented Kalman filter which work on
nonlinear system
In mathematics and science, a nonlinear system is a system in which the change of the output is not proportional to the change of the input. Nonlinear problems are of interest to engineers, biologists, physicists, mathematicians, and many othe ...
s. The basis is a
hidden Markov model
A hidden Markov model (HMM) is a statistical Markov model in which the system being modeled is assumed to be a Markov process — call it X — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an ...
such that the
state space of the
latent variables is
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous g ...
and all latent and observed variables have Gaussian distributions. Kalman filtering has been used successfully in
multi-sensor fusion, and distributed
sensor networks to develop distributed or
consensus Kalman filtering.
History
The filtering method is named for Hungarian
émigré
An ''émigré'' () is a person who has emigrated, often with a connotation of political or social self-exile. The word is the past participle of the French ''émigrer'', "to emigrate".
French Huguenots
Many French Huguenots fled France followin ...
Rudolf E. Kálmán, although
Thorvald Nicolai Thiele and
Peter Swerling developed a similar algorithm earlier. Richard S. Bucy of the
Johns Hopkins Applied Physics Laboratory contributed to the theory, causing it to be known sometimes as Kalman–Bucy filtering.
Stanley F. Schmidt
Stanley F. Schmidt (January 21, 1926 – August 13, 2015) was an American aerospace engineer who pioneered the Schmidt-Kalman filter used in air and space navigation, most notably in Apollo program, Apollo spacecraft.
Early life and education
S ...
is generally credited with developing the first implementation of a Kalman filter. He realized that the filter could be divided into two distinct parts, with one part for time periods between sensor outputs and another part for incorporating measurements. It was during a visit by Kálmán to the
NASA Ames Research Center that Schmidt saw the applicability of Kálmán's ideas to the nonlinear problem of trajectory estimation for the
Apollo program resulting in its incorporation in the
Apollo navigation computer.
This Kalman filtering was first described and developed partially in technical papers by Swerling (1958), Kalman (1960) and Kalman and Bucy (1961).
Kalman filters have been vital in the implementation of the navigation systems of
U.S. Navy nuclear
ballistic missile submarine
A ballistic missile submarine is a submarine capable of deploying submarine-launched ballistic missiles (SLBMs) with nuclear warheads. The United States Navy's hull classification symbols for ballistic missile submarines are SSB and SSBN � ...
s, and in the guidance and navigation systems of cruise missiles such as the U.S. Navy's
Tomahawk missile and the
U.S. Air Force's
Air Launched Cruise Missile
An air-launched cruise missile (ALCM) is a cruise missile that is launched from a military aircraft. Current versions are typically standoff weapons which are used to attack predetermined land targets with conventional, nuclear or thermonuclear ...
. They are also used in the guidance and navigation systems of
reusable launch vehicles and the
attitude control and navigation systems of spacecraft which dock at the
International Space Station
The International Space Station (ISS) is the largest Modular design, modular space station currently in low Earth orbit. It is a multinational collaborative project involving five participating space agencies: NASA (United States), Roscosmos ( ...
.
Overview of the calculation
Kalman filtering uses a system's dynamic model (e.g., physical laws of motion), known control inputs to that system, and multiple sequential measurements (such as from sensors) to form an estimate of the system's varying quantities (its
state
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
) that is better than the estimate obtained by using only one measurement alone. As such, it is a common
sensor fusion and
data fusion algorithm.
Noisy sensor data, approximations in the equations that describe the system evolution, and external factors that are not accounted for, all limit how well it is possible to determine the system's state. The Kalman filter deals effectively with the uncertainty due to noisy sensor data and, to some extent, with random external factors. The Kalman filter produces an estimate of the state of the system as an average of the system's predicted state and of the new measurement using a
weighted average. The purpose of the weights is that values with better (i.e., smaller) estimated uncertainty are "trusted" more. The weights are calculated from the
covariance
In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the le ...
, a measure of the estimated uncertainty of the prediction of the system's state. The result of the weighted average is a new state estimate that lies between the predicted and measured state, and has a better estimated uncertainty than either alone. This process is repeated at every time step, with the new estimate and its covariance informing the prediction used in the following iteration. This means that Kalman filter works
recursively and requires only the last "best guess", rather than the entire history, of a system's state to calculate a new state.
The measurements' certainty-grading and current-state estimate are important considerations. It is common to discuss the filter's response in terms of the Kalman filter's ''
gain
Gain or GAIN may refer to:
Science and technology
* Gain (electronics), an electronics and signal processing term
* Antenna gain
* Gain (laser), the amplification involved in laser emission
* Gain (projection screens)
* Information gain in de ...
''. The Kalman-gain is the weight given to the measurements and current-state estimate, and can be "tuned" to achieve a particular performance. With a high gain, the filter places more weight on the most recent measurements, and thus conforms to them more responsively. With a low gain, the filter conforms to the model predictions more closely. At the extremes, a high gain close to one will result in a more jumpy estimated trajectory, while a low gain close to zero will smooth out noise but decrease the responsiveness.
When performing the actual calculations for the filter (as discussed below), the state estimate and covariances are coded into
matrices because of the multiple dimensions involved in a single set of calculations. This allows for a representation of linear relationships between different state variables (such as position, velocity, and acceleration) in any of the transition models or covariances.
Example application
As an example application, consider the problem of determining the precise location of a truck. The truck can be equipped with a
GPS unit that provides an estimate of the position within a few meters. The GPS estimate is likely to be noisy; readings 'jump around' rapidly, though remaining within a few meters of the real position. In addition, since the truck is expected to follow the laws of physics, its position can also be estimated by integrating its velocity over time, determined by keeping track of wheel revolutions and the angle of the steering wheel. This is a technique known as
dead reckoning
In navigation, dead reckoning is the process of calculating current position of some moving object by using a previously determined position, or fix, and then incorporating estimates of speed, heading direction, and course over elapsed time. ...
. Typically, the dead reckoning will provide a very smooth estimate of the truck's position, but it will
drift
Drift or Drifts may refer to:
Geography
* Drift or ford (crossing) of a river
* Drift, Kentucky, unincorporated community in the United States
* In Cornwall, England:
** Drift, Cornwall, village
** Drift Reservoir, associated with the village
...
over time as small errors accumulate.
For this example, the Kalman filter can be thought of as operating in two distinct phases: predict and update. In the prediction phase, the truck's old position will be modified according to the physical
laws of motion (the dynamic or "state transition" model). Not only will a new position estimate be calculated, but also a new covariance will be calculated as well. Perhaps the covariance is proportional to the speed of the truck because we are more uncertain about the accuracy of the dead reckoning position estimate at high speeds but very certain about the position estimate at low speeds. Next, in the update phase, a measurement of the truck's position is taken from the GPS unit. Along with this measurement comes some amount of uncertainty, and its covariance relative to that of the prediction from the previous phase determines how much the new measurement will affect the updated prediction. Ideally, as the dead reckoning estimates tend to drift away from the real position, the GPS measurement should pull the position estimate back toward the real position but not disturb it to the point of becoming noisy and rapidly jumping.
Technical description and context
The Kalman filter is an efficient
recursive filter In signal processing, a recursive filter is a type of filter which re-uses one or more of its outputs as an input. This feedback typically results in an unending impulse response (commonly referred to as ''infinite impulse response'' (IIR)), chara ...
estimating the internal state of a
linear dynamic system from a series of
noisy measurements. It is used in a wide range of
engineering
Engineering is the use of scientific principles to design and build machines, structures, and other items, including bridges, tunnels, roads, vehicles, and buildings. The discipline of engineering encompasses a broad range of more speciali ...
and
econometric applications from
radar
Radar is a detection system that uses radio waves to determine the distance (''ranging''), angle, and radial velocity of objects relative to the site. It can be used to detect aircraft, Marine radar, ships, spacecraft, guided missiles, motor v ...
and
computer vision
Computer vision is an interdisciplinary scientific field that deals with how computers can gain high-level understanding from digital images or videos. From the perspective of engineering, it seeks to understand and automate tasks that the human ...
to estimation of structural macroeconomic models, and is an important topic in
control theory
Control theory is a field of mathematics that deals with the control system, control of dynamical systems in engineered processes and machines. The objective is to develop a model or algorithm governing the application of system inputs to drive ...
and
control system
A control system manages, commands, directs, or regulates the behavior of other devices or systems using control loops. It can range from a single home heating controller using a thermostat controlling a domestic boiler to large industrial ...
s engineering. Together with the
linear-quadratic regulator (LQR), the Kalman filter solves the
linear–quadratic–Gaussian control problem (LQG). The Kalman filter, the linear-quadratic regulator, and the linear–quadratic–Gaussian controller are solutions to what arguably are the most fundamental problems of control theory.
In most applications, the internal state is much larger (has more
degrees of freedom
Degrees of freedom (often abbreviated df or DOF) refers to the number of independent variables or parameters of a thermodynamic system. In various scientific fields, the word "freedom" is used to describe the limits to which physical movement or ...
) than the few "observable" parameters which are measured. However, by combining a series of measurements, the Kalman filter can estimate the entire internal state.
For the
Dempster–Shafer theory, each state equation or observation is considered a special case of a
linear belief function Linear belief functions are an extension of the Dempster–Shafer theory of belief functions to the case when variables of interest are continuous. Examples of such variables include financial asset prices, portfolio performance, and other anteced ...
and the Kalman filtering is a special case of combining linear belief functions on a join-tree or
Markov tree. Additional methods include
belief filtering which use Bayes or evidential updates to the state equations.
A wide variety of Kalman filters exists by now, from Kalman's original formulation - now termed the "simple" Kalman filter, the
Kalman–Bucy filter, Schmidt's "extended" filter, the
information filter, and a variety of "square-root" filters that were developed by Bierman, Thornton, and many others. Perhaps the most commonly used type of very simple Kalman filter is the
phase-locked loop
A phase-locked loop or phase lock loop (PLL) is a control system that generates an output signal whose phase is related to the phase of an input signal. There are several different types; the simplest is an electronic circuit consisting of a ...
, which is now ubiquitous in radios, especially
frequency modulation
Frequency modulation (FM) is the encoding of information in a carrier wave by varying the instantaneous frequency of the wave. The technology is used in telecommunications, radio broadcasting, signal processing, and computing.
In analog ...
(FM) radios, television sets,
satellite communications
A communications satellite is an artificial satellite that relays and amplifies radio telecommunication signals via a transponder; it creates a communication channel between a source transmitter and a receiver at different locations on Earth. ...
receivers, outer space communications systems, and nearly any other
electronic communications equipment.
Underlying dynamic system model
Kalman filtering is based on
linear dynamic systems discretized in the time domain. They are modeled on a
Markov chain
A Markov chain or Markov process is a stochastic model describing a sequence of possible events in which the probability of each event depends only on the state attained in the previous event. Informally, this may be thought of as, "What happen ...
built on
linear operator
In mathematics, and more specifically in linear algebra, a linear map (also called a linear mapping, linear transformation, vector space homomorphism, or in some contexts linear function) is a Map (mathematics), mapping V \to W between two vect ...
s perturbed by errors that may include
Gaussian
Carl Friedrich Gauss (1777–1855) is the eponym of all of the topics listed below.
There are over 100 topics all named after this German mathematician and scientist, all in the fields of mathematics, physics, and astronomy. The English eponym ...
noise
Noise is unwanted sound considered unpleasant, loud or disruptive to hearing. From a physics standpoint, there is no distinction between noise and desired sound, as both are vibrations through a medium, such as air or water. The difference aris ...
. The
state
State may refer to:
Arts, entertainment, and media Literature
* ''State Magazine'', a monthly magazine published by the U.S. Department of State
* ''The State'' (newspaper), a daily newspaper in Columbia, South Carolina, United States
* ''Our S ...
of the target system refers to the ground truth (yet hidden) system configuration of interest, which is represented as a
vector of
real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s. At each
discrete time
In mathematical dynamics, discrete time and continuous time are two alternative frameworks within which variables that evolve over time are modeled.
Discrete time
Discrete time views values of variables as occurring at distinct, separate "po ...
increment, a linear operator is applied to the state to generate the new state, with some noise mixed in, and optionally some information from the controls on the system if they are known. Then, another linear operator mixed with more noise generates the measurable outputs (i.e., observation) from the true ("hidden") state. The Kalman filter may be regarded as analogous to the hidden Markov model, with the difference that the hidden state variables have values in a continuous space as opposed to a discrete state space as for the hidden Markov model. There is a strong analogy between the equations of a Kalman Filter and those of the hidden Markov model. A review of this and other models is given in Roweis and
Ghahramani (1999) and Hamilton (1994), Chapter 13.
[Hamilton, J. (1994), ''Time Series Analysis'', Princeton University Press. Chapter 13, 'The Kalman Filter']
In order to use the Kalman filter to estimate the internal state of a process given only a sequence of noisy observations, one must model the process in accordance with the following framework. This means specifying the matrices, for each time-step ''k'', following:
* F
''k'', the state-transition model;
* H
''k'', the observation model;
* Q
''k'', the
covariance
In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the le ...
of the process noise;
* R
''k'', the
covariance
In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the le ...
of the observation noise;
* and sometimes B
''k'', the control-input model as described below; if B
''k'' is included, then there is also
* u
''k'', the control vector, representing the controlling input into control-input model.
The Kalman filter model assumes the true state at time ''k'' is evolved from the state at (''k'' − 1) according to
:
where
* F
''k'' is the state transition model which is applied to the previous state x
''k''−1;
* B
''k'' is the control-input model which is applied to the control vector u
''k'';
* w
''k'' is the process noise, which is assumed to be drawn from a zero mean
multivariate normal distribution
In probability theory and statistics, the multivariate normal distribution, multivariate Gaussian distribution, or joint normal distribution is a generalization of the one-dimensional ( univariate) normal distribution to higher dimensions. One ...
,
, with
covariance
In probability theory and statistics, covariance is a measure of the joint variability of two random variables. If the greater values of one variable mainly correspond with the greater values of the other variable, and the same holds for the le ...
, Q
''k'':
.
At time ''k'' an observation (or measurement) z
''k'' of the true state x
''k'' is made according to
:
where
* H
''k'' is the observation model, which maps the true state space into the observed space and
* v
''k'' is the observation noise, which is assumed to be zero mean Gaussian
white noise
In signal processing, white noise is a random signal having equal intensity at different frequencies, giving it a constant power spectral density. The term is used, with this or similar meanings, in many scientific and technical disciplines ...
with covariance R
''k'':
.
The initial state, and the noise vectors at each step are all assumed to be mutually
independent
Independent or Independents may refer to:
Arts, entertainment, and media Artist groups
* Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s
* Independe ...
.
Many real-time dynamic systems do not exactly conform to this model. In fact, unmodeled dynamics can seriously degrade the filter performance, even when it was supposed to work with unknown stochastic signals as inputs. The reason for this is that the effect of unmodeled dynamics depends on the input, and, therefore, can bring the estimation algorithm to instability (it diverges). On the other hand, independent white noise signals will not make the algorithm diverge. The problem of distinguishing between measurement noise and unmodeled dynamics is a difficult one and is treated as a problem of control theory using
robust control In control theory, robust control is an approach to controller design that explicitly deals with uncertainty. Robust control methods are designed to function properly provided that uncertain parameters or disturbances are found within some (typicall ...
.
Details
The Kalman filter is a
recursive estimator. This means that only the estimated state from the previous time step and the current measurement are needed to compute the estimate for the current state. In contrast to batch estimation techniques, no history of observations and/or estimates is required. In what follows, the notation
represents the estimate of
at time ''n'' given observations up to and including at time .
The state of the filter is represented by two variables:
*
, the ''
a posteriori
("from the earlier") and ("from the later") are Latin phrases used in philosophy to distinguish types of knowledge, justification, or argument by their reliance on empirical evidence or experience. knowledge is independent from current ex ...
'' state estimate at time ''k'' given observations up to and including at time ''k'';
*
, the ''a posteriori'' estimate covariance matrix (a measure of the estimated
accuracy
Accuracy and precision are two measures of '' observational error''.
''Accuracy'' is how close a given set of measurements ( observations or readings) are to their '' true value'', while ''precision'' is how close the measurements are to each o ...
of the state estimate).
The algorithm structure of the Kalman filter resembles that of
Alpha beta filter
An alpha beta filter (also called alpha-beta filter, f-g filter or g-h filterEli Brookner: Tracking and Kalman Filtering Made Easy. Wiley-Interscience, 1st edition, 4 1998.) is a simplified form of observer for estimation, data smoothing and contr ...
. The Kalman filter can be written as a single equation; however, it is most often conceptualized as two distinct phases: "Predict" and "Update". The predict phase uses the state estimate from the previous timestep to produce an estimate of the state at the current timestep. This predicted state estimate is also known as the ''a priori'' state estimate because, although it is an estimate of the state at the current timestep, it does not include observation information from the current timestep. In the update phase, the
innovation
Innovation is the practical implementation of ideas that result in the introduction of new goods or services or improvement in offering goods or services. ISO TC 279 in the standard ISO 56000:2020 defines innovation as "a new or changed enti ...
(the pre-fit residual), i.e. the difference between the current ''a priori'' prediction and the current observation information, is multiplied by the optimal Kalman gain and combined with the previous state estimate to refine the state estimate. This improved estimate based on the current observation is termed the ''a posteriori'' state estimate.
Typically, the two phases alternate, with the prediction advancing the state until the next scheduled observation, and the update incorporating the observation. However, this is not necessary; if an observation is unavailable for some reason, the update may be skipped and multiple prediction procedures performed. Likewise, if multiple independent observations are available at the same time, multiple update procedures may be performed (typically with different observation matrices H
''k'').
Predict
Update
The formula for the updated (''a posteriori'') estimate covariance above is valid for the optimal K
k gain that minimizes the residual error, in which form it is most widely used in applications. Proof of the formulae is found in the ''
derivations'' section, where the formula valid for any K
k is also shown.
A more intuitive way to express the updated state estimate (
) is:
:
This expression reminds us of a linear interpolation,
for
between
,1
In our case:
*
is the Kalman gain (
), a matrix that takes values from
(high error in the sensor) to
(low error).
*
is the value estimated from the model.
*
is the value from the measurement.
This expression also resembles the
alpha beta filter
An alpha beta filter (also called alpha-beta filter, f-g filter or g-h filterEli Brookner: Tracking and Kalman Filtering Made Easy. Wiley-Interscience, 1st edition, 4 1998.) is a simplified form of observer for estimation, data smoothing and contr ...
update step.
Invariants
If the model is accurate, and the values for
and
accurately reflect the distribution of the initial state values, then the following invariants are preserved:
:
where