Log(Normal Thoughts)

Kalman Filter

2007-11-05T18:52:00.000-08:00

Kalman Filter

The purpose of this note is to give simple non technical introduction to Kalman filter.

Suppose we need to track position of the moving object. Our measurements can give us a position of this object with accuracy R. So every time we take a measurement we have

Xm = Xtrue + R

Where Xm is measured position, Xtrue is true position and R is measurement error. If there is no other source of information about this object then we should accept Xm as an estimate of the object position.

But suppose we know something about time object, for example the estimate of its previous position and the estimate of its velocity. By assuming that object velocity does not change we can estimate its position

Xmodel = Xprev + Velosity*dt + Q

Xmodel – an estimate of object position according to our model

Xprev – estimate of previous position

Q – model estimation error (we know that our model is not perfect)

The key idea of Kalman filter is to combine measurement and the model.

Xnext = Xmodel + K*(Xm - Xmodel)

This equation is basically linear combination of model prediction and measurement. If parameter K = 1 (called Kalman gain) then Xnext=Xm (i.e. we absolutely trust our measurements and don’t trust our model).

We choose value of K that minimizes variance (i.e. uncertainty) of Xnext

D[Xnext] = D[Xmodel]*(1-K)^2 + K^2*D[Xm]

D[x] – is variance or dispersion of x, D[x] = E[(x-E[x])^2] where E[x] – expectation of x.

From equations above we have:

D[Xm] = D[R]

D[Xmodel] = D[Xprev] + D[Q]

Minimum of D[Xnext] is achieved when K = D[Xmodel] / (D[Xmodel] + D[R])

(Note that D[Xmodel] = D[Xprev]+D[Q])

This agrees with our intuition, when there is no uncertainty about measurements D[R] = 0 that K = 1 and we completely ignore model prediction in computing an estimate for the Xnext.

Substituting the value of K into the equation for variance of Xnext we find:

D[Xnext] = (1-K) * D[Xprev]

Let’s put it all together. Kalman filters measurements based on the model predictions. In order to make it work we need to specify a model as well as accuracy of the model (Q) and measurements (R).

Specify R, Q, Xprev and D[Xprev] (Xprev and D[Xprev] are not critical since filter will automatically update these values),
Compute model prediction Xmodel
Take a measurement Xm
Compute Kalman gain K = (D[Xprev]+D[Q]) / (D[Xprev]+D[Q]+ D[R])
Correct measurement using model prediction Xnext = Xmodel + K*(Xm - Xmodel)
Compute D[Xnext] = (1-K) * D[Xprev]

If R=0 then filter absolutely trusts measurements and no adjustments will be made based on model predictions.

Even when Q=0 filter will not absolutely trust model since predicted value still contains an uncertainty of previous position.

Kalman, R. E. ( 1960). “A New Approach to Filtering and Prediction Problems.”

Transaction of the ASME Journal of Basic Engineering, 82(Series D), 35–45.

Building ATLAS 3.8.0 DLL on Windows.

2007-10-12T12:30:00.000-07:00

ATLAS (Automatically Tuned Linear Algebra Software), is a BLAS (Basic Linear Algebra Subprograms) library which is empirically optimized during installation specifically for the platform you are installing it on. Here I will describe how to build dynamic atlas library.

The BLAS is library of simple linear algebra routines that are used in more advanced libraries such as LAPACK. Using optimized BLAS library such as Atlas is very important since linear algebra operations can very slow. For example matrix multiplication using ATLAS is about 50 times faster than vanilla C# code.

Installation of Atlas on Linux is very straightforward, while installing it on Windows can be quite
challenging. Hopefully reading this will save you some time and make installation of Atlas easier.

Prerarations
First download and install Linux-like command line environment for Windows called Cygwin. In Cygwin command line enter the following commands (you current directory should contain Atlas tar archive):

gunzip -c atlas3.8.0.tar | tar xfm -
mv ATLAS ATLAS3.8.0
cd ATLAS3.8.0
mkdir WinNT
cd WinNT

These commands will extract atlas library and move it to the atlas3.8.0 folder. And also create a folder WinNT to store all files generated during installation.

Configuration

Before running configuration script, make sure that “IRunArchInfo_winnt” is defined in
ATLAS\CONFIG\src\Makefile

If it is not defined, then copy definition for “IRunArchInfo_linux” and rename linux to winnt
So it should look like this in ATLAS\CONFIG\src\Makefile:

IRunArchInfo_winnt: xarchinfo_winnt
- rm -f config0.out
$(MAKE) $(atlrun) atldir=$(mydir) exe=xarchinfo_winnt args="$(args)" \
redir=config0.out

Now you can run atlas configuration script by entering the following in cygwin command promt

../configure -b 32 -D c - -DPentiumCPS=2800 -Fa alg -fPIC --with-netlib-lapack={your LAPACK path}/lapack_LINUX.a

If you have 64bit CPU then instead of “-b 32” use “-b 64”. Specify your CPU frequency in Mhz for example if you have 2.8Ghz CPU then use “-DPentiumCPS=2800” . If you want to use LAPACK library with your atlas you should specify where your lapack library is located. For example in order to use lapack from "C:\Numlib\LAPACK_3.1.1\lapack_LINUX.a" you should use to following command line argument in atlas configuration script
“--with-netlib-lapack= /cygdrive/c/Numlib/LAPACK_3.1.1/lapack_LINUX.a”

Run configuration script.

Build
If configuration script completes without errors, try to make atlas library by entering:

make build

The build takes about 20-30 minutes. Since atlas will be running benchmarks on your computer as a part of installation process, close all applications (except cygwin) and do not use your computer while installation is running (this is important if you want to have a good Atlas library).

Check
After installation is complete you can check atlas library.

make check
make time

If check did not find any errors with your atlas library and you are happy with timings you can proceed to the next step of generating dynamic library.

Dynamic Library

Atlas static libraries are located in WinNT\lib folder, you will need them to build dynamic library.

Atlas provides a script that generates dynamic library (make shared) but this script does not work in cygwin environment (it did not work for me). So i wrote a script to create Atlas dynamic library that worked on my computer. You are welcome to use it and modify it in any way you want.

###########BASH SCRIPT: link.bash###########
#! /bin/bash
# base name of the DLL
AtlasName=my_atlas_library
# set names for specific output files

defname=exports.def
dllname=${AtlasName}.dll
gcclibname=${AtlasName}_gcc.lib

CLIBPATH=/cygdrive/c/cygwin/lib/mingw
CLIBPATH1=/cygdrive/c/cygwin/lib/gcc/i686-pc-mingw32/3.4.4
mingwclib="$CLIBPATH1/libg2c.a $CLIBPATH/libmoldname.a $CLIBPATH/libmsvcrt.a"

# Link Atlas DLL
echo 'Linking DLL and creating gcc import library...'

gcc -mno-cygwin -shared -o ${dllname} ${defname} \
liblapack.a libcblas.a libf77blas.a libatlas.a \
-Wl,--out-implib=${gcclibname} \
-Wl,--enable-auto-import \
-Wl,--no-whole-archive ${mingwclib}

###########EOF###########

Run this script by entering "./link.bash" in cygwin command window. ("./" before file name indicates that script is located in current folder)

exports.def – is the list of functions that you what to export. You can download it from http://www.dnanalytics.net/files/exports.def.

New Beginning

2007-10-09T05:41:00.000-07:00

I decided to create my personal blog to help me to remember all useful things that I learned while working as a fixed income quant on Wall Street.