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