# Particle filter: Evaluating Optimal importance density

NOTE I posted this in the math stack exchange but I realized this may be the more appropriate place, old post here. I'm not sure if I should delete one of them so I just linked them in both?

I am reading about particle filtering and I am having a hard time understanding the importance density step. I understand the necessity but can't quite understand the optimal proposal density, I'll introduce an example below. The math regarding the proposal density stuff comes from Beyond the Kalman Filter: Particle Filters for Tracking Applications

Assuming a state space model $$x_{k+1} = f(x_{k}, u_k, w_k)$$ $$y_k = H x_k + v_k$$ where the measurement function is assumed linear and Gaussian and the state transition is not necessarily linear nor Gaussian. In this case the optimal proposal density $$q(x_k|x_{k-1}^i,z_k)=p(x_k|x_{k-1},z_k)$$ is possible. With this the weight update becomes $$w_k^i \propto w_{k-1}^i p(z_k|x_{k-1}^i)$$ I am not sure how to evaluate this.

I would imagine that it would look like this in a pseudo-code example

initialize pf
for i=1:num_time
% measurement update
residual = meas-H*particles
w = normpdf(residual, 0, meas_noise) % multivariate gaussian, 0 mean and meas_noise covariance
w = w/sum(w)

% importance sampling
if (1/sum(w^2)<0.5*num_particles)
resample

% sample from transitional
particles = state_trans_fcn(particles, input)


Because as far as I understand sampling from the transitional prior $$x^i_k \sim p(x_k|x_{k-1})$$ is just applying the mapping $$f$$ to the particle cloud. Calculating the measurement likelihood $$p(z_k|x_{k-1}^i)$$ is what really confuses me, because the calculation in the pseudo-code to me feels more like the calculation of $$p(x_k|z_k)$$?

• Please remove one of the two questions, more likely the one on math exchange. Jan 3, 2020 at 21:23
• Okay I'll remove that one. Jan 4, 2020 at 1:03

You're mistaken about a few things (and that's okay!).

In this case the optimal proposal density...is [available].

I believe this is only true if $$f$$, the state transition is Gaussian. It can be nonlinear, which precludes closed-form Kalman filtering, but it must be Gaussian to exploit Gaussian-Gaussian conjugacy. In this case, the proposal $$p(x_k|x_{k-1},z_k) \propto f(x_k \mid x_{k-1})p(z_k \mid x_k) .$$ You can derive that this is Gaussian using standard Bayesian techniques related to identifying conjugate distributions. In this case, the multiplicative adjustment to the weights are not even functions of the current samples you're simulating because there will be significant cancellations in the numerator and the denominator of the importance weight adjustment.

Because as far as I understand sampling from the transitional prior...

You aren't sampling from the state transition prior. That algorithm would be called the bootstrap filter. There, the importance weight updates would be functions of your current samples, and so they would end up having higher variance. The upside to this algorithm is that the weight updates would only require that you can evaluate the observation density. This would be handy for when you cannot evaluate the state transition density (but you can sample from it). Different algorithm, though.

Calculating the measurement likelihood $$p(z_k \mid x_{k-1})$$ is what really confuses me

That is not the measurement density! You are conditioning on the previous time's state, not the current state! This is only evaluate-able if you derive it by solving the following integral:

$$p(z_k \mid x_{k-1}) = \int \underbrace{p(z_k \mid x_{k})}_{\text{observation density}} \underbrace{f(x_k \mid x_{k-1})}_{\text{state transition}} dx_k.$$

By the way, this example is discussed in Inference in Hidden Markov Models on page 220/221.

• I am confused about your explanation regarding the transitional prior. The reason I suggested was because the book Beyond the Kalman Filter: Particle Filters for Tracking Applications introduces it as the most common suboptimal proposal density. For argument sake, if we assume that the process noise cannot be assumed to be Gaussian this would be a potential candidate for the proposal distribution. This would lead to the weight update equation: $w_k^i \propto w_{k-1}^i p(z_k|x_k^i)$. Jan 4, 2020 at 1:07
• So in short I am still kind of uncertain how to evaluate each of the two weight updates. It looks as though $p(z_k|x_{k-1}^i) = \int p(z_k|x_{k}^i) f(x_k|x_{k-1}^i)$ (I think you made a typo?). Does this then mean that evaluating the measurement with respect to the particles, normpdf(meas-particles,0,meas_noise), on a multivariate Gaussian, like in the pseudo-code, is how one would calculate $p(z_k|x_k^i)$? Jan 4, 2020 at 1:10
• I can't edit my previous comment, but to keep things are clear as possible I should have wrote normpdf(particles,meas,meas_noise) to clarify that the $\mu=\text{meas}$ and $\Sigma=\text{meas_noise}$ when evaluating the multivariate normal as here. Jan 4, 2020 at 1:20
• Regarding your first comment, yes that’s correct. If you’re proposal is the same distribution as he state transition, then you only need to evaluate the normal observation density on each sample. Regarding your second, yes, that’s a typo. Thank you. It’s now corrected :) Jan 4, 2020 at 1:35
• If using the transitional prior as proposal density could one still call it an SIS PF, or is it most accurately then referred to as boostrap? Also assuming Gaussian measurement with noise $R$, is $p(z_k|x_k^i) = normpdf(x_k^i, z_k, R)$ true? Jan 4, 2020 at 1:41