Bootstrap Filter

What is a Bootstrap Filter?

A Bootstrap Filter is the most basic form of Particle Filter, introduced by Gordon, Salmond, and Smith in 1993. It’s used to estimate the hidden state of a dynamic system when the system is nonlinear and/or the noise is non-Gaussian.

Key Concepts

• State-space model:
  You have a hidden (latent) state xtx_txt​ that evolves over time and observations yty_tyt​ that are noisy functions of the state.

• Transition model:
  xt∼p(xt∣xt−1)x_t \sim p(x_t \mid x_{t-1})xt​∼p(xt​∣xt−1​)

• Observation model:
  yt∼p(yt∣xt)y_t \sim p(y_t \mid x_t)yt​∼p(yt​∣xt​)

Bootstrap Filter Algorithm (Step-by-Step)

At each time step $t$, given a set of particles {xt−1(i)}i=1N\{x_{t-1}^{(i)}\}_{i=1}^N{xt−1(i)​}i=1N​:

1. Resampling:
   Resample particles xt−1(i)x_{t-1}^{(i)}xt−1(i)​ based on their weights wt−1(i)w_{t-1}^{(i)}wt−1(i)​ to get xt−1∗(i)x_{t-1}^{*(i)}xt−1∗(i)​

2. Propagation:
   Sample new particles from the transition model:
   xt(i)∼p(xt∣xt−1∗(i))x_t^{(i)} \sim p(x_t \mid x_{t-1}^{*(i)})xt(i)​∼p(xt​∣xt−1∗(i)​)

3. Weighting:
   Compute importance weights based on the likelihood of the observation:
   wt(i)∝p(yt∣xt(i))w_t^{(i)} \propto p(y_t \mid x_t^{(i)})wt(i)​∝p(yt​∣xt(i)​)

4. Normalization:
   Normalize the weights so they sum to 1.

5. Estimate (optional):
   Use the weighted particles to estimate the posterior:
   p(xt∣y1:t)≈∑wt(i)δ(xt−xt(i))p(x_t \mid y_{1:t}) \approx \sum w_t^{(i)} \delta(x_t – x_t^{(i)})p(xt​∣y1:t​)≈∑wt(i)​δ(xt​−xt(i)​)

✅ Pros

• Simple and flexible

• Handles nonlinear and non-Gaussian systems

❌ Cons

• Can suffer from weight degeneracy (most weights become zero)

• May require many particles for good performance

Use Cases

• Object tracking (e.g., radar, computer vision)

• Econometrics (hidden Markov models)

• Robotics (localization and SLAM)