03/31/03 12.540 Lec 13 1 12.540 Principles of the Global Positioning System Lecture 13 Prof. Thomas Herring 03/31/03 12.540 Lec 13 2 – First-order Gauss Markov Processes – to be estimated are changing with time Estimation ? Summary Kalman filters – Estimation in which the parameters 1 ? ? 03/31/03 12.540 Lec 13 3 Specific common processes j xx (t) = s 2 e - F xx (w) = 2bs 2 w 2 + b 2 1 b is correlation time ? White-noise: Autocorrelation is Dirac-delta function; PSD is flat; integral of power under PSD is variance of process (true in general) ? First-order Gauss-Markov process (one of most models common in Kalman filtering) b t 03/31/03 12.540 Lec 13 4 Other characteristics of FOGM dx dt x(t)b + w(t) x(t t) = e -Dtb x(t) + e -Dtb e ub w(t + u)du 0 Dt ú 1 2 3 Variance over interval T s T 2 (T) = s 2 1 + (1 - e -2Tb ) 2Tb ê ? á ? ˉ ? Variance of change in t D(t) = 2s 2 1- e - t b ( ) w(t s 2 /(2b) Excitation function = - Solution + D White Noise Excitation 444 444 White noise, ), variance = F 2 03/31/03 12.540 Lec 13 5 Characteristics of FOGM ? This process noise model is very useful because as b, inverse correlation time, goes to infinity (zero correlation time), the process is white noise ? When the correlation time goes to infinity (b process becomes random walk (ie, sum of white noise). ? NOTE: Random walk is not a stationary process because its variance tends to infinity as time goes to infinity ? In the FOGM solution equation, note the damping term e -Dtb x which keeps the process bounded 03/31/03 12.540 Lec 13 6 Formulation of Kalman filter measurements. deterministic. –>0), ? A Kalman filter is an implementation of a Bayes estimator. ? Basic concept behind filter is that some of the parameters being estimated are random processes and as data are added to the filter, the parameter estimates depend on new data and the changes in the process noise between ? Parameters with no process noise are called 3 ? ? 03/31/03 12.540 Lec 13 7 properties. y t = A t x t + v t x t +1 = S t x t + w t < v t v t T >= V t < w t w t T >= W t Formulation ? For a Kalman filter, you have measurements y(t) with noise v(t) and a state vector (parameter list) which have specified statistical Observation equation at time t State transition equation Covariance matrices 4 03/31/03 12.540 Lec 13 8 Basic Kalman filter steps steps – data ?x t +1 t = S t ?x t t S t C t +1 t = S t C t t S t T + W t W t ? Kalman filter can be broken into three basic ? Prediction: Using process noise model, “predict” parameters at next data epoch Subscript is time quantity refers to, superscript is is state transition matrix is process noise covariance matrix ? 03/31/03 12.540 Lec 13 9 Prediction step ? The state transition matrix S projects state vector (parameters) forward to next time. Dt][0 1] -Dtb ? The second equation projects the covariance matrix of the state vector , C, forward in time. Contributions from state transition and process noise (W matrix). W elements are 0 for deterministic parameters – For random walks: S=1 – For rate terms: S is matrix [1 – For FOGM: S=e – For white noise S=0 5 03/31/03 12.540 Lec 13 10 Kalman Gain K = C t +1 t A t +1 T V t +1 + A t +1 C t +1 t A t +1 T ( ) -1 ? The Kalman Gain is the matrix that allocates the differences between the observations at time t+1 and their predicted value at this time based on the current values of the state vector according to the noise in the measurements and the state vector noise ? 03/31/03 12.540 Lec 13 11 Update step ? the filter and the covariance matrix of the state vector is updated. ? The filter has now been updated to time t+1 and measurements from t+2 can added and so on until all the observations have been added. ?x t +1 t +1 = ?x t +1 t + K(y t +1 - A t +1 ?x t +1 t ) C t +1 t +1 = C t +1 t - KA t +1 C t +1 t Step in which the new observations are “blended” into 03/31/03 12.540 Lec 13 12 Aspects to note about Kalman Filters ? How is the filter started? Need to start with an apriori state vector covariance matrix (basically at time 0) ? Notice in updating the state covariance matrix. C, that at each step the matrix is decremented. If the initial covariances are too large, then significant rounding (variance 10 10 mm apriori and data determines to 1 mm, then C digits). ? Square-root-information filters overcome this problem filter. error in calculation eg. If position assumed ±100 m is decremented by 10 orders of magnitude (double precision has on 12 significant but usually take longer to run than a standard Kalman 6 ? 03/31/03 12.540 Lec 13 13 “Smoothing” filters ? In a standard Kalman filters, the stochastic parameters obtained during the filter run are not optimum because they do not contain information about the deterministic parameters obtained from future data. ? A smoothing Kalman filter, runs the filter forwards (FRF) and backwards in time (BRF), taking the full average of the forward filter at the update step with the backwards filter at the prediction step. 7 03/31/03 12.540 Lec 13 14 Smoothing filters B = C + (C + + C - ) -1 C + from FRF, C - from BRF ?x t s = ?x + + B( ?x - - ?x + ) Smoothed state vector estimate C t s = C + - BC - Smoothed estimate covariance matrix ? The derivation of the full average can be derived from the filter equations. ? The smoothing filter is Smoothing Kalman Gain 03/31/03 12.540 Lec 13 15 03/31/03 12.540 Lec 13 16 Note on apriori constraints ? In Kalman filter, apriori covariances must be applied to all parameters, but cannot be too large or else large matrices). ? Error due to apriori constraints given approximately by (derived from filter equations). ? Approximate formulas assuming uncorrelated parameter estimates and the apriori variance is large can be determined. Properties of smoothing filter ? Deterministic parameters (ie., no process noise) should remain constant with constant variance in smoothed results. ? Solution takes about 2.5 times longer to run than just a forward filter ? If deterministic parameters are of interest only, then just FRF needed. rounding errors (non-positive definite covariance compared to intrinsic variance with which parameter 8 ? 03/31/03 12.540 Lec 13 17 Errors due to apriori constraints D?x a s 2 s 0 2 (x 0 - ?x) D ?x (x 0 - ?x); s 0 2 s 2 s 2 s 0 2 1 a s 4 s 0 2 to apriori variance is error in estimates due to error in apriori is apriori variance, is variance of estimate. is assumed << Error in variance estimate is Note: Error depends on ratio of aposteriori to apriori variance rather than absolute magnitude of error in apriori 03/31/03 12.540 Lec 13 18 ? In Kalman filters, apriori constraints must be given for all parameters; not needed in weighted least squares (although can be done). ? Kalman filters allow zero variance parameters; can not be done is WLS since inverse of constraint matrix needed ? Kalman filters allow zero variance data; can not be done in WLS ? Kalman filters allow method for applying absolute constraints; can only be tightly constrained in WLS ? In general, Kalman filters are more prone to numerical stability problems and take longer to run (strictly many more parameters). ? Process noise models can be implemented in WLS but very slow. Contrast between WLS and Kalman Filter again due to inverse of data covariance matrix. 9 03/31/03 12.540 Lec 13 19 Applications in GPS application ? Most handheld GPS receivers use Kalman filters to estimate velocity and position as function of time. ? Clock behaviors are “white noise” and can be treated with Kalman filter ? Atmospheric delay variations ideal for filter ? Stochastic variations in satellite orbits 10