Kalman Filtering Algorithm

A Kalman Filtering Algorithm is a recursive discrete-data linear filtering algorithm (that can estimate the internal state of a linear dynamic system from a noisy data series).

• AKA: Linear Quadratic Estimation, LQE.
• Context:
  • It can be used as an Autoregressor for continuous variables (assuming Gaussian noise).
  • It can range from being a Univariate Kalman Filter to being a Multivariate Kalman Filter.
  • It can be implemented by a Kalman Filter System (to solve a Kalman filtering task).
  • It can (typically) use Bayesian Updating (via Bayes theorem).
  • It can be referenced by an Extended Kalman Filter.
  • …
• Counter-Example(s):
  • a Bayesian Filter.
  • a Gabor Filter.
• See: Linear Filter, Moving Average, Recursive Algorithm, Forecasting Algorithm, Linear Dynamical System, Linear-Quadratic Regulator, Linear-Quadratic-Gaussian Control.

---

---

References

2018

• https://rodneybrooks.com/my-dated-predictions/
  • QUOTE: … Kalman filtering was used to track the spacecraft (completely true), that Kalman filtering uses Bayesian updating (completely true), and that therefore Kalman filtering is an instance of machine learning (complete non sequitur) and that therefore machine learning was used to get to the Moon (a valid inference based on a non-sequitur, and completely wrong). When anyone says Machine Learning these days (and indeed since the introduction of the term in 1959 by Arthur Samuel (see my post on ML for details) they mean using examples in same way to induce a representation of some concept that can later be used to select a label or action, based on an input and that saved learned material. Kalman filtering uses multiple data points from a particular process to get a good estimate of what the data is really saying. It does not save anything for later to be used for a similar problem at some future time. So, no, it is not Machine Learning, …

2015

• http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/
  • QUOTE: Kalman filters are ideal for systems which are continuously changing. They have the advantage that they are light on memory (they don’t need to keep any history other than the previous state), and they are very fast, making them well suited for real time problems and embedded systems.

2014

• (Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/Kalman_filter#Technical_description_and_context Retrieved:2014-9-23.
  • The Kalman filter is an efficient recursive filter that estimates the internal state of a linear dynamic system from a series of noisy measurements. It is used in a wide range of engineering and econometric applications from radar and computer vision to estimation of structural macroeconomic models, and is an important topic in control theory and control systems 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 in control theory.

    In most applications, the internal state is much larger (more degrees of freedom) than the few "observable" parameters which are measured. However, by combining a series of measurements, the Kalman filter can estimate the entire internal state.

    In Dempster–Shafer theory, each state equation or observation is considered a special case of a linear belief function and the Kalman filter is a special case of combining linear belief functions on a join-tree or Markov tree. Additional approaches include belief filters which use Bayes or evidential updates to the state equations.

    A wide variety of Kalman filters have now been developed, from Kalman's original formulation, now called 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, which is now ubiquitous in radios, especially frequency modulation (FM) radios, television sets, satellite communications receivers, outer space communications systems, and nearly any other electronic communications equipment.

2012

• http://en.wikipedia.org/wiki/Kalman_filter
  • QUOTE:The Kalman filter is an algorithm which operates recursively on streams of noisy input data to produce a statistically optimal estimate of the underlying system state. The filter is named for Rudolf (Rudy) E. Kálmán, one of the primary developers of its theory.

    The Kalman filter has numerous applications in technology. A simple and ubiquitous example is the phase-locked loop, used in FM radios and most electronic communications equipment.^{[citation needed]} Another common application is for guidance, navigation and control of vehicles, particularly aircraft and spacecraft.

    Sensors are used to make measurements of the system's state (position and velocity, in the case of a vehicle), but the measurements are always corrupted with some amount of error, including random noise. The Kalman Filter algorithm is an optimized method for determining the best estimation of the vehicle's state. The basic concept is similar to simple mathematical curve-fitting of data points using a least-squares approximation and enables predictions of the state into future time steps. The most basic concepts of the filter are related to interpolation (where data estimates are filled in between given points) and extrapolation (data estimates being extended beyond the given set, e.g. future estimates).

     The algorithm works in a two-step process: in the prediction step, the Kalman filter produces estimates of the true unknown values, along with their uncertainties. Once the outcome of the next measurement is observed, these estimates are updated using a weighted average, with more weight being given to estimates with higher certainty. This method produces estimates that tend to be closer to the true unknown values than those that would be based on a single measurement alone or the model predictions alone.

    Because the certainty of the measurements is often difficult to measure precisely, it is common to discuss the filter's behavior in terms of gain. The Kalman gain is a function of the relative certainty of the measurements and current state estimate, and can be "tuned" to achieve particular performance. With a high gain, the filter places more weight on the measurements, and thus follows them more closely. With a low gain, the filter follows the model predictions more closely, smoothing out noise but decreasing the responsiveness. At the extremes, a gain of one causes the filter to ignore the state estimate entirely, while a gain of zero causes the measurements to be ignored.

    Because of the algorithm's recursive nature, it can run in real time using only the present input measurements and the previously calculated state; no additional past information is required. From a theoretical standpoint, the main assumption of the Kalman filter is that the underlying system is a linear dynamical system and that all error terms and measurements have a Gaussian distribution (often a multivariate Gaussian distribution). Extensions and generalizations to the method have also been developed, such as the Extended Kalman Filter and the Unscented Kalman filter which work on nonlinear systems. The underlying model is a Bayesian model similar to a hidden Markov model but where the state space of the latent variables is continuous and where all latent and observed variables have Gaussian distributions.

1995

• (Welch & Bishop, 1995) ⇒ Greg Welch, and Gary Bishop. (1995). “An Introduction to the Kalman Filter." Technical Report, TR95-041. University of North Carolina at Chapel Hill
  • ABSTRACT: In 1960, R.E. Kalman published his famous paper describing a recursive solution to the discrete-data linear filtering problem. Since that time, due in large part to advances in digital computing, the Kalman filter has been the subject of extensive research and application, particularly in the area of autonomous or assisted navigation. The Kalman filter is a set of mathematical equations that provides an efficient computational (recursive) means to estimate the state of a process, in a way that minimizes the mean of the squared error. The filter is very powerful in several aspects: it supports estimations of past, present, and even future states, and it can do so even when the precise nature of the modeled system is unknown. The purpose of this paper is to provide a practical introduction to the discrete Kalman filter. This introduction includes a description and some discussion of the basic discrete Kalman filter, a derivation, description and some discussion of the extended Kalman filter, and a relatively simple (tangible) example with real numbers & results.

1960

• (Kalman, 1960) ⇒ Rudolf E. Kálmán. (1960). “A New Approach to Linear Filtering and Prediction Problems". In: Journal of Basic Engineering, 82(1).

---