1、Comparative survey on non linear filtering methods : the quantization and the particle filtering approaches Afef SELLAMI,Chang Young Kim,Overview,Introduction Bayes filters Quantization based filters Zero order scheme First order schemes Particle filters Sequential importance sampling (SIS) filter S
2、ampling-Importance Resampling(SIR) filter Comparison of two approaches Summary,Non linear filter estimators,Quantization based filters Zero order scheme First order schemesParticle filtering algorithms: Sequential importance sampling (SIS) filter Sampling-Importance Resampling(SIR) filter,Overview,I
3、ntroduction 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
4、 all measurements.PredictionCorrection,Bayes Filter,One step transition bayes filter equationBy introducint the operaters , sequential definition of the unnormalized filter nForward Expression,Bayes Filter,Overview,Introduction Bayes filters Quantization based filters Zero order scheme First order s
5、chemes Particle filters Sequential importance sampling (SIS) filter Sampling-Importance Resampling(SIR) filter Comparison of two approaches Summary,Quantization based filters,Zero order scheme First order schemes One step recursive first order scheme Two step recursive first order scheme,Zero order
6、scheme,QuantizationSequential definition of the unnormalized filter nForward Expression,Zero order scheme,Recalling Taylor Series,Lets call our point x0 and lets define a new variable that simply measures how far we are from x0 ; call the variable h = x x0. Taylor Series formulaFirst Order Approxima
7、tion:,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 byOne step recursive scheme based on a recursive definition of the differ
8、ential term estimator.Two step recursive scheme based on an integration by part transformation of conditional expectation derivative.,First order schemes,One step recursive scheme,The recursive definition of the differential term estimatorForward Expression,Two step recursive scheme,An integration b
9、y part formulawherewhere,Comparisons of convergence rate,Zero order schemeFirst order schemes One step recursive first order schemeTwo step recursive first order scheme,Overview,Introduction Bayes filters Quantization based filters Zero order scheme First order schemes Particle filters Sequential im
10、portance sampling (SIS) filter Sampling-Importance Resampling(SIR) filter Comparison of two approaches Summary,Particle filtering,Consists of two basic elements: Monte Carlo integrationImportance sampling,Importance sampling,Proposal distribution: easy to sample from,Original distribution: hard to s
11、ample from, easy to evaluate,Importance weights,we want samples fromand make the following importance sampling identifications,Sequential importance sampling (SIS) filter,Proposal distribution,Distribution from which we want to sample,SIS Filter Algorithm,Sampling-Importance Resampling(SIR),Problems
12、 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,Sampling-Importance Resampling(SIR),x,Sensor model,Update,Resamp
13、ling,Prediction,Overview,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,Elements for a comparison,Complexity Numer
14、ical performances in three state models: Kalman filter (KF) Canonical stochastic volatility model (SVM) Explicit non linear filter,Complexity comparison,Numerical performances,Three models chosen to make up the benchmark. Kalman filter (KF) Canonical stochastic volatility model (SVM) Explicit non li
15、near filter,Kalman 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 discretizati
16、on of a continuous diffusion model.State Model,Explicit non linear filter,A non linear non Gaussian state equation Serial Gaussian distributions SG()State Model,Numerical performance Results,Convergence teststhree test functions:Kalman filter: d=1,Numerical performance Results : Convergence rate imp
17、rovement,Kalman filter: d=3,Numerical performance Results,Stochastic volatility model,Numerical performance Results,Non linear explicit filter,Conclusions,Particle methods do not suffer from dimension dependency when considering their theoretical convergence rate, whereas quantization based methods
18、do depend on the dimension of the state space. Considering the theoretical convergence results, quantization methods are still competitive till dimension 2 for zero order schemes and till dimension 4 for first order ones. Quantization methods need smaller grid sizes than Monte Carlo methods to attain convergence regions,
