Kalman filters and matrix inverses

Hi all.

I'm reading about Kalman filters in Durbin & Koopman: "Time series
analysis by state space methods". The filtering equations are

  y[t] = Z[t]a[t] + e[t]
  a[t+1] = T[t]a[t] + R[t]n[t]

where

  e[t] ~ N(0,H[t])
  n[t] ~ N(0,Q[t])
  a[1] ~ N(A[1],P[1]).

A bit into the derivations,  a matrix F appears as

  F[t] = Z[t]P[t]Z'[t] + H[t].

The inverse of F is used as

a[t+1] = T[t]a[t]+T[t]P[t]Z'[t]F^{-1}[t]v[t].

My questions concern the matrix inverse F^{-1}[t], which
seem to repersent a major computational task:

- Does one have to explicitly compute F[t] and invert it?
- Are there situations where other, more efficient ways of
  finding F^{-1}[t] can be used?

Any comments appreciated.

Rune

On 2006-08-20 03:31:20 -0300, "Rune Allnor" <allnor@tele.ntnu.no> said:

> Hi all.
> 
> I'm reading about Kalman filters in Durbin & Koopman: "Time series
> analysis by state space methods". The filtering equations are
> 
>   y[t] = Z[t]a[t] + e[t]
>   a[t+1] = T[t]a[t] + R[t]n[t]
> 
> where
> 
>   e[t] ~ N(0,H[t])
>   n[t] ~ N(0,Q[t])
>   a[1] ~ N(A[1],P[1]).
> 
> A bit into the derivations,  a matrix F appears as
> 
>   F[t] = Z[t]P[t]Z'[t] + H[t].
> 
> The inverse of F is used as
> 
> a[t+1] = T[t]a[t]+T[t]P[t]Z'[t]F^{-1}[t]v[t].
> 
> My questions concern the matrix inverse F^{-1}[t], which
> seem to repersent a major computational task:
> 
> - Does one have to explicitly compute F[t] and invert it?
> - Are there situations where other, more efficient ways of
>   finding F^{-1}[t] can be used?
> 
> Any comments appreciated.
> 
> Rune

You could try reading a book on numerical methods in least squares.
It will go into techniques for avoiding inverses, or even the Normal
Equations via cross products.

A highly recommended book is the the one by Ake Bjorck and published
by SIAM. He lives in your general neigbourhood as he is a Swede. He
hangs out in Linkoping but is "retired" from the universtiy although
still seems to be giving papers. See <http://www.mai.liu.se/~akbjo/>.
Draft chapters for his new book are available as pdf downloads.

It is usually difficult to create a general form of a Kalman filter to
implement that is computationally efficient.  Based on your specific
application, you can often times make assumptions based on symmetry and
what not, where there may exist a direct method to calculate the
inverse with out all of the divisions etc.  You might want to check out
IEEE, there are several papers that go into hardware efficient methods
for Kalman filter implementation.
Rune Allnor wrote:
> Hi all.
>
> I'm reading about Kalman filters in Durbin & Koopman: "Time series
> analysis by state space methods". The filtering equations are
>
>   y[t] = Z[t]a[t] + e[t]
>   a[t+1] = T[t]a[t] + R[t]n[t]
>
> where
>
>   e[t] ~ N(0,H[t])
>   n[t] ~ N(0,Q[t])
>   a[1] ~ N(A[1],P[1]).
>
> A bit into the derivations,  a matrix F appears as
>
>   F[t] = Z[t]P[t]Z'[t] + H[t].
>
> The inverse of F is used as
>
> a[t+1] = T[t]a[t]+T[t]P[t]Z'[t]F^{-1}[t]v[t].
>
> My questions concern the matrix inverse F^{-1}[t], which
> seem to repersent a major computational task:
>
> - Does one have to explicitly compute F[t] and invert it?
> - Are there situations where other, more efficient ways of
>   finding F^{-1}[t] can be used?
> 
> Any comments appreciated.
> 
> Rune

Rune Allnor wrote:

> Hi all.
> 
> I'm reading about Kalman filters in Durbin & Koopman: "Time series
> analysis by state space methods". The filtering equations are
> 
>   y[t] = Z[t]a[t] + e[t]
>   a[t+1] = T[t]a[t] + R[t]n[t]
> 
> where
> 
>   e[t] ~ N(0,H[t])
>   n[t] ~ N(0,Q[t])
>   a[1] ~ N(A[1],P[1]).
> 
> A bit into the derivations,  a matrix F appears as
> 
>   F[t] = Z[t]P[t]Z'[t] + H[t].
> 
> The inverse of F is used as
> 
> a[t+1] = T[t]a[t]+T[t]P[t]Z'[t]F^{-1}[t]v[t].
> 
> My questions concern the matrix inverse F^{-1}[t], which
> seem to repersent a major computational task:
> 
> - Does one have to explicitly compute F[t] and invert it?
> - Are there situations where other, more efficient ways of
>   finding F^{-1}[t] can be used?
> 
> Any comments appreciated.
> 
> Rune
> 
Keep reading.

You can't get entirely away from inverting F, or some other matrix. 
Depending on the form of the filter, and the problem involved, there are 
things you _can_ do:

* If Z, T and R are time invariant, or always evolve the same way, you 
can compute F[t] and P[t] offline once, then use the stored values.

* If Z, T and R are time invariant, if the start-up performance of the 
filter isn't that important, and if certain other conditions are met you 
can compute F[infinity] and P[infinity] and use the steady-state Kalman.

* IIRC, the dimensions of F match the dimension of y, so if there aren't 
too many elements in y the matrix inversion isn't that bad.

I assume that your book will cover this.  If not, I just got a copy of 
"Optimal State Estimation: Kalman, H-infinity, and Nonlinear Approaches, 
John Wiley & Sons, 2006" by Dan Simon, which does (and which is why 
these answers were fresh in my mind).

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Posting from Google?  See http://cfaj.freeshell.org/google/

"Applied Control Theory for Embedded Systems" came out in April.
See details at http://www.wescottdesign.com/actfes/actfes.html

Tim Wescott wrote:

> I assume that your book will cover this.  If not, I just got a copy of
> "Optimal State Estimation: Kalman, H-infinity, and Nonlinear Approaches,
> John Wiley & Sons, 2006" by Dan Simon, which does (and which is why
> these answers were fresh in my mind).

Thanks for mentioning it. I'll have a look at it on amazon.com, and
probably 
order it pretty soon. 

Rune