Sparse grid-based likelihood evaluation for particle filtering

A novel Sparse Grid-Based Likelihood Evaluation (SGLE) method is proposed for the first time to reduce the number of Likelihood Evaluations (LE) of the Particle Filter (PF) and to decrease the overall computational cost. We use a sparse grid to identify clusters of sample points that have similar estimated values of likelihood, and take one LE for each cluster to approximate the likelihood of each sample points in the cluster. Then SGLE is incorporated to the standard particle filter to form a new posterior density estimation method called SGLE-PF. Performance analyses of precision and computational cost are given. We also give the condition under which SGLE-PF can actually reduce the LEs overhead. Then SGLE-PF was applied to a video target tracking task, and the experimental result shows that SGLE-PF can reduce a significant number of LEs without sacrificing estimation precision. Furthermore, SGLE can be easily incorporated with other PF variations or other methods incorporating Monte Carlo approach to approximate posterior probability density function.