1
KALMAN FILTERS
Simon Haykin
Communications Research Laboratory, McMaster University,
Hamilton, Ontario, Canada
()
1.1 INTRODUCTION
The celebrated Kalman filter, rooted in the state-space formulation of
linear dynamical systems, provides a recursive solution to the linear
optimal filtering problem. It applies to stationary as well as nonstationary
environments. The solution is recursive in that each updated estimate of
the state is computed from the previous estimate and the new input data,
so only the previous estimate requires storage. In addition to eliminating
the need for storing the entire past observed data, the Kalman filter is
computationally more efficient than computing the estimate directly from
the entire past observed data at each step of the filtering process.
In this chapter, we present an introductory treatment of Kalman filters
to pave the way for their application in subsequent chapters of the book.
We have chosen to follow the original paper by Kalman [1] for the
1
Kalman Filtering and Neural Networks, Edited by Simon Haykin
ISBN 0-471-36998-5 # 2001 John Wiley & Sons, Inc.
Kalman Filtering and Neural Networks, Edited by Simon Haykin
Copyright # 2001 John Wiley & Sons, Inc.
ISBNs: 0-471-36998-5 (Hardback); 0-471-22154-6 (Electronic)
derivation; see also the books by Lewis [2] and Grewal and Andrews [3].
The derivation is not only elegant but also highly insightful.
Consider a linear, discrete-time dynamical system described by the
block diagram shown in Figure 1.1. The concept of state is fundamental to
this description. The state vector or simply state, denoted by x
k

is assumed to be additive, white,
and Gaussian, with zero mean and with covariance matrix defined
by
E½w
n
w
T
k
¼
Q
k
for n ¼ k;
0 for n 6¼ k;
&
ð1:2Þ
where the superscript T denotes matrix transposition. The dimension
of the state space is denoted by M.
Figure 1.1 Signal-flow graph representation of a linear, discrete-time
dynamical system.
2
1 KALMAN FILTERS
2. Measurement equation
y
k
¼ H
k
x
k
þ v
k

The Kalman filtering problem, namely, the problem of jointly solving
the process and measurement equations for the unknown state in an
optimum manner may now be formally stated as follows:
 Use the entire observed data, consisting of the vectors y
1
; y
2
; ...; y
k
,
to find for each k ! 1 the minimum mean-square error estimate of
the state x
i
.
The problem is called filtering if i ¼ k, prediction if i > k, and smoothing
if 1 i < k.
1.2 OPTIMUM ESTIMATES
Before proceeding to derive the Kalman filter, we find it useful to review
some concepts basic to optimum estimation. To simplify matters, this
review is presented in the context of scalar random variables; general-
ization of the theory to vector random variables is a straightforward matter.
Suppose we are given the observable
y
k
¼ x
k
þ v
k
;
where x

~
xx
k
defined by
~
xx
k
¼ x
k
À
^
xx
k
:
These two requirements are satisfied by the mean-square error
defined by
J
k
¼ E½ðx
k
À
^
xx
k
Þ
2

¼ E½
~
xx

¼ E½x
k
jy
1
; y
2
; ...; y
k
:
Theorem 1.2 Principle of orthogonality Let the stochastic processes
fx
k
g and fy
k
g be of zero means; that is,
E½x
k
¼E½y
k
¼0 for all k:
Then:
(i) the stochastic process fx
k
g and fy
k
g are jointly Gaussian; or
(ii) if the optimal estimate
^
xx
k

^
xx
À
k
denote a priori estimate of the
state, which is already available at time k. With a linear estimator as the
objective, we may express the a posteriori estimate
^
xx
k
as a linear
combination of the a priori estimate and the new measurement, as
shown by
^
xx
k
¼ G
ð1Þ
k
^
xx
À
k
þ G
k
y
k
; ð1:5Þ
where the multiplying matrix factors G
ð1Þ

ð1Þ
k
^
xx
À
k
À G
k
H
k
x
k
À G
k
w
k
Þy
T
i
¼0 for i ¼ 1; 2; ...; k À 1:
ð1:8Þ
Since the process noise w
k
and measurement noise v
k
are uncorrelated, it
follows that
E½w
k
y

i
¼0; ð1:9Þ
where I is the identity matrix. From the principle of orthogonality, we now
note that
E½ðx
k
À
^
xx
À
k
Þy
T
i
¼0:
Accordingly, Eq. (1.9) simplifies to
ðI À G
k
H
k
À G
ð1Þ
k
ÞE½x
k
y
T
i
¼0 for i ¼ 1; 2; ...; k À 1: ð1:10Þ
For arbitrary values of the state x

k
: ð1:11Þ
Substituting Eq. (1.11) into (1.5), we may express the a posteriori estimate
of the state at time k as
^
xx
k
¼
^
xx
À
k
þ G
k
ðy
k
À H
k
^
xx
À
k
Þ; ð1:12Þ
in light of which, the matrix G
k
is called the Kalman gain.
There now remains the problem of deriving an explicit formula for G
k
.
Since, from the principle of orthogonality, we have

is an estimate of y
k
given the previous measurement
y
1
; y
2
; ...; y
kÀ1
.Define the innovations process
~
yy
k
¼ y
k
À
^
yy
k
: ð1:15Þ
The innovation process represents a measure of the ‘‘ new’’ information
contained in y
k
; it may also be expressed as
~
yy
k
¼ y
k
À H

À
^
xx
k
Þ
~
yy
T
k
¼0: ð1:17Þ
Using Eqs. (1.3) and (1.12), we may express the state-error vector x
k
À
^
xx
k
as
x
k
À
^
xx
k
¼
~
xx
À
k
À G
k

xx
À
k
À G
k
v
k
gðH
k
~
xx
À
k
þ v
k
Þ ¼ 0: ð1:19Þ
Since the measurement noise v
k
is independent of the state x
k
and
therefore the error
~
xx
À
k
, the expectation of Eq. (1.19) reduces to
ðI À G
k
H

k
Þðx
k
À
^
xx
À
k
Þ
T

¼ E½
~
xx
À
k
Á
~
xx
TÀ
k
: ð1:21Þ
1.3 KALMAN FILTER
7
Then, invoking the covariance definitions of Eqs. (1.4) and (1.21), we may
rewrite Eq. (1.20) as
ðI À G
k
H
k

þ R
k

À1
; ð1:22Þ
where the symbol ½Á
À1
denotes the inverse of the matrix inside the square
brackets. Equation (1.22) is the desired formula for computing the Kalman
gain G
k
, which is defined in terms of the a priori covariance matrix P
À
k
.
To complete the recursive estimation procedure, we consider the error
covariance propagation, which describes the effects of time on the
covariance matrices of estimation errors. This propagation involves two
stages of computation:
1. The a priori covariance matrix P
À
k
at time k is defined by Eq. (1.21).
Given P
À
k
, compute the a posteriori covariance matrix P
k
, which, at
time k,isdefined by

À
k
.
To proceed with stage 1, we substitute Eq. (1.18) into (1.23) and note
that the noise process v
k
is independent of the a priori estimation error
~
xx
À
k
.
We thus obtain
1
P
k
¼ðI À G
k
H
k
ÞE½
~
xx
À
k
~
xx
TÀ
k
ðI À G

R
k
G
T
k
: ð1:24Þ
1
Equation (1.24) is referred to as the ‘‘ Joseph’’ version of the covariance update equation
[5].
8
1 KALMAN FILTERS