An example of data filtering - Freie Universität

1 Providesa gentleintroductionto theKalman lter,a numericalmethod thatcanbe usedforsensorfusionor ,we considertheKalman lterfora thattheKalman lteris simplya linearweightedaverageoftwo ,we show thatthegeneralcasehasa similarstructureandthatthemathematicalfo rmulationis exampleof data filteringTheKalman lteris widelyusedin aeronauticsandengineeringfortwo mainpurposes:forcombiningmeasurements of thesamevariablesbutfromdi erentsensors,andforcombininganinexactfor ecastof a system'sstatewithaninexactmeasurement of lterhasalsoapplicationsin timeseriesof datapointsx1; x2; : : : ; xn, aforecastercom-putesthebestguessforthepo intxn+1.

2 Asmootherlooksback at thedata,andcomputesthebestpossiblexitaki nginto account thepoints beforeandafterxi. A lterprovidesa correctionforxn+1takinginto account allthepointsx1; x2; : : : ; xnandaninexactmeasurement ofxn+ a lteris thefollowing:Assumethatwe have a systemwhoseone-dimensionalstatewe canmeasureatsuccessive themeasurements arex1; x2; : : : ; xn. Ourtaskis to computetheaverage nof n=1nnX1xi:If a newpointxn+1is measured,we canrecompute n, butit is moree cient tousetheoldvalueof nandmake a smallcorrectionusingxn+1.

3 Thecorrectioniseasyto derive, since n+1=1n+ 1n+1X1xi=nn+ 1 1nnX1xi+1nxn+1!andso, n+1canbe writtenas( ) n+1=nn+ 1 +1n+ 1xn+1= +K(xn+1 )whereK= 1=(n+ 1).Kis n+1is aweightedaverageof theoldestimate nandthenewvaluexn+1. We trust nmorethanthesinglevaluexn+1; therefore,theweight of nis largerthantheweightofxn+1. alsoreadas statingthattheaverageis corrected12 RAUL ROJAS usingthedi erenceofxn+1andtheoldvalue n. ThegainKadjustshow canalsorecalculaterecursivelythequadrati cstandarddeviationof thetimeseries(thevariance).

4 Givennpoints,thequadraticstandarddeviati on nis givenby: 2n=1nnX1(xi )2:If a newpointxn+1is measured,thenewvarianceis 2n+1=1n+ 1n+1X1(xi n+1)2=1n+ 1n+1X1(xi n K(xn+1 n)2)whereKis thegainfactorde nedabove andwe canbe expandedas follows: 2n+1=1n+ 1"nX1(xi n)2+ 2 KnX1(xi n)(xn+1 n) +nK2(xn+1 n)2+ (1 K)2(xn+1 n)2#Thesecondterminsidethebracketsis zero,becausePn1(xi n) = 0. Therefore,thewholeexpressionreducesto 2n+1=1n+ 1(n 2n+ (xn+1 )2(nK2+ (1 K)2):SincenK2+ (1 K)2=nKthelastexpressionreducesto 2n+1=nn+ 1( 2n+K(xn+1 )2) = (1 K)( 2n+K(xn+1 )2):Thewholeprocesscannow be castedinto as a seriesof stepsto be followediteratively.)

5 Giventhe rstnpoints,andourcalculationof nand n, then Whena newpointxn+1is measured,we computethegainfactorK=1=(n+ 1). We computethenewestimationof theaverage n+1= n+K(xn+1 ) We computealsoa provisionalestimateof thenewstandarddeviation 02n= 2n+K(xn+1 )2 Finally, we ndthecorrect n+1usingthecorrection 2n+1= (1 K) 02nThiskindof iterative computationis usedin calculatorsforupdatingtheaverageandstand arddeviationof numbersenteredsequentiallyinto thecalculatorwithouthavingto iterative procedureshowsthegeneral avor of theKalman lter,which is a kindof recursive showedhow to updatea statisticalquantity thatwe aredealingwithtwo di erentinstruments thatprovidea readingforsomequantity of interestx.

6 We callx1thereadingfromthe rstinstrument know thatthe rstinstrument hasanerrormodelledby a Gaussianwithstan-darddeviation 1. Theerrorof thesecondinstrument is alsonormallydistributedaroundzerowithsta ndarddeviation 2. We wouldlike to combinebothreadingsinto a bothinstruments areequallygood ( 1= 2), we justtake theaverageof the rstinstrument is absolutelysuperior( 1<< 2), we willkeepx1as ourestimate,andviceversaif thesecondinstrument is clearlysuperiorto the any othercasewe wouldlike to forma weightedaverageof bothreadingsto generateanestimateofxwhich we call^ is which is isweightingeach readinginverselyproportionalto itsprecision,thatis,^x=x1 21+x2 221 21+1 22or simplifying^x=x1 22+x2 21 21+ 22 Thisestimationof ^xful estimatecanbe alsorewrittenas^x=x1+K(x2 x1)wherenow thegainK= 21=( 21+ 22).

7 Theupdateequationhasthesamegeneralformas in theexamplein is optimalgivenourstateof fromtheinstruments is a Gaussian,we canwritetheprobability ofxbeingtheright measurement asp1(x) =1p2 1e 12(x x1)2= 21forinstrument 1, andasp2(x) =1p2 2e 12(x x2)2= 22forinstrument the rstcase,x1is themostprobablemeasurement, in thesecond,x2, butallpointsxhave a non-vanishingprobability of beingtherightmeasurement dueto theinstruments' ROJASS incethetwo measurements areindependent we cancombinethembest,bymultiplyingtheirpro bability obtain:p(x) =p1(x)p2(x) =Ce 12(x x1)2= 21 12(x x2)2= 22whereCis a constant obtainedafterthemultiplication(including thenormalizationfactorneededforthenewGau ssian).

8 Theexpressionforp(x) canbe expandedintop(x) =Ce 12((x2 21 2xx1 21+x21 21)+(x2 22 2xx2 22+x22 22))which groupingsometermsreducestop(x) =Ce 12(x2(1 21+1 21) 2x(x1 21+x2 22))+DwhereDis a constant. Theexpressioncanbe rewrittenasp(x) =Ce 12( 21+ 22 21 22(x2 2x(x1 22+x2 21 21+ 22)))+D:Completingthesquarein theexponent we obtain:p(x) =F e 12 21+ 22 21 22 x (x1 22+x2 21) 21+ 22 2whereallconstants in theexponent (alsothosearisingfromcompletingthesquare )andin front of theexponentialfunctionhave beenabsorbedinto ,we seethatthemostprobableresult^xobtainedfr omcombiningthetwo measurements (thatis, thecenterof thedistribution)is^x=(x1 22+x2 21) 21+ 22andthevarianceof thecombinedresultis^ 2= 21 22 21+ 22If we introducea gainfactorK= 21=( 21+ 22) we canrewritethebestestimate^xof thestateas^x=x1+K(x2 x1)andthechangeto thevariance 21as^ = (1 K)

9 21 Thisis thegeneralformof theclassicalKalman notneedto be a measurement. It canbe a forecastof thesystemstate,witha variance 21, andx2canbe a measurement withtheerrorvariance 22. TheKalman lterwouldin thatcasecombinetheforecastwiththemeasure ment in orderto providethebestpossiblelinearcombinationo f bothasthe - uncorrelated dimensionsWe cangeneralizetheresultobtainedabove to thecaseof multipledimensions,wheneverydimensionis independent of each other,thatis, whenthereis nocor-relationbetweenthemeasurements obtainedforeach thatcasethemeasurementsx1andx2arevectors ,andwe thecaseof uncorrelateddimensions,given measurementsx1andx2( vectorsof dimensionn)

10 , thevariancesforeach dimensioncanbe arrangedin thediagonalof two matrices 1and 2, as follows: 1=2664 2110 00 212 000 00 0 21n3775and 2=2664 2210 00 222 000 00 0 22n3775where 21irepresents thevarianceof thei-thcoordinateforthe rstinstrument,and 22ithevarianceof givenby^x= ( 2x1+ 1x2)( 1+ 2) 1 IntroducingthegainK= 1( 1+ 2) 1, we canrewritetheexpressionabove as^x=x1+K(x2 x1)andthenewestimateof allvariancescanbe putin thediagonalof a matrix^ computedas^ = (I K) 1whereIis then nidentity 1and 2arethecovariancematricesforthetwo uncorrelateddimensions,thecovariancematr ixis thatthecovariancematrix formn-dimensionaldatapointsx1; x2; : : : ; xmis de nedas =1n(x1xT1+x2xT2+ +xmxTm) verysimilarto almostidentical,butnow we have to , we assumethatthetwoinstruments thatproducedthemhave a rstmea-surement is centeredatx1withcovariancematrix 1.