Particle filters and resampling techniques: Importance in computational complexity analysis

Abstract

The huge computational complexities involved with particle filters is known to be one of the major constraint to their widespread use for different real time applications. This paper analyzes the computational complexities of the sampling, importance weight and resampling steps for the two most popular types of particle filters; generic particle filter and regularized particle filter (RPF). In the resampling step, different types of resampling methods are considered. From experiments, the importance weight step is found to be the most computational intensive part and RPF showed a relatively higher complexity to the generic particle filter. Among the resampling methods considered, Independent Metropolis Hastings Algorithm (IMHA) resampling resulted in the lowest computational complexity followed by systematic, stratified, residual and multinomial resampling algorithms. In addition to the computational complexities, the performance of the algorithms is also considered by using the most common root mean squared error (RMSE) metrics. The results obtained are of importance in the study of accelerating the algorithm in a hardware based platform and to be applied in real time problems.