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
