Editing Fast Kalman filter

The '''fast Kalman filter (FKF)''', devised by Antti Lange (born 1941), is an extension of the [[Helmert–Wolf blocking]]<ref name="fn_1">{{cite tech report|title=Making Combined Adjustments [GPScom Software Documentation]|institution=Geoscience Research Division of NOAA|url=https://www.ngs.noaa.gov/GRD/GPS/DOC/gpscom/mca.html}}</ref> (HWB) method from [[geodesy]] to safety-critical real-time applications of [[Kalman filter|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 filtering technique for building fault-tolerance into a wide range of systems, including real-time imaging.
The ordinary Kalman filter is an optimal filtering algorithm for linear systems. However, an optimal Kalman filter is not stable (i.e. reliable) if Kalman's [[observability]] and [[controllability]] conditions are not continuously satisfied.<ref>{{cite journal|last1=Kalman|first1=Rudolf|title=A New Approach to Linear Filtering and Prediction Problems|doi=10.1115/1.3662552|pages=34–45|volume=82|issue=1|journal=Journal of Basic Engineering|year=1960}}</ref> 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|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.<ref>{{cite journal|last1=Lange|first1=Antti|title=Statistical Calibration of Observing Systems|pages=34–45|volume=22|journal=Finnish Meteorological Institute Contributions|date=2008|url=http://personal.fimnet.fi/business/terhikki.lange/thesis.pdf}}</ref> Observing instruments onboard orbiting satellites gives an example of optimal Kalman filtering where their calibration is done indirectly on ground.<ref>{{cite report|last1=Jacobsson |first1=B|last2=Nylund|first2=M|last3=Olssoon|first3=T|last4=Vandermarcq|first4=O|last5=Vinterhav|first5=E|title=Star Tracker/Gyro Calibration and Attitude Reconstruction for the Scientific Satellite Odin - In Flight Results|date=2001|url=http://www.ssc.se:80/data/content/DOCUMENTS/20049612942476Star%20Tracker,%20Gyro%20Calibration%20and%20Attitude%20Reconstruction.pdf|archive-url=https://web.archive.org/web/20070111070733/http://www.ssc.se:80/data/content/DOCUMENTS/20049612942476Star%20Tracker,%20Gyro%20Calibration%20and%20Attitude%20Reconstruction.pdf|archive-date=11 January 2007|archive-format=PDF}}</ref> There may also exist other state parameters that are hardly or not at all observable if too small samples of data are processed at a time by any sort of a Kalman filter.

=== Inverse problem ===
The computing load of the [[inverse problem]] of an ordinary<ref>{{cite journal|last1=Lange|first1=Antti|title=Statistical Calibration of Observing Systems|pages=12–13|volume=22|journal=Finnish Meteorological Institute Contributions|date=2008|url=http://personal.fimnet.fi/business/terhikki.lange/thesis.pdf}}</ref> Kalman recursion is [[Cholesky decomposition#Computing the Cholesky decomposition|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,<ref>{{cite journal|first1=Elmar|last1=Brockman|date=1997|language=gsw|title=Combination of Solutions for Geodetic and Geodynamic Applications of the Global Positioning System (GPS)|url=https://www.sgc.ethz.ch/sgc-volumes/sgk-55.pdf|volume=55|journal=Geodaetisch-geophysikalische Arbeiten in der Schweiz}}</ref> 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 [[Linear regression#Multiple linear regression|Normal Equations]].<ref name="fn_4">{{cite book|last1=Strange|first1=Gilbert|last2=Borre|first2=Borre|date=1997|title=Linear Algebra, Geodesy, and GPS|publisher=Wellesley-Cambridge Press|isbn=978-0961408862|pages=507–508}}</ref> 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.<ref name="fn_4" /> The optimal solution may also be obtained by Gauss elimination using other sparse-matrix techniques or some iterative methods based e.g. on [[Calculus of variations|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,<ref>{{cite journal|first=Antti|last=Lange|doi=10.1016/S1464-1895(01)00086-2|journal=Physics and Chemistry of the Earth, Part A: Solid Earth and Geodesy|volume=26|issue=6–8|pages=471–473|date=2001|issn=1464-1895|publisher=Elsevier Science|title=Simultaneous Statistical Calibration of the GPS signal delay measurements with related meteorological data|location=Amsterdam|language=en}}</ref> 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 generalized Canonical Correlation Analysis [[Generalized canonical correlation|(gCCA)]].

Such a large matrix can thus be most effectively inverted in a blockwise manner by using the following 
[[Invertible matrix#Blockwise inversion|analytic inversion formula]]:
:<math>\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}</math>
of [[Ferdinand Georg Frobenius|Frobenius]] where 
:<math> A = </math> a large block- or band-diagonal (BD) matrix to be easily inverted, and,
:<math> (D-CA^{-1}B) = </math> a much smaller matrix called the [[Issai Schur|Schur]] complement of <math>A</math>.

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]] and used for controlling the stability of this optimal fast Kalman filtering.<ref>{{cite report|first=Antti|last=Lange|title=Using Helmert–Wolf blocking for diagnosis & treatment of GNSS errors|date=9 October 2015|publisher=22nd ITS World Congress|docket=Technical PAper ITS-1636|location=Bordeaux|url=http://www.fkf.net/World-ITS-2015-Lange.pdf}}</ref>

== 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.<ref>{{cite conference|url=http://www.fkf.net/LangeA2003.PDF|title=Optimal Kalman Filtering for ultra-reliable Tracking|first=Antti|last=Lange|date=15 October 2003|location= Matera, Italy|conference=Atmospheric Remote Sensing using Satellite Navigation Systems}}</ref> First important applications will be real-time optimum calibration of global observing systems in Meteorology,<ref name="fn_6">{{cite conference|url=https://www.fkf.net/paper1.pdf|title=A high-pass filter for Optimum Calibration of observing systems with applications|first=Antti|last=Lange|date=1988|conference=Simulation and Optimization of Large Systems|editor=Andrez J. Osiadacz|pages=311–327|publisher=Oxford University Press/Clarendon Press|location=Oxford}}</ref> Geophysics, Astronomy etc.

For example, a [[Numerical weather prediction|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 the feedback between these forecasts and the satellite images requires a sensor fusion technique that is both fast and robust, which the FKF fulfills.

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 devices can make the best out of FKF.

== References ==
{{Reflist}}

== External links ==
* [http://portal.acm.org/citation.cfm?id=200979.200987 BBD] - software
* [http://www.fkf.net/FKFformula.html FKF] - formulas
* [http://www.fkf.net/Wolf.html HWB] - formulas
* [http://www.fkf.net/Langesformula.html The error covariance matrix of FKF] - formulas
* There are other Fast Kalman Algorithms designed for special signal processing purposes, see e.g. [https://ieeexplore.ieee.org/xpl/abs_free.jsp?arNumber=31289 Stabilizing the Fast Kalman Algorithms] on IEEE Xplore
*[http://portal.acm.org/citation.cfm?id=982359  Kalman filter recipes for real-time image processing]

{{DEFAULTSORT:Fast Kalman Filter}}
[[Category:Signal estimation]]
[[Category:Linear filters]]