Fast Kalman filter

The fast Kalman filter (FKF), devised by Antti Lange (1941- ), is an extension of the Helmert-Wolf blocking[1] (HWB) method from geodesy to real-time applications of Kalman filtering (KF) such as satellite imaging of the Earth.

Motivation

Kalman filters are an important software technique for building fault-tolerance into a wide range of systems, including real-time imaging. The ordinary Kalman filter is optimal for general systems. However, an optimal Kalman filter is probably stable only if Kalman's observability[2] and controllability conditions[3] are also satisfied (Kalman, 1960). These conditions are challenging to continuously maintain for a large system which means that even an optimal Kalman filter may diverge towards false solutions. Fortunately, the stability of an optimal Kalman filter can be controlled by monitoring its error variances if these can be reliably estimated. Their precise computation is, however, much more demanding than the optimal filtering itself but the FKF method may provide the required speed-up also in this respect.

Optimum calibration

Calibration parameters are a typical example of those state parameters that may create serious observability problems if a narrow window of data (i.e. too few measurements) is continuously used by a Kalman filter (Lange, 1999). Observing instruments onboard orbiting satellites gives an example of optimal Kalman filtering where their calibration is done indirectly on ground (Olsson el al, 2001). There may also exist other state parameters that are hardly or not at all observable (estimable) if too small samples of data are processed (analysed) at a time by any sort of a Kalman filter.

Inverse problem

The computing load of the inverse problem of an ordinary Kalman recursion is roughly proportional to the cube of the number of the measurements processed simultaneously, which can always be set to 1 by processing each scalar measurement independently and (if necessary) performing a simple pre-filtering algorithm to de-correlate these measurements.

Even when many measurements are processed simultaneously, it is not unusual that the linear equation system is sparse, because some measurements turn out to be independent of some state or calibration parameters. In Satellite Geodesy problems (Brockmann, 1997), the computing load of the HWB (and FKF) method is only roughly proportional to the square of the number of the state parameters (and not of the measurements whose number may be billions).

Reliable solution

Reliable operational Kalman filtering requires continuous fusion of data in real-time. Its optimality depends essentially on use of the error variances and covariances between all measurements and the estimated state and calibration parameters. This large error covariance matrix is obtained by matrix inversion from the respective system of Normal Equations.[4] Its coefficient matrix is usually sparse and the exact solution of all estimated parameters can be computed by using the HWB method.[5] The optimal solution may also be obtained by Gauss elimination using other sparse-matrix techniques or iterative methods based e.g. on Variational Calculus. However, these latter methods can solve the large matrix of all error variances and covariances only approximately and it would thus be impossible to do the data fusion in a strictly optimal fashion. Consequently, the filter's stability may become uncertain even if the observability and controllability conditions were satisfied.

Description

The Fast Kalman filter applies only to systems with sparse matrices (Lange, 2001), since HWB is an inversion method to solve sparse linear equations (Wolf, 1978).

The sparse coefficient matrix to be inverted may often have either a bordered block- or band-diagonal (BBD) structure. If it is band-diagonal it can be transformed into a block-diagonal form e.g. by means of a generalised Canonical Correlation Analysis (gCCA).

Such a large matrix can thus be most effectively inverted in a blockwise manner by using the following analytic inversion formula:

\begin{bmatrix} A & B \\ C & D \end{bmatrix}^{-1} = \begin{bmatrix} A^{-1}+A^{-1}B(D-CA^{-1}B)^{-1}CA^{-1} & -A^{-1}B(D-CA^{-1}B)^{-1} \\ -(D-CA^{-1}B)^{-1}CA^{-1} & (D-CA^{-1}B)^{-1} \end{bmatrix}

of Frobenius where

A = a large block- or band-diagonal (BD) matrix to be easily inverted, and,
(D-CA^{-1}B) = a much smaller matrix called the Schur complement of A.

This is the FKF method that may make it computationally possible to estimate a much larger number of state and calibration parameters than an ordinary Kalman recursion can do. Their operational accuracies may also be reliably estimated from the theory of Minimum-Norm Quadratic Unbiased Estimation (MINQUE) of C. R. Rao (1920- ) and used for controlling the stability of optimal Kalman filtering.

Applications

The FKF method extends the very high accuracies of Satellite Geodesy to Virtual Reference Station (VRS) Real Time Kinematic (RTK) surveying, mobile positioning and ultra-reliable navigation (Lange, 2003). First important applications will be real-time optimum calibration of global observing systems in Meteorology,[6] Geophysics, Astronomy etc.

For example, a Numerical Weather Prediction (NWP) system can now forecast observations with confidence intervals and their operational quality control can thus be improved. A sudden increase of uncertainty in predicting observations would indicate that important observations were missing (observability problem) or an unpredictable change of weather is taking place (controllability problem). Remote sensing and imaging from satellites may partly be based on forecast information. Controlling stability of such feedback between the forecast and satellite data calls for the theory of optimal Kalman filtering. No suboptimal solution would do a proper job as public safety is usually at stake.

The computational advantage of FKF is marginal for applications using only small amounts of data in real-time data. Therefore, improved built-in calibration and data communication infrastructures need to be developed first and introduced to public use before personal gadgets and machine-to-machine (M2M) devices can make the best out of FKF.

Notes

  1. ↑ see GPScom Software Documentation from Geoscience Research Division of NOAA.
  2. ↑ see the observability condition of a Kalman filter as described by Dr. Hongxing Xia of George Mason University.
  3. ↑ see the two stability conditions of an optimal Kalman filter as described e.g. by B. Southall, B. F. Buxton, J. A. Marchant (1998): "Controllability and Observability: Tools for Kalman Filter Design", On-Line Proceedings of the Ninth British Machine Vision Conference.
  4. ↑ see formulas (15.56-58) on pages 507-508 of Strang, G. and Borre, K. (1997): Linear Algebra, Geodesy, and GPS, Wellesley-Cambridge Press.
  5. ↑ see the HWB formula (unnumbered) at the end of page 508 of Strang, G. and Borre, K. (1997): Linear Algebra, Geodesy, and GPS, Wellesley-Cambridge Press.
  6. ↑ see Lange, A. A. (1988): "A high-pass filter for Optimum Calibration of observing systems with applications", Simulation and optimization of large systems, edited by Andrzej. J. Osiadacz, Clarendon Press, Oxford, pp. 311-327.

References

External links

This article is issued from Wikipedia - version of the Thursday, October 22, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.