KALMAN FILTER

Linear Prediction Model
Given the knowledge of the measured variable yn-1, ..., yn-m, the prediction of yn is denoted Yn , and the prediction error is the difference between the newly measured value and its prediction,

fm(n) = yn - Yn( yn-1, ..., yn-m)

an = fm(n) is called the innovation. We assume that the prediction is a linear function of the measured values (linear prediction), with coefficients cn,k. The innovation can therefore be written

an = yn + ∑k=1 .. m cn,k yn-k

The coefficients of the linear prediction are obtained by minimizing the correlation of the innovation with the measures,

E[ an yn-k ] = 0     for k in 1 .. m

or equivalently
E[ an an-k ] = 0     for k in 1 .. m

If the process is stationary the prediction coefficicents cn,k do not depend on the index n, but only on the delay index k. In this case they are computed by solving the linear equation

E[ yn-h yn-k] ck + E[ yn-h yn] = 0

The estimation of the parameter variable x is assumed a linear function of the measures, i.e., of the innovations,

Xn( yn, yn-1, ..., yn-m) = Xn( an, an-1, ..., an-m) = ∑k=0 .. m bk an-k

bk is found by minimizing the distance between xn and Xn. This is a mean square value problem. In order to find the minimum of

F = | xn - ∑k=0 .. m bk an-k |2

the derivatives of F with respect to the bk are computed and equated to zero. This gives the equations

∑j=0 .. m E[an-k an-j] bj = E[ xn an-k]

Since E[akaj]=0 if k is different from j, this system is immediately solved

bk = E[ xn an-k] / E[ an-k an-k]

and

Xn(y) = Xn-1(y) + bn an

which is suitable for a recursive implementation since Xn(y1 ... yn) is expressed as Xn-1(y1 ... yn-1) and a coefficient, bn , that depends on xn and an, i.e., on xn and yn, and is multiplied by an.

Kalman Filter

Suppose to have a model described by the (linear) evolution equation

xn+1 = An xn + Bn+1 un+1 + wn

where An is a MxM state transition matrix, xn is a M-dim state vector (parameter variable of the system), and wn is a M-dim noise vector with normal probability distribution, with zero mean and covariance W,
E[ wn wk] = W dn,k

un+1 is an additional control paramater, which will be ignored in the sequel.

The measured variable is

yn = Hn xn + vn

where Hn is a NxM matrix, vn a N-dim measurement noise vector, with normal probability distribution, with zero mean and covariance V and uncorrelated to wk. The process and noise covariances might change at each step, ie, they might depend on the index n, but we will assume that they are constant. The matrices An and Hn are assumed known. In general thay change with the time step.

The covariance of the system state is Pn+1,n = E[ xn+1 xn ].

The a-priori estimate of the system state (ie, the estimate at time step n+1 given the knowledge up to time n) is

xn+1|n = An xn|n + wn

and the a-posteriori estimate of the system state, given the measurement yn+1, is
xn+1|n+1 = xn+1|n + Kn+1 ( yn+1 - Hn+1 xn+1|n )

where the Kalman gain matrix is to be determined.

The estimate errors are

en+1|n = xn+1 - xn+1|n
en+1|n+1 = xn+1 - xn+1|n+1

The covariances of the a-priori and a-posterior estimate errors are computed recursively
Pn+1|n = An Pn|n An + W
Pn+1|n+1 = ( I - Kn+1 Hn+1) Pn+1|n

and the Kalman gain matrix is
Kn+1 = Pn+1,n Hn+1t ( V + Hn+1 Pn+1,n Hn+1t )-1

To derive these results we begin by writing the a-posteriori estimate as a linear combination of the a-priori estimate and the difference between the actual measurement and the predicted measurement,

xn+1|n+1 = xn+1|n + Kn+1 ( yn+1 - Hn+1 xn+1|n )

The term in parenthesis is called the measurement innovation. When it is zero there is no difference between the predicted measurement and the actual measurement. The matrix Kn+1 is called gain and is chosen so tat to minimize the a-posteriori error covariance.

To find it we substitute this equation in the definition of the covariance, the derivative with respect to K is taken and equated to zero. THe result is the expression of the Kalman gain matrix written above.

When the process is not linear the Kalnam filter theory can be applied to the linearized system (about te current mean and covariance). This is called Extended Kalman Filter.

"Kalman Filter Theory" in S. Haykin, Adaptive Filter Theory, Prentice Hall, 1986, p. 269.
http://www.cs.unc.edu/~welch/kalman/

Marco Corvi - Page hosted by geocities.com.