Rao–Blackwellized particle filter

Use the conditionally linear-Gaussian model of Conditionally linear-Gaussian state-space model and a fixed observation path $y_{1:T}$. For each $0\le t\le T$, let ${\bar{P}}_t$ be the nonlinear path law generated by ${\mu }_0$ and the path-extension kernels from Nonlinear path extension is a probability kernel, and put $c_t(y_{1:t})={\int }_{{\mathsf{Z}}_{0:t}}{\prod }_{s=1}^t{\mathrm{\ell }}_s(z_{0:s};y_{1:s}){\bar{P}}_t(d{z}_{0:t}),c_0=1.$ Here ${\mathrm{\ell }}_s$ is the conditional observation density supplied by The Kalman filter is exact conditional on a nonlinear path. For the claim that the procedure targets the nonlinear filtering law at every prefix, assume $0<c_t(y_{1:t})<\mathrm{\infty }$ for every $t$; this is the finite-positive normalizer condition for the normalized Feynman–Kac target. The Kalman likelihood factorization identifies $c_t$ with the observation evidence density and the normalized path target with the exact conditional law of $Z_{0:t}$ given $Y_{1:t}=y_{1:t}$. The particle procedure itself uses finite positive per-particle likelihoods, so each of its empirical weight normalizers is finite positive. The particle state at time $t$ is the full nonlinear history $z_{0:t}$; finite products of the standard-Borel state spaces are standard Borel. Its transition appends a draw $z_t\sim M_t(z_{t-1},\cdot )$; the resulting path-extension probability kernel and standard-Borel path space are supplied by Nonlinear path extension is a probability kernel. Set the initial Feynman–Kac potential to $G_0\equiv 1$ and the time-$t$ potential to the conditional observation density $G_t(z_{0:t})={\mathrm{\ell }}_t(z_{0:t};y_{1:t})$ from The Kalman filter is exact conditional on a nonlinear path. Use the same path-extension kernel as target and proposal, so the initial and transition Radon–Nikodym weights are identically one. Run Sequential importance resampling for Feynman–Kac path targets with multinomial resampling to approximate the filtering law of the nonlinear path. Each particle stores alongside its path the conditional Gaussian moments of $U_t$.

Initialize $N\ge 1$ particles by drawing $z_0^i\sim {\mu }_0$ independently, setting $w_0^i=1\mathrm{/}N$, $m_{0\mathrm{\mid }0}^i=m_0(z_0^i)$, and $P_{0\mathrm{\mid }0}^i=P_0(z_0^i)$. For each $t=1,\dots ,T$:

1. Draw ancestor indices $J_t^1,\dots ,J_t^N$ independently with probabilities $(w_{t-1}^1,\dots ,w_{t-1}^N)$ and append independent transitions $z_t^i\sim M_t(z_{t-1}^{J_t^i},\cdot )$.
2. For each particle, abbreviate its appended path by $z_{0:t}^i$ and compute $m_{t\mathrm{\mid }t-1}^i=A_t(z_{0:t}^i)m_{t-1\mathrm{\mid }t-1}^{J_t^i},P_{t\mathrm{\mid }t-1}^i=A_t(z_{0:t}^i)P_{t-1\mathrm{\mid }t-1}^{J_t^i}{A}_t(z_{0:t}^i{)}^T+Q_t(z_{0:t}^i)\mathrm{.}$ Form $v_t^i=y_t-C_t(z_{0:t}^i)m_{t\mathrm{\mid }t-1}^i$ and $S_t^i=C_t(z_{0:t}^i)P_{t\mathrm{\mid }t-1}^i{C}_t(z_{0:t}^i{)}^T+R_t(z_{0:t}^i)$.
3. Set the incremental weight to the finite positive Gaussian density $a_t^i=(2\pi {)}^{-p_t\mathrm{/}2}\det (S_t^i{)}^{-1\mathrm{/}2}\exp \text{\hspace{0.17em}⁣}(-\frac{1}{2}(v_t^i{)}^T(S_t^i{)}^{-1}{v}_t^i),$ and normalize $w_t^i=a_t^i\mathrm{/}{\sum }_j{a}_t^j$.
4. Update the conditional Gaussian moments by $K_t^i=P_{t\mathrm{\mid }t-1}^i{C}_t(z_{0:t}^i{)}^T(S_t^i{)}^{-1},m_{t\mathrm{\mid }t}^i=m_{t\mathrm{\mid }t-1}^i+K_t^i{v}_t^i,P_{t\mathrm{\mid }t}^i=P_{t\mathrm{\mid }t-1}^i-K_t^i{S}_t^i(K_t^i{)}^T\mathrm{.}$

The procedure returns the weighted nonlinear particle paths and the Gaussian mixture ${\widehat{\pi }}_t^N(d{u}_t,d{z}_{0:t})={\sum }_{i=1}^N{w}_t^{i}N(d{u}_t;m_{t\mathrm{\mid }t}^i,P_{t\mathrm{\mid }t}^i){\delta }_{z_{0:t}^i}(d{z}_{0:t})\mathrm{.}$ Its conditional mean is ${\sum }_i{w}_t^i{m}_{t\mathrm{\mid }t}^i$ and its conditional covariance is ${\sum }_i{w}_t^i[P_{t\mathrm{\mid }t}^i+(m_{t\mathrm{\mid }t}^i-{\bar{m}}_t)(m_{t\mathrm{\mid }t}^i-{\bar{m}}_t{)}^T]$, where ${\bar{m}}_t={\sum }_i{w}_t^i{m}_{t\mathrm{\mid }t}^i$. These are moments of the finite mixture approximation; for finite $N$ the algorithm remains an approximation to the full nonlinear filter. It makes no general variance-reduction, convergence-rate, or long-time accuracy claim.

For every particle, $P_{t\mathrm{\mid }t-1}^i$ is positive semidefinite and $R_t(z_{0:t}^i)$ is positive definite, so $S_t^i$ is positive definite and the Kalman update and Gaussian density are defined. Conditional exactness of each Gaussian component is supplied by The Kalman filter is exact conditional on a nonlinear path. More precisely, each stored component is the conditional law of $U_t$ given its prefix $Z_{0:t}=z_{0:t}^i$ and $Y_{1:t}=y_{1:t}$. This follows by induction: at time zero it is the specified Gaussian law; at each later step the appended nonlinear transition is $M_t(z_{t-1},\cdot )$ and does not depend on $U_{t-1}$, so conditioning on the appended state does not change the parent Gaussian component, after which the Kalman prediction and observation update give the stated component. Equivalently, the Kalman lemma's conditional law given the full nonlinear path depends through time $t$ only on $z_{0:t}$; future nonlinear transitions are independent of $U_{0:t}$ and $Y_{1:t}$ given the prefix, depend only on the current nonlinear state, and integrate to one. Integrating over $z_{t+1:T}$ therefore leaves that same Gaussian law given the prefix. The mixture over nonlinear paths is still represented by finitely many particles.