Kalman filter

• 1. Introduction

  ›

  The Kalman filter is the hidden arithmetic behind some of the most consequential machines ever built. It flew to the Moon inside the Apollo navigation computer. It steers U.S. Navy nuclear ballistic missile submarines through the deep. It guides cruise missiles like the Tomahawk to within meters of their targets. And right now, somewhere in the world, a truck driver has no idea that the smooth GPS reading on their dashboard is only that smooth because of a recursive algorithm published in 1960.

  At its heart, the Kalman filter answers a question that haunts every measurement ever taken: if your sensors are noisy and your models are imperfect, what is your best possible guess about what is actually happening? The answer, it turns out, is not to trust one reading. It is to combine every piece of evidence you have, weight it by how reliable it is, and update your estimate every single time a new measurement arrives.

  The filter is named for Rudolf E. Kalman, a Hungarian emigre whose ideas were so ahead of their time that the Soviet mathematician Ruslan Stratonovich had already published some of the same equations before the two men met at a conference in Moscow in the summer of 1961. Who deserves credit, how the algorithm found its way into the Apollo program, and why the most widely used version of the filter is now found in virtually every FM radio on Earth are the threads this story will follow.

• 2. The Two-Step Machine

  ›

  Rudolf Kálmán did not invent the problem of noisy measurement. Norbert Wiener had already attacked it, producing what became known as the Wiener filter. What Kálmán did was reframe the problem using state variables, a move that changed everything. By thinking about a system's hidden internal condition rather than just its observable outputs, he opened a path to an algorithm that could run in real time, updating itself moment by moment with no need to store or reprocess the past.

  The algorithm works in two distinct phases. In the prediction phase, the filter uses a mathematical model of how the system behaves to project forward: given where things were, where should they be now? In the update phase, a new measurement arrives. That measurement is noisy, necessarily corrupted with some error. The filter does not simply replace its prediction with the measurement. Instead, it forms a weighted average. Estimates with smaller uncertainty are trusted more. The result lands between the predicted state and the measured state, and its uncertainty is smaller than either alone.

  This process repeats at every time step. Each cycle needs only the previous best estimate and its uncertainty matrix. No history of observations is required. Stanley F. Schmidt, who is generally credited with developing the first implementation, recognized that this recursive structure meant the filter could be divided into two distinct processing stages. It was that recognition, made during a visit by Kálmán to the NASA Ames Research Center, that led Schmidt to see how the algorithm could solve the nonlinear problem of trajectory estimation for the Apollo program.

• 3. Apollo and the Nuclear Fleet

  ›

  The Apollo navigation computer had 2k of magnetic core RAM and 36k of wire rope memory. Its clock speed ran under 100 kHz. By the standards of any era that came after, it was a device of almost laughable constraint. Yet MIT engineers packed into it one of the very first real applications of the Kalman filter, and it worked. Astronauts navigated to the Moon and back.

  The Kalman filter's arrival in military systems was equally consequential. The navigation systems of U.S. Navy nuclear ballistic missile submarines depend on it. The guidance and navigation of the Tomahawk cruise missile rely on it, as does the U.S. Air Force's Air Launched Cruise Missile. Spacecraft that dock at the International Space Station use it for attitude control and navigation.

  The path to these applications ran through the work of Kálmán and Richard S. Bucy of the Johns Hopkins Applied Physics Laboratory, whose contributions were significant enough that the algorithm is sometimes called Kalman-Bucy filtering. The continuous-time version of the filter, which Bucy helped develop, is now formally named the Kalman-Bucy filter. The original technical papers appeared in 1958 from Swerling, in 1960 from Kalman, and in 1961 from Kalman and Bucy together.

• 4. The Gaussian Assumption and Its Limits

  ›

  In his own words, Rudolf Kálmán specified that "the primary sources are assumed to be independent Gaussian random processes with zero mean; the dynamic systems will be linear." That sentence contains the filter's most important constraint and one of its most persistent misunderstandings at once.

  The misunderstanding, which has been perpetuated in the technical literature, is the belief that the Kalman filter cannot be rigorously applied unless all noise processes are Gaussian. This is not true. If the process and measurement covariances are known, the Kalman filter is the best possible linear estimator in the minimum mean-square-error sense regardless of whether the noise is Gaussian. There may be better nonlinear estimators in the non-Gaussian case, but the filter's claim as the optimal linear estimator stands.

  The harder practical problem is getting good estimates of the noise covariance matrices in the first place. Knowing how much your sensors are wrong, and how much your model of the world is wrong, is not always possible from theory alone. The autocovariance least-squares technique addresses this by using time-lagged autocovariances of routine operating data. GNU Octave and Matlab code for this technique is available under the GNU General Public License. A more recent approach, the Optimized Kalman Filter, treats the covariance matrices not as descriptions of noise but as tunable parameters aimed directly at achieving the most accurate state estimation possible.

• 5. Beyond Linearity

  ›

  Real physical systems rarely behave as cleanly as the linear model assumes. A spacecraft maneuvering through a gravitational field, a robot navigating a cluttered environment, an aircraft responding to turbulence all involve nonlinearities that the basic filter cannot directly handle. Two descendants of the original algorithm address this.

  The Extended Kalman Filter, often abbreviated EKF, handles nonlinear systems by linearizing around the current estimate at each time step. It computes a matrix of partial derivatives, the Jacobian, of the nonlinear transition and observation functions. This local linearization lets the rest of the filter proceed as normal. Schmidt's original application to the Apollo trajectory problem was itself an extended filter, which is why it is sometimes called Schmidt's extended filter in the historical taxonomy.

  When the nonlinearity is severe, the EKF's linearization can produce poor results because it propagates the covariance through that local approximation rather than through the true nonlinear function. The Unscented Kalman Filter takes a different approach. It selects a minimal set of sample points, called sigma points, that capture the mean and covariance of the current estimate, propagates those points through the nonlinear functions directly, and then reconstructs the mean and covariance from the result. A typical recommended parameterization uses values of alpha equal to 0.001, beta equal to 2, and kappa equal to 0 when the true distribution is Gaussian. This approach also removes the requirement to calculate Jacobians, which can be analytically difficult or computationally costly for complex functions.

• 6. The Filter Everywhere

  ›

  Thorvald Nicolai Thiele and Peter Swerling each developed similar algorithms before Kálmán published in 1960. The filter's independent rediscovery by Stratonovich, whose papers on the linear special case appeared before the two men met in Moscow, reflects how naturally the idea arises from a general set of mathematical pressures. A family of solutions was converging on the same structure from multiple directions.

  The variants that have accumulated since are numerous. The information filter, which inverts the covariance matrix and represents state as an information vector, becomes more efficient when the number of observations exceeds the dimension of the state. Square-root filters, developed by Bierman and Thornton among others, address numerical instability by factoring the covariance matrix into a product form that guarantees positive-definiteness even when round-off error would otherwise corrupt it. The U-D decomposition, where the matrix is expressed as the product of a unit triangular matrix and a diagonal matrix, uses the same storage as the Cholesky factorization but somewhat less computation.

  Perhaps the most ubiquitous descendant is the phase-locked loop. It is now found in FM radios, television sets, satellite communications receivers, and nearly any other electronic communications equipment. Most people who have never heard the name Kalman have nonetheless relied on his algorithm every time they tuned a radio. The application to modeling the central nervous system's control of movement adds one more domain: human neuroscience now uses the filter as a realistic model of how the brain estimates the current state of the motor system and issues updated commands, accounting for the time delay between motor commands and sensory feedback.