Fast Kalman filter

The fast Kalman filter (FKF), devised by Antti Lange (1941- ), is an extension of the Helmert-Wolf blocking (HWB) method from geodesy to safety-critical real-time applications of Kalman filtering (KF) such as GNSS navigation up to the centimeter-level of accuracy and satellite imaging of the Earth including atmospheric tomography.

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 generally optimal for many systems. However, an optimal Kalman filter is not stable (i.e. reliable) if Kalman's observability and controllability conditions are not continuously satisfied (Kalman, 1960). These conditions are very challenging to maintain for any larger system. This means that even optimal Kalman filters may start diverging towards false solutions. Fortunately, the stability of an optimal Kalman filter can be controlled by monitoring its error variances if only these can be reliably estimated (e.g. by MINQUE) . Their precise computation is, however, much more demanding than the optimal Kalman filtering itself. The FKF computing method often provides 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. This number 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. However, for any large and complex system this pre-filtering may need the HWB computing. Any continued use of a too narrow window of input data weakens observability of the calibration parameters and, in the long run, this may lead to serious controllability problems totally unacceptable in safety-critical applications.

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

Reliable solution

Reliable operational Kalman filtering requires continuous fusion of data in real-time. Its optimality depends essentially on the use of exact 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 the estimated parameters can be computed by using the HWB (and FKF) method. The optimal solution may also be obtained by Gauss elimination using other sparse-matrix techniques or some iterative methods based e.g. on Variational Calculus. However, these latter methods may solve the large matrix of all the error variances and covariances only approximately and the data fusion would not be performed in a strictly optimal fashion. Consequently, the long-term stability of Kalman filtering becomes uncertain even if Kalman's observability and controllability conditions were permanently 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 this optimal fast Kalman filtering (Lange, 2015).

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 are missing (observability problem) or an unpredictable change of weather is taking place (controllability problem). Remote sensing and imaging from satellites are partly based on forecasted information. Controlling stability of such feedback between these forecasts and the satellite images calls for the theory of optimal Kalman filtering. No suboptimal solution would do a proper job as the public safety is here at stake.

The computational advantage of FKF is marginal for applications using only small amounts of data in real-time. 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.

References

• Lange, A. A. (2015): "Using Helmert-Wolf blocking for diagnosis & treatment of GNSS errors", Technical Paper ITS-1636, Bordeaux, 22nd ITS World Congress, 5-9 October 2015.
• 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.

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