FACTOID # 6: Michigan is ranked 22nd in land area, but since 41.27% of the state is composed of water, it jumps to 11th place in total area.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Fast Kalman filter


The fast Kalman filter (FKF) of Antti Lange (1941- ) is an extension of the Helmert-Wolf blocking1 (HWB) method from Geodesy to real-time applications of Kalman filtering (KF). The FKF 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 observability2 and controllability conditions3 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 filtering itself. Antti Lange (born December 11, 1941 in Helsinki, Finland) is a Finnish mathematician and statistician of the Finnish Meteorological Institute. ... This article contains information that is not verifiable. ... It has been suggested that geodetic system be merged into this article or section. ... The Kalman filter is an efficient recursive filter which estimates the state of a dynamic system from a series of incomplete and noisy measurements. ...

Contents


Optimum calibration

Calibration parameters are a typical example of those state parameters that may create serious observability problems if a short data window (i.e. too small number of measurements) is continously 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 cubic of the number of the measurements and this number is therefore very limited. The use of a larger 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. The inverse problem is the task that often occurs in many branches of science and mathematics where the values of some model parameter(s) must be obtained via manipulation of observed data. ... In mathematics, the Cholesky decomposition, named after André-Louis Cholesky, is a matrix decomposition of a symmetric positive-definite matrix into a lower triangular matrix and the transpose of the lower triangular matrix. ...


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 larger data window is sparse as some measurements become 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).


Reliable solution

Ultra-reliable operational Kalman filtering requires continuous fusion of real-time data where its optimality crucially depends on the full use of all error variances and covariances of the measurements and estimated state and calibration parameters. This error covariance matrix must be derived by a matrix inversion from the respective large system of Normal Equations4. Its coefficient matrix is usually sparse and an exact solution of the estimated state parameters can be obtained by using the HWB method5. The same solution may often be computed also by Gauss elimination using sparse-matrix techniques or some iterative methods. However, these latter methods do not solve error variances and covariances of the state parameters. It would then be impossible to combine information on recursive state estimates in an optimal fashion for a Kalman filter. Consequently, the stability of such suboptimal Kalman filtering may severely suffer even though the observability and controllability conditions were satisfied. It has been suggested that this article or section be merged with invertible matrix. ... In statistics, linear regression is a method of estimating the conditional expected value of one variable y given the values of some other variable or variables x. ...


Fortunately, the large coefficient matrix to be inverted has a bordered block- or band-diagonal (BBD) structure. It can thus be blockwisely inverted by using the following analytic inversion formula: It has been suggested that this article or section be merged with invertible matrix. ...

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 Picture of Frobenius Ferdinand Georg Frobenius (October 26, 1849 - August 3, 1917) was a German mathematician, best-known for his contributions to the theory of differential equations and to group theory. ...

A = a large block- or band-diagonal (BD) matrix, and,
(DCA − 1B) = 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 filter can do. Their operational accuracies can then 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. Issai Schur (January 10, 1875 in Mogilyov - January 10, 1941 in Tel Aviv) was a mathematician who worked in Germany for most of his life. ... In statistics, the theory of minimum norm quadratic unbiased estimation (MINQUE) was developed by C.R. Rao. ... Calyampudi Radhakrishnan Rao (born September 10, 1920) is a famous Indian statistician and currently professor emeritus at Penn State University. ...


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 Meteorology6, Geophysics, Astronomy etc. Real Time Kinematic (RTK) land survey is based on a differential use of carrier phase measurements of the GPS, Glonass and/or Galileo signals where a single reference station provides the real-time corrections of even to a centimetre level of accuracy. ...


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 an important observation was missing from somewhere or an unpredicted change of weather is taking place. Remote sensing from satellites is partly based on forecasted information. Control of the stability of this feedback between those forecasts and the satellite observations calls for optimal Kalman filtering. No suboptimal solution would do the job properly as public security is at stake.


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


Notes

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

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.


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

  Results from FactBites:
 
Kalman filter - Wikipedia, the free encyclopedia (2458 words)
The Kalman filter is an efficient recursive filter which estimates the state of a dynamic system from a series of incomplete and noisy measurements.
The Kalman filter exploits the dynamics of the target, which govern its time evolution, to remove the effects of the noise and get a good estimate of the location of the target at the present time (filtering), at a future time (prediction), or at a time in the past (interpolation or smoothing).
It was during a visit of Kalman to the NASA Ames Research Center that he saw the applicability of his ideas to the problem of trajectory estimation for the Apollo program, leading to its incorporation in the Apollo navigation computer.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m