Google Answers Logo
View Question
 
Q: Kalman filter implementation ( Answered 5 out of 5 stars,   6 Comments )
Question  
Subject: Kalman filter implementation
Category: Science > Math
Asked by: asiatechnicals-ga
List Price: $53.00
Posted: 18 Feb 2003 18:40 PST
Expires: 20 Mar 2003 18:40 PST
Question ID: 163255
Background
==========

I am a finance professional asked to give a presentation on smoothing
of economic timeseries.  I would like to include optimal smoothing,
but do not have the mathematical ability to implement a Kalman filter.


Ability Level
=============

I use Excel and VBA regularly and I have a fair amount of practical
experience with timeseries analysis, analog signal processing,
forecasting and statistical concepts. My mathematical ability is stuck
where I stopped studying it at age 16 and has degraded somewhat; I
have trouble with mathematical notation and medium-advanced
mathematical techniques, including, unfortunately, matrix algebra.

I have done some background reading on Kalman filters, from John
Elhers' "Rocket science for traders" which presents only the most
basic concepts, to Eli Brookner's "Tracking and Kalman Filtering Made
Easy" which, for a lay-person such as myself, is interesting, yet did
not help me build one for myself.


Question
========

Help me implement a Kalman filter in Excel. A simple example of a
Kalman filter would do. I would prefer a spreadsheet solution,
possibly using Excel's matrix formulae, but I'll accept a VBA solution
if necessary. I suggest historical monthly closing S&P500 for a
dataset, unless you have an alternative.


Deliverables
============

A file, VBA listing, detailed and simple instructions for entering
formulae, or whatever it takes for me to have a working, modifiable,
Excel implementation.


Professional Fees
=================

I assume this question will be answered by a professional familiar
with Kalman filters.  Therefore I will pay my standard Google Answers
rate of $20 per hour, on the basis of two chargeable hours' work.
Hence, I have priced the question at $53, including Google Answers'
commission.

I realise I may have misjudged the requirements and, notwithstanding
Google Answers' researcher guidelines, am willing to negotiate a
different price. I'll discuss lowering the fee if you cannot deliver
exactly what I need, but can point me to an existing third party
implementation on the Web, or raising the fee (through tipping) if you
feel it needs more work, but can still deliver value for money.


Rating
======

A five star rating will be timely and complete, and leave me able to
implement Kalman filters and deduce/explain the concepts to others. A
four star rating, would be for an answer, that following clarification
remains acceptable, but not completely satisfies my requirements.
Other answers will be ungraded.

Request for Question Clarification by mathtalk-ga on 19 Feb 2003 11:39 PST
Hi, asiatechnicals-ga:

Thanks for posting this interesting question, which I'd like to
address.  I have an extensive (doctoral) background in numerical
analysis, and you can check some of my answers to programming and
mathematics questions here by clicking on my username.

I often recommend Excel as the "poor man's" numerical analysis
toolkit, but it does have some shortcomings as far as a production
environment.  Here, of course, your purpose is primarily educational.

For the list price offered I think you are asking a large effort.  Not
only is the functionality required substantial, you ask ideally for an
answer that will provide you the ability "to implement Kalman filters
and deduce/explain the concepts to others."

My feeling is that your request is close to the upper limit of
granularity that can be handled through the Google Answers mechanism. 
Nonetheless I am willing to work with you towards this goal.  I'm not
interested in trying to simplify the requirements downward, though
other researchers might entertain such an approach.

You suggested the monthly S&P 500 closing prices as a suitable time
series.  I created an Excel spreadsheet with 1985 through 1999 values.
 Would that be sufficient for your demonstration?

You contrast the use of Excel spreadsheet functions with VBA coding,
with noted preference for the former.  Would it be acceptable to have
a very slow implementation that used only spreadsheet functions?  The
time series above has 180 entries.  Solutions of the corresponding
matrix equations are apt to be time consuming without assistance from
external DLLs.

regards, mathtalk-ga

Clarification of Question by asiatechnicals-ga on 19 Feb 2003 18:22 PST
Mathtalk-ga,

Thank you for picking up this question. You are the first person I
have ever corresponded with that has been able to answer it.  My
flexible approach to deliverables reflected my expectation of the
scarcity of people with your skills at Google Answers.

I chose an Excel implementation because it would prevent important
concepts and algorithmic elements from being obscured behind DLLs and
other shortcuts. The primary purpose of this exercise is the education
of myself and others. It needs only demonstrate the principles and
produce a prediction series for benchmarking other filters.
Performance is not an issue, as this will never be used for real-time
analysis. Therefore, I continue to prefer a spreadsheet
implementation, although I recognize that some algorithms are far
better suited to a VBA-like structure.

The time series you propose is fine. I only need enough history to
build the structure and check it is working correctly. I did not know
how much data is needed to initialize the arrays, hence the open-ended
time series.  I assume the implementation will be easily extensible
for longer timeseries.

I estimated 2 hours for the task, because from my experience
programming and with spreadsheets under pressure, most structures can
be implemented within this timeframe, from FFTs to the carrying
forward of tax losses. I don't need much functionality or
documentation; I already understand the principles of Kalman filters,
I simply can't implement the matrix algebra.

As stated in the original brief, if these relatively modest
requirements can't be implemented to a satisfactory quality within the
budget required, you are welcome to propose an appropriate price.

I look forward to your response.

Regards,

AsiaTechnicals-ga

Clarification of Question by asiatechnicals-ga on 20 Feb 2003 23:57 PST
I've asked your friend dannidin-ga if he/she wants to attempt an
independent solution (id=165102).  This doesn't affect my above
question for you or my offer of discussing a reasonable price.

Dannidin's done some excellent work for me before (id=111686) and I'd
be interested in seeing how similar/ different your approaches are to
the challenge above.

Request for Question Clarification by mathtalk-ga on 21 Feb 2003 06:54 PST
Dannidin does indeed do excellent work!  I'm sure we'd both learn a
good bit from any answer Dannidin finds time to post.

Here is a question for you, asiatechnicals.  It seems that a central
concern is to illustrate/illuminate the matrix arithmetic aspects of
Kalman filters.  But if we apply the algorithm to a "system" like S&P
500 monthly closes, then the "state" of the system is only a single
scalar: the arithmetic is scalar rather than matrix (and the Kalman
filter is much like a moving average in terms of how it smooths the
time series).

So in order to illustrate the matrix aspects of the computation, I
think we need to include a second component to the system.  In this
regard I propose that we look at the pairing of S&P 500 monthly
closing prices with some monthly prices for an ounce of gold. 
Naturally we expect to find a bit of "anti-correlation" in these two
components.

I think this will make for a simple "matrix" demonstration in the
range of financial applications.  What do you think?

regards, mathtalk-ga

Clarification of Question by asiatechnicals-ga on 22 Feb 2003 02:41 PST
My goal is fairly unambitious.

I have implemented a number of IIR and FIR filters, including adaptive
and predictive examples and these are the primary focus of my
presentation. The Kalman filter will be used as an example of optimal
estimation of the index level, rejecting high frequency noise (low
pass).  As such, it will not be required to integrate multiple inputs,
beyond time and price. This is a simplified application analogous to
radar tracking. (*See Link)

I agree that the use of matrix algebra is the key strength of Kalman
filtering and its power is somewhat squandered in a smoothing
application. However, I prefer to stick to the original brief due to
the simplicity.  My audience will be principly traders and analysts,
people noted for their practicality, rather than mathematical prowess
(as am I). I need only present the concept, describe its performance,
strengths and weaknesses and be prepared to answer general laypersons'
questions. I also intend to deliver my spreadsheet so that they may
further understand and verify my working in their own time.

John Ehlers, in book "Rocket Science for Traders", describes the
principles of the g-h Kalman Filter, and proceeds to demonstrate them
through what I remember to be an exponential moving average corrected
by the smoothed residuals. This is not the methodology I see described
in the more technical books, the use of which remains sadly out of my
reach.

Therefore, I respectfully request the original specification, or
something not much more enhanced. I would be grateful if you would
accept my question and despite its weaknesses.

To save time, I propose we begin work at the price listed. We can
adjust the final payment through tipping. I am sure Dannidin-ga would
vouch for my willingness to pay fairly, if you ask him. I will be
working through the weekend on the presentation and can assure you of
a timely response to ongoing requests for clarification.

Regards,

Asiatechnicals

*Link: Meyers Analytics; g-h Kalman Filter Application Description
https://w1427.securedweb.net/meyersanalytics/www/kalf.htm

Request for Question Clarification by mathtalk-ga on 22 Feb 2003 12:57 PST
Hi, asiatechnicals:

I posted some "working notes" below as a comment (and note also my
earlier comment, in case you didn't already).  It might be helpful to
review the notation chosen.  Neither Google Answers nor Excel make an
especially clear medium for writing "x-hat" symbols, so I've tried to
come up with a simple version of the notation (that's not too simple,
as Einstein might have warned us).  The "decoration" of my Excel
worksheet is being built around this notation, so let me know if you
have some suggestions.

regards, mathtalk

Clarification of Question by asiatechnicals-ga on 22 Feb 2003 18:15 PST
The modified notation works fine for me; especially having puzzled my
way through a few papers, books and web pages.

The working notes are interesting. I've also had trouble determining
the Kalman gain and initializing variables. There's no need to worry
about the rationale or the D.K.F. or to prove any formulae.
Answer  
Subject: Re: Kalman filter implementation
Answered By: mathtalk-ga on 23 Feb 2003 10:03 PST
Rated:5 out of 5 stars
 
Hi, asiatechnicals:

Your spreadsheet is PK'zipped and ready for download at:

http://www.lucidmatrix.com/uploads/MonthlyTS.zip

The Excel workbook includes three worksheets.  The first sheet
contains two time series, in reverse time order, for the S&P 500
monthly closing prices and for gold prices (per ounce), over the
period Jan. 1985 to Dec. 1999.

The second sheet is the desired implementation of the "g-h" Kalman
filter on the S&P closing prices and their month-to-month changes.

The third sheet has a chart that plots the row data (in blue) vs. the
filtered data (in pink).

I've tested the spreadsheet by changing the system parameters and
initial values around some.  I'd be glad to provide any clarifications
you want, in particular perhaps a discussion of how I chose these
parameters.

I'm including by reference the comments I wrote below concerning the
notation and forumulas involved for the discrete Kalman filter
algorithm.

regards, mathtalk

Request for Answer Clarification by asiatechnicals-ga on 06 Mar 2003 05:56 PST
Sorry about the extended delay.  I've been really snowed under and I
wanted to give your original Comment before I can back to you with
only a partial understanding.

As I said previously, the spreadsheet looks to have produced
everything I asked for and exactly as envisaged; quite a miracle in
itself.

I am particularly interested in your formulae, especially the matrix
formulae. I am terribly lost in that respect and an explanation would
be gratefully received.  Perhaps answer this part first if you are
busy, so that I can mull your clarification over while you work on
other things.

As a second priority, please also explain how the system parameters
and initial values were selected.

I expect this clarification and your original notes will have put you
over our agreed time budget.  Let me know your claim for additional
hours worked (at the $20/hr rate agreed).

Clarification of Answer by mathtalk-ga on 08 Mar 2003 09:44 PST
Hi, asiatechnicals:

It was great to hear from you, and I will be glad to provide some
clarification.  Since the original "urgency" of your request no longer
seems as great, I have tried to take my time these past two days in
drafting my clarification, hoping to wrap things up on the current
question.

In the earlier write up that I posted as a Comment, we walked through
the formulas for the (linear) Kalman filter in some detail and
generality.  Given your focus on having a better understanding of
matrix computations generally, it might be best to drop back a step
and discuss matrix arithmetic.  Then we can look at how Excel supports
matrix operations and what specific use I made of them in the
spreadsheet.

A matrix is a rectangular array of numbers, and we usually describe
the "size" of a matrix as "m by n" meaning m rows by n columns. 
Addition of matrices is easy.  Two matrices can be added together if
they have the same size.  Their sum is obtained by adding the
corresponding entries of given rows and columns, so that the result is
a matrix again of the same size.

E.g. [+1 -3] + [-2 +4] = [-1 +1].

There are two "multiplication" operations that apply to matrices.  One
is termed "scalar multiplication".  Here "scalar" refers to an
ordinary number (as opposed to a matrix), and scalar multiplication is
an operation that involves one ordinary number and one matrix.  The
result is gotten by multiplying each entry of the matrix by the
ordinary number (scalar), producing a matrix of same size as the given
matrix.

E.g. 3 * [-1 +1] = [-3 +3].

The second sort of multiplication that concerns matrices is properly
called "matrix multiplication" and operates on two matrices.  However
there are compatibility requirements on the sizes of the two matrices
involved, in order for the multiplication to be defined.  The product
AB of matrices A,B is only defined if the length of a row in A agrees
with the length of column in B.

In terms of "matrix sizes" of A,B this means that for A an m by n
matrix, B must be an n by p matrix.  Then the matrix multiplication is
carried out by summing, for each row of A and each column of B, the
products of corresponding entries (as one sweeps along the row in A
and down the column in B).

The simplest example is when A consists of a single row and B a single
column.  Their product (assuming equal lengths) is then a 1 by 1
matrix:

E.g. Let A = [+1 -1] be a single row.

Let B = [+1] be a single column.
        [-1]

Then AB = [+1 -1] * [+1]
                    [-1]

         = [(+1)(+1)+(-1)(-1)] = [2]

The general case, in which A contains several rows and B several
columns, is performed in the same way.  Where A is m by n and B is n
by p, their product:

C = AB

will be an m by p matrix.  Notice that in many cases AB can be defined
but BA may either not be defined or, even if it is defined, it may be
of different size than AB (or unequal to AB, even if the same size). 
For this reason we must say that matrix multiplication is _not_
commutative in general.  (However matrix addition is a commutative
operation, A + B = B + A whenever one side is defined.)

Special importance is placed on the "identity" elements for matrix
addition and matrix multiplication.  The identity element for matrix
addition is simply the matrix whose entries are all zeroes, the "zero
matrix" of appropriate size which we conventionally denote by 0 when
there is no confusion with scalar 0.

E.g. 0 + A = A = A + 0 where 0 means a zero matrix of size the same as
A.

The identity element for matrix multiplication turns out to be a
square matrix with 1's on the diagonal and 0's elsewhere. 
Conventionally we denote this matrix by I, although of course it means
technically a different matrix depending on the size n by n which is
assigned.

E.g. If I is the n by n identity matrix and B is an n by p matrix,
then:

IB = B.

Note that here for us to write BI = B would require a possibly
different size identity matrix I, namely p by p.

If a matrix is square, then one can ask whether that matrix has a
multiplicative inverse.  That is, if A is n by n, it is possible that
there might exist another n by n matrix B such that:

AB = I

It turns out that this condition is equivalent (for a square matrix A)
to the existence of B such that BA = I (and that the same matrix B is
satisfies both conditions).  Note that "I" here means the n by n
identity matrix.

Rather than rehash the conditions under which a matrix has a
multiplicative inverse, I will refer you to this short Word document
on vector algebra:

[Vector spaces]
http://www.public.asu.edu/~sergei/classes/mat242f99/LinAlg3.doc 

and this Web page on matrix multiplication specifically:

[Matrix multiplication]
http://ccrma-www.stanford.edu/~jos/mdft/Matrix_Multiplication.html 

The facilities that Excel provides for matrix arithmetic involve not
only some built-in functions for matrix multiplication and inverses,
but equally important is the concept of array formula.  In order to
"output" a matrix from an Excel expression into a spreadsheet, the
rectangular array of cells which is to hold that matrix must be
"lumped together" in a way that assigns the expression to those cells
collectively.  This is done in much the same way as an ordinary
formula is assigned to a single cell.  A rectangular grouping of cells
is selected, by mouse or keystrokes.  The formula is entered into the
expression box above the spreadsheet.  Finally the formula is assigned
to the array of cells by the keystroke combination Ctrl-Shift-Enter
(instead of simply Enter for an ordinary formula).

I used some artifice in laying out the data and formulas in the
spreadsheet in order to produce a visually logical flow, from top to
bottom (earliest to most recent history).  One trick in particular
deserves explicit comment, but let me review briefly the earlier
discussion and its notation.

The formulas presented in my Comment below use a fairly standard
convention, by which "matrices" are denoted by capital letters and
"vectors" by lowercase letters.  The "vectors" are associated with
"state" information (their projections, estimates, errors, etc.),
while the "matrices" are derived from the underlying model and its
measurement covariance structure.  A richer text medium would allow
for more suggestive presentation of these matrix equations, but I
think the notation here was serviceable.

As is usual the "vectors" are treated in that discuss as "column"
vectors, and hence the matrix multiplication between "matrix" A and
"vector" v would be expressed Av.  That is where my "trick" in laying
out the spreadsheet comes into play.  In order to better maintain the
spreadsheet's flow I formatted the given vector data (in this case
monthly prices and monthly changes to prices) as rows rather than
columns (cf. the left-hand side of the spreadsheet).  The operation to
exchange rows for columns in matrices is called "transpose", and it is
often denoted by ' (lacking the ability to make a T-shaped
superscript).

As mentioned in the second of the links provided above, transpose and
matrix multiplication have the following curious relationship:

(Av)' = (v')(A')

In short, transposing a product reverses the order of matrix
multiplication.

Therefore you will see in some of my formulas that the order of
multiplication is backwards to what I described in the Comment below. 
That not all formulas need to be "reversed" is due to the symmetry of
many of the matrices referred to in the Kalman filter algorithm. [A
symmetric matrix is one which is equal to its transpose.]  If my
purpose here were less tied to "exposing" the steps of the algorithm
through a spreadsheet, I would not "resort" to such trickery.  It is
poor practice from a software engineering standpoint to revise the
"specs" on the fly in implementation.

The quick answer as to how I selected the system parameters is that I
played around with them until I got results which were neither too
"smoothed" nor too tightly coupled to the input data, using the Chart
worksheet as my visual guide.  The "model" equation, which garnered
the lion's share of that effort, reflects some knowledge of the fact
that the second component is a "delta" (change) of the first component
and some anticipation of a rising market trend (possibly no more than
inflationary increases).  In estimating the variances of the model I
did not do what would be reasonable for an actual data set, and that
is to estimate the variances using the sample data.  My focus, of
course, was on pedagogy rather than real world analysis.

Naturally, as you have asked about a topic which has a great deal of
application, estimation technique, and other literature associated
with it, my answer has touched only on a very narrow and basic extent
of it.  While I have tried to be reasonably self-contained in my
presentation, it is to be expected and even hoped that this note will
lead you to investigate further.

I appreciate the suggestion or acknowledgement that I have perhaps
spent more than the two hours orginally estimated by you in answering
the question.  It is somewhat important to me personally, and I think
to the Google Answers service during this "beta" period of
development, to provide a good answer almost independent of the price
offered.  One thought is that you might review, for the sake of future
questions, these Google Answers pricing guidelines:

http://answers.google.com/answers/pricing.html

A key recommendation there is to list a price according to how much
the required answer is valuable to you.  This approach would lend
itself to a more efficient "marketplace" of information exchange, in
the long run.
 
Another thought is that perhaps I might post a question for you. 
Although you are not a Google Answers researcher, you are able to
participate in the exchange of information by posting comments.  This
is a great way for non-researchers to increase the value of the
service offered by Google Answers, along with providing thoughtful
comments in the Ratings process.

regards, mathtalk

Request for Answer Clarification by asiatechnicals-ga on 11 Mar 2003 19:36 PST
Thank you for your clarification.  I have numerous follow-up queries,
but you have ably answered the original Question, so I plan to reserve
them for new Questions.

I understand that, given GA's policies, you may have trouble stating
what you consider to be a fair price for your work.  I would happily
waive this protection, because you are a valuable resource and I want
to continue to attract your Answers to my Questions.  Nevertheless, I
conservatively estimate that you have spent an additional 5 chargeable
hours on this assignment.  Hence I propose a tip of US$100.  Let me
know if you feel I have significantly underestimated your efforts.

I welcome your suggestion that I provide help to you on request. 
Given my wide range of interests, my skill set and my job nature,
which requires me to become familiar with any topic within a day's
notice, I can probably be of assistance to you from time to time. 
We'd have to keep the arrangement informal, because my workload is
very difficult to predict. Let me know how you plan to alert me on the
occasions you need my help.

Clarification of Answer by mathtalk-ga on 11 Mar 2003 22:03 PST
Hi, asiatechnicals:

However you arrived at the figure (the maximum tip which can be
given), I can assure you that I find your remarks complimentary and
encouraging.  In a strict sense I'm sure that negotiating over a tip
is against the spirit of the Google Answers policies, but of more
acute concern to me is the perception of my fellow researchers.  I
care a great deal for sustaining an unwritten contract of
professionalism with them.

One distinguishing characteristic of this service is that Google
Answers researchers are tested and approved on their ability to write
and search the Internet for relevant information.  Google Answers also
guarantees the satisfaction of customers.  I believe these policies
are intended to encourage customers to list a price for questions that
reflects the difficulty and urgency of their requests, despite
uncertainty about precisely which researcher might attempt an answer.

There are many additional points that might be raised, but some
specifics are at least touched upon in the pricing guidelines link
above.

I think a couple of points might be addressed to your own
circumstances.  While not every researcher here would consider
themselves qualified to tackle issues in higher mathematics, you have
already encountered one other such researcher, dannidin-ga, and I'm
aware of at least a third doctoral mathematician in our ranks.  There
are certainly others who are expert in related areas of software
engineering and financial analysis.

The other note is that the "thematic" design of Google Answers is a
question and answer format.  It is required that the question is posed
in English and that the "deliverables" are provided (loosely) as
English text.  In practice there are requests for materials that
stretch this framework:  an Excel spreadsheet (as in your case) or a
translation of something into German (to give another recent example).

Since the "software" you wanted was for a presentation, I felt the
request was within the realm of reason for the Google Answers service.
 Systems development of a more ambitious nature, such as a production
options pricing engine, would probably not be a good fit, though of
course one might post a question seeking recommendations for suitable
software development partners.  One obstacle to doing a very complex
project is the tension between interactivity needed for refining high
level requirements into specifications and the "arms length"
relationship between customer and researcher insisted upon by the
Google Answers terms of service.

It is pleasant to have the opportunity to assist you, and I'll be
looking forward to more challenges of this kind.

best wishes, mathtalk-ga
asiatechnicals-ga rated this answer:5 out of 5 stars and gave an additional tip of: $100.00
A perfectly comprehensive and professional response to an
exceptionally difficult question. The $100 tip on a $53 question was
worth every penny. Thank you.

Comments  
Subject: Re: Kalman filter implementation
From: dannidin-ga on 21 Feb 2003 13:34 PST
 
asiatechnicals,

i've posted a comment answering your question for me

https://answers.google.com/answers/main?cmd=threadview&id=165102

and mathtalk - thanks for the compliments, i've returned them in what
i wrote. good luck with your Excel project!

dannidin
Subject: Re: Kalman filter implementation
From: asiatechnicals-ga on 22 Feb 2003 02:44 PST
 
Dannidin,

Many thanks for the encouragement; I hope you'll find Mathtalk's
solution interesting.

Asiatechnicals
Subject: Re: Kalman filter implementation
From: mathtalk-ga on 22 Feb 2003 08:07 PST
 
Hi, asiatechnicals:

Thanks for responding to my request for clarification.  The link you
posted describe applying the Kalman filter algorithm to a "state" with
multiple components (and therefore makes use of matrix arithmetic).
The "g-h" approach that you single out in titling the link refers to
taking price to be one component and _change_ to price to be a second
component.

I'll proceed on the assumption that you'd like this same approach
taken to "smoothing" the S&P 500 monthly closing prices paired with
month to month differences in closing prices.  The arithmetic then
involves 2x2 matrices.

regards, mathtalk
Subject: Re: Kalman filter implementation
From: mathtalk-ga on 22 Feb 2003 12:52 PST
 
Mathematically speaking the discrete Kalman filter algorithm is a
"linear recursion" and is in principle very easy to formulate and
implement.  However some proper notation is required to clearly
explain the method in a manner that makes its application to new
problems accessible.

Given an "observed" sequence of vectors u_i, which represent a
combination of some underlying vector values z_i with measurement
errors e_i, and a "stochastic process" governing those underlying
values which also involves random perturbations f_i, the discrete
Kalman filter computes a pair of sequences, here called v_i and w_i,
which represent a priori and a posteriori estimates of u_i.

[Our notation here departs from the usual x-hat symbolism, which is
difficult to reproduce in this text-only medium.  It should be noted
that v_i corresponds to what is conventional denoted x-hat-minus,
while our w_i is "their" x-hat.]

For the present application we are assuming that the underlying vector
values are directly observable.  That means:

u_i = z_i + e_i

where in a more general setting one may assume a linear mapping from
the underlying z_i to the observable u_i, as:

u_i = Hz_i + e_i

In short we shall assume H = I the identity mapping.

The other "model" equation is the one which "governs" in a stochastic
sense that underlying process:

z_i = Az_{i-1} + b + f_i

Here again we are assuming a slightly simplified circumstance of a
constant "bias" vector b.  More generally one allows for controlled
inputs g_i to the process, which would relate to the above by another
matrix "parameter" B:

z_i = Az_{i-1} + Bg_i + f_i

In effect we are assuming that the controlled inputs g_i are fixed for
this application.

To summarize what is required in order to formulate this special case
of the discrete Kalman filter algorithm, we assume that matrix
parameter A and vector parameter b are provided, and also that the
"Gaussian noise" introduced by e_i and f_i are represented by normally
distributed vector processes with zero mean and known covariance
matrices R and Q, respectively.

A strong heuristic rationale for the discrete Kalman filter algorithm
could be given in terms of conditional probability and Bayesian
statistics, but we will instead focus on concrete formulation of our
method.  The method is analogous to the solution of a system of
ordinary differential equations by so-called "predictor-corrector"
approximations, where one alternately computes (predicts) the
"apriori" estimate v_i:

v_i = Aw_{i-1} + b

and then smoothes (corrects) this with the measured values u_i to
obtain the "aposteriori" estimate w_i:

w_i = v_i + K_i(u_i - v_i)

The former equation involves a "time update" since we apply the
"process model" to advance the computation in time from the "smoothed"
estimate w_{i-1} at the previous step to the "rough" estimate v_i at
the current step.

The latter equation takes "place" only in the current time step and
"imports" information (feedback) from the actual measured values u_i. 
But it introduces a previously unmentioned matrix K_i that is called
"the Kalman gain".

What is this Kalman gain, K_i?  From a conceptual viewpoint it is
determined by a requirement that the estimate w_i be "optimal" in a
minimum variance sense, but from an operational viewpoint one can
define it by certain "magic" equations that incorporate what we know
about the covariances R and Q of "noise" vectors e_i and f_i.  To make
a long story short we will recursively maintain (update) not only the
sequence K_i of matrices, but also a double sequence P_i, S_i of
"apriori" and "aposteriori" estimated error covariance matrices.

Therefore we back up and give this almost complete account of the
algorithm, first the "time update":

v_i = Aw_{i-1} + b

P_i = AS_{i-1}A' + Q (where A' denotes the transpose of A)

and then the "Kalman filter measurement update":

K_i = P_i(P_i + R)^-1

w_i = v_i + K_i(u_i - v_i)

S_i = (I - K_i)P_i

I say "almost complete account" because we must also provide a
mechanism for initializing the first values for w_0 and S_0.

This is somewhat a matter of art, closely related to the problem of
identifying system parameters A, b, R, and Q.  For simplicity one may
say that w_0 can be chosen as an "expected" value in some suitable
sense, and that in the long run the choice of S_0 should not be too
critical, so that one might take S_0 = I unless this turns out to
cause numerical instability.  In exact arithmetic a symmetric matrix
for S_0, as for covariance matrices R and Q, would yield P_i and S_i
symmetric for all time.

[We may mention in passing that where numerical stability is of
greatest concern, one uses instead of the above formula for S_i a
different expression, Joseph's formula, which better maintains the
symmetry of this sequence.]
Subject: Re: Kalman filter implementation
From: asiatechnicals-ga on 23 Feb 2003 18:36 PST
 
I was delighted to login this morning and to have your spreadsheet
waiting for me. I'm a little busy at work today, so I hope you don't
mind if I take a day or so to get my head round it, before asking any
questions.

I have to say that my first impressions are that it's doing all I
hoped it would. Wow, this is going to be the best Monday I had in a
while.

Google should use this as a case study.
Subject: Re: Kalman filter implementation
From: mathtalk-ga on 24 Feb 2003 08:34 PST
 
Thanks for the feedback.  If you post a request for clarification,
I'll be notified by Google Answers and will respond promptly.

Some areas I wondered if you would want clarification about:

- how the system parameters and initial values were selected

- how the spreadsheet is laid out & formulas implemented

- what the chart is actually displaying

- comments on the results of the calculations

regards, mathtalk

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy