PaperlayerView exact revision on arXiv

Source-linked AI summary

An Elementary Introduction to Kalman Filtering

Yan Pei, Swarnendu Biswas, Donald S. Fussell, Keshav Pingali

arXiv:1710.04055v5eess.SYcs.SY

TL;DR

Existing introductions often focus on particular applications, making Kalman filtering’s general principles harder to see. The paper derives its linear-system treatment from elementary estimation ideas. It reports that scalar estimates should be weighted inversely to their variance and can be fused incrementally without loss in final quality.

  • Problem

    Many introductions focus on particular applications, making it difficult to see how Kalman filtering applies to other problems.

    Source: §1 · p. 1

  • Method

    The paper derives linear-system Kalman filtering from optimal linear estimators for fusing uncorrelated estimates and best linear unbiased estimators for correlated variables.

    Source: §6.5 · p. 10

  • Results

    Each scalar estimate’s weight should be inversely proportional to its variance, and multiple estimates can be fused incrementally without loss in final quality.

    Source: §3.4 · p. 5

  • Takeaways & Limitations

    Making the assumptions behind optimality explicit should make it easier to apply Kalman filtering to problems in computer systems.

    Source: §8 · p. 12

    The paper establishes that its linear estimator matches any unbiased nonlinear estimator when the noise is Gaussian.

    Source: §6.5 · p. 11

Abstract

from arXiv · show

Kalman filtering is a classic state estimation technique used in application areas such as signal processing and autonomous control of vehicles. It is now being used to solve problems in computer systems such as controlling the voltage and frequency of processors. Although there are many presentations of Kalman filtering in the literature, they usually deal with particular systems like autonomous robots or linear systems with Gaussian noise, which makes it difficult to understand the general principles behind Kalman filtering. In this paper, we first present the abstract ideas behind Kalman filtering at a level accessible to anyone with a basic knowledge of probability theory and calculus, and then show how these concepts can be applied to the particular problem of state estimation in linear systems. This separation of concepts from applications should make it easier to understand Kalman filtering and to apply it to other problems in computer systems.

1 INTRODUCTION

Existing introductions often focus on particular applications, making Kalman filtering’s general principles harder to see. This paper presents its abstract concepts and clarifies their assumptions before applying them to linear-system state estimation.

1 INTRODUCTION

  • Many existing introductions focus on particular applications, making it difficult to see how Kalman filtering applies to other problems.The paper also notes that Bayesian presentations can foster the misconception that Kalman filtering requires Gaussian noise.Source: §1 · p. 1
  • The paper separates general Kalman-filtering concepts and their assumptions from an application to state estimation in linear systems.It aims to make the concepts accessible to computer scientists and support application to other computer-systems problems.Source: §1 · pp. 1–2
  • The paper frames Kalman filtering as combining approximations of an unknown value, illustrated by fusing two noisy CPU-temperature measurements.The measurements come from differently designed devices whose noise is assumed to affect them in unrelated ways.Source: §1 · p. 1
  • A weighted sum is a linear estimator, but discarding a lower-confidence measurement is generally not optimal because that measurement can still provide useful information.The optimal weights depend on the confidence in each device.Source: §1 · p. 1
  • The paper asks how to fuse estimates optimally, then develops scalar fusion, vector fusion, and BLUE-based estimation from partial observations.It also identifies applying these ideas to linear systems and briefly discussing nonlinear extensions.Source: §1 · p. 2

2 FORMALIZATION OF ESTIMATES

The section formalizes estimates using probability distributions, means, variances, and covariance, then extends scalar reasoning to vector estimates. It treats unbiasedness and variance as criteria for estimator quality.

2.1 Scalar estimates

  • Each measurement device is modeled by a random variable sampled from its probability density function, which need not be Gaussian.The distribution’s mean and variance represent the device’s expected measurement and variability.Source: §2.1 · p. 2
  • A distribution mean different from ground truth represents systematic error, while variance measures random error that repeated averaging can reduce.Figure 1 marks the 60 °C ground truth and uses dashed lines for distribution means.Source: §2.1 · p. 2, Figure 1 · p. 2
  • For single measurements, confidence is modeled by variance: smaller variance means greater confidence, under the usual no-systematic-error assumption.The first device’s broader distribution in Figure 1 illustrates its larger variance.Source: §2.1 · p. 2, Figure 1 · p. 2
  • Uncorrelated measurements need not be independent; uncorrelatedness requires their covariance to be zero and their conditional mean to remain unchanged.The paper uses this weaker condition to formalize noise affecting devices in unrelated ways.Source: §2.1 · pp. 2–3
  • The paper considers only unbiased estimators, preferring lower variance at equal bias and using variance as scalar mean square error.The same mean-and-variance reasoning applies to estimates produced by an estimator.Source: §2.1 · p. 3

2.2 Vector estimates

  • For vector estimates, covariance matrices encode component variances and covariances, while cross-covariance describes dependence between two random vectors.Vectors are represented with bold lowercase letters and matrices with uppercase letters.Source: §2.2 · p. 3
  • Lemma 2.2 extends linear-combination mean and covariance reasoning to pairwise uncorrelated random vectors and preserves uncorrelatedness with another vector.It generalizes the corresponding scalar result.Source: §2.2 · p. 3
  • For an unbiased vector estimator, mean square error is the sum of component variances, equivalently the trace of its covariance matrix.For a scalar estimate, this reduces to variance.Source: §2.2 · p. 3

3 FUSING SCALAR ESTIMATES

Scalar estimates can be fused optimally by weighting them according to their confidence, and multiple estimates can be fused incrementally without reducing the quality of the final estimate.

3.1 Fusing two scalar estimates

  • For two uncorrelated scalar estimates, minimum-variance linear fusion weights each estimate in proportion to its precision, using variances alone without requiring equal means.The optimal value of α is called the Kalman gain K.Source: §3.1 · p. 4

3.2 Fusing multiple scalar estimates

  • For n pairwise uncorrelated scalar estimates, variance-minimizing linear weights sum to one and are proportional to inverse variance, or precision.The contribution of each estimate to the fused value is proportional to its confidence.Source: §3.2 · pp. 4–5

3.3 Incremental fusing is optimal

  • Fusing n>2 scalar estimates sequentially through a running estimate preserves the same optimal final estimate as batch fusion.The paper shows that each input’s path-weight product in the incremental process equals its weight in the batch estimator.Source: §3.3 · p. 5

3.4 Summary

  • The summary states that weights are inversely proportional to variance: as ν1≫ν2, K≈0 and fusion approaches x1; as ν1≪ν2, K≈1 and fusion approaches x2.Source: §3.4 · p. 5

4 FUSING VECTOR ESTIMATES

Vector fusion extends scalar fusion by replacing variances with covariance matrices. The paper also presents the vector Kalman gain and states that multiple vector estimates can be fused incrementally without loss of precision.

4 FUSING VECTOR ESTIMATES

  • Vector fusion extends the scalar results by replacing variances with covariance matrices.Source: §4 · p. 5

4.1 Fusing multiple vector estimates

  • For pairwise uncorrelated vector estimates, the optimal linear fusion minimizes MSE under sum Ai=I; covariance matrices take the role of scalar variances, and precision is their inverse.Source: §4.1 · pp. 5–6

4.2 Summary

  • The vector summary expresses the two-estimate update through Kalman gain K, and multiple vector estimates can be fused incrementally without loss of precision.Source: §4.2 · p. 6, §4.1 · p. 6

5 BEST LINEAR UNBIASED ESTIMATOR (BLUE)

When only part of a state is observable, BLUE estimates the hidden part from the visible part. It fits an unknown linear relationship between random variables, choosing an unbiased estimator with minimal mean squared error.

5 BEST LINEAR UNBIASED ESTIMATOR (BLUE)

  • BLUE estimates a hidden state component from the measured component when only part of the state is observable.It assumes a linear relationship between the observable and hidden parts of the state.Source: §5 · p. 6
  • For random variables without a precise functional relationship, the conditional mean could estimate y from x, but requires their joint distribution.The confidence ellipse can contain many possible y values for a given x.Source: §5 · p. 6
  • BLUE fits an unknown linear relationship between x and y and estimates y from x, analogously to ordinary least squares.The y values cluster around the BLUE line, making its estimate for a given x reasonable.Source: §5 · p. 6
  • The estimator Ax+b is chosen to be unbiased and to have minimal mean squared error.An unbiased BLUE passes through the point (µx, µy).Source: §5 · p. 7
  • BLUE uses the correlation between x and y to improve the estimate; if they are uncorrelated, the estimate is µy.For a functional relationship y=Cx, BLUE returns Cx; with discrete data, its line matches ordinary least squares.Source: §5 · p. 7

6 KALMAN FILTERS FOR LINEAR SYSTEMS

For linear systems, Kalman filtering alternates model-based prediction with fusion of measurements to update state estimates. Its partial-observation case uses BLUE, and the paper derives the filter from optimal linear estimation ideas while clarifying the conditions behind its optimality.

6 KALMAN FILTERS FOR LINEAR SYSTEMS

  • For a linear system, the state evolves as xt = Ftxt−1 + Btut; imperfect initial state, dynamics, or inputs can make model estimates diverge from reality.The filter predicts from the previous estimate, then fuses that prediction with the measurement to produce the updated estimate for the next step.Source: §6 · p. 7

6.1 State evolution model and prediction

  • Prediction uses the previous a posteriori estimate as a proxy for the previous state to compute the a priori estimate.The model includes deterministic control input and zero-mean noise; the covariance calculation assumes the noise is uncorrelated with the previous estimate.Source: §6.1 · p. 8

6.2 Fusing complete observations of the state

  • With complete observations, the filter fuses the a priori estimate and measurement when they are uncorrelated.The measurement model includes zero-mean noise with covariance Rt, uncorrelated across time and with the state-estimation noises.Source: §6.2 · p. 9

6.3 Fusing partial observations of the state

  • With partial observations, BLUE updates the hidden state using its covariance with the measured state and the measurement innovation.The observable and hidden posterior estimates are then composed into the full state estimate; this linear unbiased estimator is optimal.Source: §6.3 · pp. 9–10

6.4 Example: falling body

  • In the falling-body example, posterior estimates track the ground truth despite noisy velocity measurements and an inaccurate ideal model.The example assumes velocity measurements with Gaussian noise of variance 8; filtering rapidly reduces the initially large velocity variance.Source: §6.4 · p. 10

6.5 Discussion

  • The linear-system filter follows from optimal fusion of uncorrelated estimates and BLUE for correlated variables, exposing its assumptions.If noise is Gaussian, the linear estimator is as good as any unbiased nonlinear estimator; without Gaussian noise, a nonlinear estimator may have lower MSE.Source: §6.5 · pp. 10–11

7 EXTENSION TO NONLINEAR SYSTEMS

For nonlinear systems, the paper describes EKF and UKF as heuristic extensions of Kalman filtering. EKF linearizes the system and measurement functions; UKF propagates sampled points through nonlinear functions to approximate posterior statistics.

7 EXTENSION TO NONLINEAR SYSTEMS

  • For nonlinear systems with additive noise, EKF and UKF are heuristic approaches to applying Kalman filtering.The state evolution and measurement equations use nonlinear functions f and h.Source: §7 · p. 11
  • EKF linearizes the nonlinear state and measurement functions using Taylor expansions to compute covariance matrices.The resulting Jacobians play the roles of the linear-system matrices Ft and Ht; EKF performs well in some navigation and GPS applications.Source: §7 · p. 11
  • UKF propagates carefully chosen sigma points through nonlinear functions and estimates posterior statistics with weighted means and covariances.It tends to be more robust and accurate than EKF, but has higher computation overhead due to sampling.Source: §7 · p. 11

8 CONCLUSION

The paper derives Kalman filtering from two concepts: optimal linear fusion of uncorrelated estimates and BLUE for correlated variables. This intuitive derivation clarifies the assumptions behind optimality and is intended to make application to computer-system problems easier.

8 CONCLUSION

  • Optimal linear fusion of uncorrelated estimates and BLUE for correlated variables provide the underpinnings for Kalman filtering.Combining these ideas derives standard linear-system results in an intuitive, straightforward way.Source: §8 · p. 11
  • The derivation clarifies the assumptions behind Kalman filtering’s optimality results and should make application to computer-system problems easier.The paper presents the derivation as simpler than other presentations of the material.Source: §8 · pp. 11–12

A BASIC PROBABILITY THEORY AND STATISTICS TERMINOLOGY

The appendix defines probability and statistics terms used to describe random variables and their relationships. It also introduces matrix derivatives as a tool for the paper’s proofs.

A BASIC PROBABILITY THEORY AND STATISTICS TERMINOLOGY

B MATRIX DERIVATIVES

  • A matrix derivative arranges the partial derivatives of a scalar function with respect to each matrix entry.Source: B MATRIX DERIVATIVES · p. 13

C PROOF OF THEOREM 4.1

The theorem gives the minimum-MSE linear fusion of pairwise uncorrelated estimates under a constraint that the estimator matrices sum to the identity. Its proof uses matrix Lagrange multipliers to preserve the problem’s matrix structure.

C PROOF OF THEOREM 4.1

  • For pairwise uncorrelated estimates, the theorem minimizes MSE for a linear estimator whose coefficient matrices sum to the identity.Source: C PROOF OF THEOREM 4.1 · p. 13
  • The proof encodes the matrix constraint with a matrix of Lagrange multipliers, avoiding a scalar-by-scalar formulation that obscures matrix structure.Source: C PROOF OF THEOREM 4.1 · pp. 13–14
  • Setting the derivatives with respect to the coefficient matrices to zero and applying the sum-to-identity constraint yields the minimizing coefficients.Source: C PROOF OF THEOREM 4.1 · p. 14

D PROOF OF THE OPTIMALITY OF EQUATION 40

The proof establishes that Equation 40 is an optimal unbiased linear estimator for combining the prior state estimate with each measurement. It first verifies unbiasedness, then shows the gain minimizes the estimation error under the stated conditions.

D PROOF OF THE OPTIMALITY OF EQUATION 40

Loading 1710.04055v5…