Comparative survey on non linear filtering methods : the quantization and the particle filtering approaches Afef SELLAMIOverviewNon linear filter estimatorsSlide 4Bayes FilterSlide 6Slide 7Quantization based filtersZero order schemeSlide 10Recalling Taylor SeriesFirst order schemesOne step recursive schemeSlide 14Two step recursive schemeSlide 16Comparisons of convergence rateSlide 18Particle filteringImportance samplingSequential importance sampling (SIS) filterSIS Filter AlgorithmSampling-Importance Resampling(SIR)Slide 24Slide 25Elements for a comparisonComplexity comparisonNumerical performancesKalman filter (KF)Canonical stochastic volatility model (SVM)Explicit non linear filterNumerical performance ResultsNumerical performance Results : Convergence rate improvementSlide 34Slide 35ConclusionsComparative survey on non linear filtering methods : thequantization and the particle filtering approachesAfef SELLAMIChang Young KimOverviewIntroductionBayes filtersQuantization based filtersZero order schemeFirst order schemesParticle filtersSequential importance sampling (SIS) filterSampling-Importance Resampling(SIR) filterComparison of two approachesSummaryNon linear filter estimatorsQuantization based filtersZero order schemeFirst order schemesParticle filtering algorithms:Sequential importance sampling (SIS) filterSampling-Importance Resampling(SIR) filterOverviewIntroductionBayes filtersQuantization based filtersZero order schemeFirst order schemesParticle filtersSequential importance sampling (SIS) filterSampling-Importance Resampling(SIR) filterComparison of two approachesSummaryBayesian approach: We attempt to construct the πnf of the state given all measurements.PredictionCorrectionBayes FilterOne step transition bayes filter equationBy introducint the operaters , sequential definition of the unnormalized filter πnForward ExpressionBayes FilterOverviewIntroductionBayes filtersQuantization based filtersZero order schemeFirst order schemesParticle filtersSequential importance sampling (SIS) filterSampling-Importance Resampling(SIR) filterComparison of two approachesSummaryQuantization based filtersZero order schemeFirst order schemesOne step recursive first order schemeTwo step recursive first order schemeZero order schemeQuantizationSequential definition of the unnormalized filter πnForward ExpressionZero order schemeRecalling Taylor Series Let's call our point x0 and let's define a new variable that simply measures how far we are from x0 ; call the variable h = x –x0.Taylor Series formulaFirst Order Approximation:Introduce first order schemes to improve the convergence rate of the zero order schemes.Rewriting the sequential definition by mimicking some first order Taylor expansion:Two schemes based on the different approximation by One step recursive scheme based on a recursive definition of the differential term estimator. Two step recursive scheme based on an integration by part transformation of conditional expectation derivative.First order schemesOne step recursive schemeThe recursive definition of the differential term estimatorForward ExpressionTwo step recursive schemeAn integration by part formulawherewhereComparisons of convergence rateZero order schemeFirst order schemesOne step recursive first order schemeTwo step recursive first order schemeOverviewIntroductionBayes filtersQuantization based filtersZero order schemeFirst order schemesParticle filtersSequential importance sampling (SIS) filterSampling-Importance Resampling(SIR) filterComparison of two approachesSummaryParticle filteringConsists of two basic elements:Monte Carlo integrationImportance samplinglimL ! 1LX`=1w`f(x`) =Zf(x )p(x)dxp(x) ¼LX`=1w`±x`Importance samplingProposal distribution: easy to sample from Original distribution: hard to sample from, easy to evaluate Ex[ f (x)] =Zp(x)f (x)dx=Zp(x)q(x)f(x)q(x)dx¼1LLX`=1p(x`)q(x`)f(x`)Importanceweights x`» q(¢)wl=p(x`)q(x`)we want samples fromand make the following importance sampling identificationsSequential importance sampling (SIS) filterProposal distribution Distribution from which we want to sample1 1 1( ) ( | ) ( | ) ( )t t t t t t tBel x p y x p x x Bel x dxh- - -=�1 1( ) ( | ) ( )t t tq x p x x Bel x- -=( ) ( )tp x Bel x=draw xit1 from Bel(xt1)draw xit from p(xt | xit1)Importance factor for xit:1 11 1( )( )( | ) ( | ) ( )( | ) ( )( | )itt t t t tt t tt tp xwq xp y x p x x Bel xp x x Bel xp y xh- -- -==�1 1 1( ) ( | ) ( | ) ( )t t t t t t tBel x p y x p x x Bel x dxh- - -=�SIS Filter AlgorithmSampling-Importance Resampling(SIR)Problems of SIS:Weight DegenerationSolution  RESAMPLINGResampling eliminates samples with low importance weights and multiply samples with high importance weightsReplicate particles when the effective number of particles is below a threshold 211( )effnikiNw==�Sampling-Importance Resampling(SIR)( )111,nikixn-=� �� ��x{ }( ) ( )1,ni ik kix w=( )111,nikixn+=� �� ��{ }( ) ( )1 11,ni ik kix w+ +=( )211,nikixn+=� �� ��Sensor modelUpdateResamplingPredictionOverviewIntroductionBayes filtersQuantization based filtersZero order schemeFirst order schemesParticle filtersSequential importance sampling (SIS) filterSampling-Importance Resampling(SIR) filterComparison of two approachesSummaryElements for a comparisonComplexityNumerical performances in three state models:Kalman filter (KF)Canonical stochastic volatility model (SVM)Explicit non linear filterComplexity comparisonZero order schemeC0N2One step recursive first order schemeC1N2d3Two step recursive first order schemeC2N2dSIS particle filterC3NSIR particle filterC4NNumerical performances Three models chosen to make up the benchmark.Kalman filter (KF)Canonical stochastic volatility model (SVM)Explicit non linear filterKalman filter (KF)Both signal and observation equations are linear with Gaussian independent noises.Gaussian process which parameters (the two first moments) can be computed sequentially by a deterministic algorithm (KF)Canonical stochastic volatility model (SVM)The time discretization of a continuous diffusion model.State ModelExplicit non