

![0_image_0.png](0_image_0.png)

is high dimensional. Hence, too many particles may be needed to accurately represent the posterior.

Similar to the MCMC methods introduced in the previous section, efficiency can be improved by analytically integrating out z 0 :k and only sampling from γ 1 :k . In fact, this form of Rao-Blackwellization is reported to give superior results when compared to standard particle filtering where both γ and z are sampled jointly (Chen & Liu, 2000; Doucet et al., 200b). The improvement is perhaps not surprising, since importance sampling performs best when the sampled space is low dimensional.

The algorithm has an intuitive interpretation in terms of a randomized breadth first tree search procedure: at each new step k, we expand N kernels to obtain S × N new kernels.

Consequently, to avoid explosion in the number of branches, we select N out of S × N branches proportional to the likelihood, See Figure 3. The derivation and technical details of the algorithm are given in the Appendix C.

The tree search interpretation immediately suggests a deterministic version of the algorithm where one selects (without replacement) the N branches with highest weight. We will refer to this method as a greedy filter (GF). The method is also known as split-track filter (Chen & Liu, 2000) and is closely related to Multiple Hypothesis Tracking (MHT) (Bar-Shalom & Fortmann, 1988).  One problem with the greedy selection schema of GF is the loss of particle diversity. Even if the particles are initialized to different locations in zo,
(e.g., to different initial tempi), mainly due to the discrete nature of the state space of γ k ,
most of the particles become identical after a few steps k . Consequently, results can not be improved by increasing the number of particles N . Nevertheless, when only very few particles can be used, say e.g., in a real time application, GF may still be a viable choice.