Parallelizing particle filters with butterfly interactions

Kari Heine, Nick Whiteley, Ali Taylan Cemgil

Research output: Contribution to journalArticle

Abstract

The bootstrap particle filter (BPF) is the cornerstone of many algorithms used for solving generally intractable inference problems with hidden Markov models. The long-term stability of the BPF arises from particle interactions that typically make parallel implementations of the BPF nontrivial. We propose a method whereby particle interaction is done in several stages. With the proposed method, full interaction can be accomplished even if we allow only pairwise communications between processing elements at each stage. We show that our method preserves the consistency and the long-term stability of the BPF, although our analysis suggests that the constraints on the stagewise interactions introduce errors leading to a lower convergence rate than standard Monte Carlo. The proposed method also suggests a new, more flexible, adaptive resampling scheme, which, according to our numerical experiments, is the method of choice, displaying a notable gain in efficiency in certain parallel computing scenarios.

Original languageEnglish
Pages (from-to)1-36
Number of pages36
JournalScandinavian Journal of Statistics
Early online date16 Aug 2019
DOIs
Publication statusE-pub ahead of print - 16 Aug 2019

Keywords

  • hidden Markov model
  • parallelism
  • particle filter
  • particle interaction
  • sequential Monte Carlo

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Cite this