Introduction to Minimax Filtering

H2 filtering, also known as Kalman filtering, is an
estimation method which minimizes “average” estimation error.
More precisely, the Kalman filter minimizes the variance of the
estimation error. But there are a couple of serious limitations
to the Kalman filter.

  1. The Kalman filter assumes that the noise properties are
    known. What if we don't know anything about the system

  2. The Kalman filter minimizes the “average” estimation
    error. What if we would prefer to minimize the worst-case
    estimation error?

These limitations gave rise to H∞ filtering, also known as
minimax filtering. Minimax filtering minimizes the “worst-case”
estimation error. More precisely, the minimax filter minimizes
the maximum singular value of the transfer function from the
noise to the estimation error. While the Kalman filter requires
a knowledge of the noise statistics of the filtered process,
the minimax filter requires no such knowledge. The Kalman
filter dates back to the late 1950s while the minimax filter
has its roots in the late 1980s.


Consider the problem of estimating the variables of some
system. In dynamic systems (that is, systems which vary with
time) the system variables are often denoted by the term “state
variables”. Assume that the system variables, represented by
the vector x, are governed by the equation xk+1 =
Axk + wk where wk is random
process noise, and the subscripts on the vectors represent the
time step. Now suppose we can measure some combination of the
states. Then our measurement can be represented by the equation
zk = Hxk + vk where
vk is random measurement noise.

Now suppose we want to find an estimator for the state x
based on the measurements z and our knowledge of the system
equation. The estimator structure is assumed to be in the
following predictor-corrector form:

= Ak
+ Kk (zk+1 – HAk

where Kk is some gain which we need to determine.
If we want to minimize the 2-norm (the variance) of the
estimation error, then we will choose Kk based on
the Kalman filter. However, if we want to minimize the ∞-norm
(the “worst-case” value) of the estimation error, then we will
choose Kk based on the minimax filter.

Several minimax filtering formulations have been proposed.
The one we will consider here is the following: Find a filter
gain Kk such that the maximum singular value is less
than g . This is a way of minimizing
the worst-case estimation error. This problem will have a
solution for some values of g but
not for values of g which are too
small. If we choose a g for which
the stated problem has a solution, then the minimax filtering
problem can be solved by a constant gain K which is found by
solving the following simultaneous equations:

K = (I + P/g )-1 PHT

P-1 = M-1 – I/g + HT H

M = APAT + I (4)

In the above equations, the superscript -1 indicates matrix
inversion, the superscript T indicates matrix transpostion, and
I is the identity matrix. The simultaneous solution of these
three equations is a problem in itself, but once we have a
solution, the matrix K gives the minimax filtering solution. If
g is too small, then the equations
will not have a solution.

One method to solve the three simultaneous equations is to
use an iterative approach. A more analytical approach is as

  1. Form the following 2n 2n matrix:


  2. Find the eigenvectors of Z. Denote those eigenvectors
    corresponding to eigenvalues outside the unit circle as c i (i = 1, . . . , n).

  3. Form the following matrix:


    where X1 and X2 are n n

  4. Compute M = X2
    X1 -1 .

This method only works if X1 has an inverse. If
X1 does not have an inverse, that means that the
chosen value of g is too small.

At this point we see that both Kalman and minimax filtering
have their pros and cons. The Kalman filter assumes that the
noise statistics are known. The minimax filter does not make
this assumption, but further assumes that absolutely nothing is
known about the noise. Suppose that although the noise
statistics are not perfectly known, we have a rough idea about
these statistics. Further suppose that we want to minimize some
combination of the 2-norm and the ∞-norm of the estimation
error. What could be done? Perhaps some combination of Kalman
and minimax filtering could be used.


For more information on minimax filtering, visit Innovatia
Software's Web site.

© 1998″2001 Innovatia Software. All Rights Reserved.

0 comments on “Introduction to Minimax Filtering

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.