Parallelising Particle Filters with Butterfly Interactions

Kari Heine, Nick Whiteley, A. Taylan Cemgil

Research output: Contribution to journalArticle (Academic Journal)peer-review

1 Citation (Scopus)


Bootstrap particle filter (BPF) is the corner stone of many popular algorithms used for solving inference problems involving time series that are observed through noisy measurements in a non-linear and non-Gaussian context. The long term stability of BPF arises from particle interactions which in the context of modern parallel computing systems typically means that particle information needs to be communicated between processing elements, which makes parallel implementation of BPF nontrivial. In this paper we show that it is possible to constrain the interactions in a way which, under some assumptions, enables the reduction of the cost of communicating the particle information while still preserving the consistency and the long term stability of the BPF. Numerical experiments demonstrate that although the imposed constraints introduce additional error, the proposed method shows potential to be the method of choice in certain settings.
Original languageUndefined/Unknown
JournalScandinavian Journal of Statistics
Early online date16 Aug 2019
Publication statusE-pub ahead of print - 16 Aug 2019

Bibliographical note

35 pages, 4 figures


  • stat.CO

Cite this