Premium
Parallelizing particle filters with butterfly interactions
Author(s) -
Heine Kari,
Whiteley Nick,
Cemgil A.Taylan
Publication year - 2020
Publication title -
scandinavian journal of statistics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.359
H-Index - 65
eISSN - 1467-9469
pISSN - 0303-6898
DOI - 10.1111/sjos.12408
Subject(s) - particle filter , resampling , stability (learning theory) , computer science , consistency (knowledge bases) , convergence (economics) , inference , pairwise comparison , monte carlo method , algorithm , term (time) , markov chain monte carlo , scheme (mathematics) , mathematical optimization , mathematics , filter (signal processing) , artificial intelligence , machine learning , statistics , physics , quantum mechanics , economics , computer vision , economic growth , mathematical analysis
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.