176 IEEE TRANSACTIONS ON SIGNAL PROCESSING, VOL. 50, NO. 2, FEBRUARY 2002
where
(11)
(12)
(13)
(14)
and where
is a Gaussian density with argument ,
mean
, and covariance , and
(15)
(16)
are the covariance of the innovation term
, and
the Kalman gain, respectively. In the above equations, the trans-
pose of a matrix
is denoted by .
This is the optimal solution to the tracking problem—if the
(highly restrictive) assumptions hold. The implication is that no
algorithm can ever do better than a Kalman filter in this linear
Gaussian environment. It should be noted that it is possible to
derive the same results using a least squares (LS) argument [22].
All the distributions are then described by their means and co-
variances, and the algorithm remains unaltered, but are not con-
strained to be Gaussian. Assuming the means and covariances
to be unbiased and consistent, the filter then optimally derives
the mean and covariance of the posterior. However, this poste-
rior is not necessarily Gaussian, and therefore, if optimality is
the ability of an algorithm to calculate the posterior, the filter is
then not certain to be optimal.
Similarly, if smoothed estimates of the states are required,
that is, estimates of
, where ,
3
then the
Kalman smoother is the optimal estimator of
.
This holds if
is fixed (fixed-lag smoothing, if a batch of data
are considered and
(fixed-interval smoothing), or if
the state at a particular time is of interest
is fixed (fixed-point
smoothing). The problem of calculating smoothed densities is
of interest because the densities at time
are then conditional
not only on measurements up to and including time index
but
also on future measurements. Since there is more information
on which to base the estimation, these smoothed densities are
typically tighter than the filtered densities.
Although this is true, there is an algorithmic issue that should
be highlighted here. It is possible to formulate a backward-time
Kalman filter that recurses through the data sequence from the
final data to the first and then combines the estimates from the
forward and backward passes to obtain overall smoothed es-
timates [20]. A different formulation implicitly calculates the
backward-time state estimates and covariances, recursively esti-
mating the smoothed quantities [38]. Both techniques are prone
to having to calculate matrix inverses that do not necessarily
exist. Instead, it is preferable to propagate different quantities
using an information filter when carrying out the backward-time
recursion [4].
3
If
`
=0
, then the problem reduces to the estimation of
p
(
x
j
z
)
consid-
ered up to this point.
B. Grid-Based Methods
Grid-based methods provide the optimal recursion of the fil-
tered density
if the state space is discrete and consists
of a finite number of states. Suppose the state space at time
consists of discrete states , . For each state
, let the conditional probability of that state, given mea-
surements up to time
be denoted by , that is,
. Then, the posterior pdf
at
can be written as
(17)
where
is the Dirac delta measure. Substitution of (17) into
(3) and (4) yields the prediction and update equations, respec-
tively
(18)
(19)
where
(20)
(21)
The above assumes that
and are known
butdoes not constrain the particular form of these discrete densi-
ties. Again, this is the optimal solution if the assumptions made
hold.
IV. S
UBOPTIMAL ALGORITHMS
In many situations of interest, the assumptions made above
do not hold. The Kalman filter and grid-based methods cannot,
therefore, be used as described—approximations are necessary.
In this section, we consider three approximate nonlinear
Bayesian filters:
a) extended Kalman filter (EKF);
b) approximate grid-based methods;
c) particle filters.
A. Extended Kalman Filter
If (1) and (2) cannot be rewritten in the form of (6) and (7)
because the functions are nonlinear, then a local linearization of
the equations may be a sufficient description of the nonlinearity.
The EKF is based on this approximation.
is approx-
imated by a Gaussian
(22)
(23)
(24)