Minimax Filtering
Dan Simon
Innovatia Software
dan@innovatia.com
Copyright 1998–2007 Innovatia Software. All Rights Reserved.
Preliminaries
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.
§
The
Kalman filter assumes that the noise properties are known. What if we don't
know anything about the system noise?
§
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-infinity 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.
Mathematics
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:
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 infinity-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:
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 follows:
§
Form
the following 2n ´ 2n matrix:
§
Find
the eigenvectors of Z. Denote those eigenvectors corresponding to
eigenvalues outside the unit circle as c i
(i = 1, . . . , n).
§
Form
the following matrix:
where X1 and X2 are n ´ n matrices.
§
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 infinity-norm of the estimation
error. What could be done? Perhaps some combination of Kalman and minimax
filtering could be used. Innovatia Software has written a white paper on this
very topic entitled Hybrid Kalman / Minimax Filtering.
References
Here are a couple of good
books about H-infinity theory.
·
B.
Francis, "A Course in H-infinity Control Theory," Springer-Verlag,
1987.
·
M.
Green and D. Limebeer, "Linear Robust Control," Prentice Hall, 1994.
·
J.
Burl, “Linear Optimal Control,” Addison Wesley, 1999.
I also
cover the basics of H-infinity filtering in a section of my book “Optimal State
Estimation.” The book web site is http://academic.csuohio.edu/simond/estimation,
where you can download more Matlab source code and additional tutorial
articles.
There have been a lot of
papers published on H-infinity theory since the late 1980s. Most recent issues
of the IEEE Transactions on Automatic Control have one or more papers on
the topic. Following are a couple of papers on the subject that I've written
which contain further useful references.
·
D.
Simon and H. El-Sherief, "Hybrid Kalman / Minimax Filtering in
Phase-Locked Loops," Control Engineering Practice, October 1996.
·
D.
Simon and H. El-Sherief, "Hybrid H2/H-infinity Estimation for Phase-Locked
Loop Filter Design," American Control Conference, 1994.
Home
Credentials
Publications White Papers
Copyright 1998–2007 Innovatia. All Rights
Reserved.
Email Address: dan@innovatia.com
Phone Number: (216)687-5407
Last Revised: May 29, 2007