Fast Kalman filter

From Wikipedia, the free encyclopedia

The fast Kalman filter (FKF), devised by Antti Lange (1941- ), is an extension of the Helmert-Wolf blocking¹ (HWB) method from geodesy to real-time applications of Kalman filtering (KF) such as satellite imaging of the Earth. Kalman filters are an important software technique for building fault-tolerance into a wide range of systems, including real-time imaging.

[edit] 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 ordinary Kalman filter is optimal for general systems. However, an optimal Kalman filter is provenly stable only if Kalman's observability² and controllability conditions³ are also satisfied (Kalman, 1960). These conditions are most tricky to be continuously maintained 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.

[edit] 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.

[edit] Inverse problem

The computing load of the inverse problem of an ordinary Kalman recursion is roughly proportional to the cubic of the number of the measurements and this number is therefore very limited. The use of a broad data window leads to a larger system of equations which increases the number of the state parameters to be estimated. This is commonly known as filter training and it is done either initially or temporarily for stabilizing the ordinary Kalman filter. HWB initially or FKF temporarily may serve as the method of choice for this purpose.

For the sake of sufficient overdetermination (i.e. Kalman's observability condition), the number of the measurements should generally be much larger than the number of all the state parameters to be estimated at a time. Fortunately, the linear equation system for a broad data window is sparse as some measurements are entirely independent of some state or calibration parameters. Thus, very high accuracies are achieved in Satellite Geodesy (Brockmann, 1997) because the computing load of the HWB (and FKF) inversion 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).

[edit] Reliable solution

Ultra-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⁴. Its coefficient matrix is usually sparse and the exact solution of all estimated parameters can be computed by using the HWB method⁵. 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.

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). The large matrix can thus be most effectively inverted in a blockwise manner by using the following analytic inversion formula:

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.

[edit] 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⁶, 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 forecasted 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.

[edit] Notes

• Note 1: see GPScom Software Documentation from Geoscience Research Division of NOAA.

• Note 2: see the observability condition of a Kalman filter as described by Dr. Hongxing Xia of George Mason University.

• Note 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.

• Note 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.

• Note 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.

• Note 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.

[edit] References

Brockmann, E. (1997): "Combination of solutions for geodetic and geodynamic applications of the Global Positioning System (GPS)", Geodätisch - geophysikalische Arbeiten in der Schweiz, Volume 55, Schweitzerische Geodätische Kommission.

Kalman, R. E. (1960): "A New Approach to Linear Filtering and Prediction Problems", Transactions of the ASME - Journal of Basic Engineering, Vol. 82: pp. 35-45.

Lange, A. A. (1999): "Statistical Calibration of Observing Systems", Academic Dissertation, Finnish Meteorological Institute Contributions, No. 22, Helsinki, Finland.

Lange, A. A. (2001): "Simultaneous Statistical Calibration of the GPS signal delay measurements with related meteorological data", Physics and Chemistry of the Earth, Part A: Solid Earth and Geodesy, Vol. 26, No. 6-8, pp. 471-473.

Lange, A. A. (2003): "Optimal Kalman Filtering for ultra-reliable Tracking", ESA CD-ROM WPP-237, Atmospheric Remote Sensing using Satellite Navigation Systems, Special Symposium of the URSI Joint Working Group FG, 13-15 October 2003, Matera, Italy.

Olsson, T. et al. (2001): "Star Tracker/Gyro Calibration and Attitude Reconstruction for the Scientific Satellite ODIN - In Flight Results."

Wolf, H. (1978): "The Helmert block method, its origin and development", Proceedings of the Second International Symposium on Problems Related to the Redefinition of North American Geodetic Networks, Arlington, Va. April 24-28, pp. 319-326.

[edit] External links

• BBD - software
• FKF - formulas
• HWB - formulas
• The error covariance matrix of FKF - formulas
• There are other Fast Kalman Algorithms designed for special signal processing purposes, see e.g. Stabilizing the Fast Kalman Algorithms on IEEE Xplore
• Kalman filter recipes for real-time image processing