Particle filter efficiency under limited communication

• 成果类型: Article
• 署名作者: Sen, Deborshee
• 署名单位: University of Bath
• 刊物名称: BIOMETRIKA
• ISSN/ISSBN: 0006-3444
• DOI: 10.1093/biomet/asac015
• 发表日期: 2022
• 页码: 921935
• 关键词: hidden markov-models; MONTE-CARLO METHODS; parallel implementation; resampling algorithms; STABILITY; CONVERGENCE; PROOF; time

摘要

Sequential Monte Carlo methods are typically not straightforward to implement on parallel architectures. This is because standard resampling schemes involve communication between all particles. The alpha-sequential Monte Carlo method was proposed recently as a potential solution to this that limits communication between particles. This limited communication is controlled through a sequence of stochastic matrices known as alpha matrices. We study the influence of the communication structure on the convergence and stability properties of the resulting algorithms. In particular, we quantitatively show that the mixing properties of the alpha matrices play an important role in the stability properties of the algorithm. Moreover, we prove that one can ensure good mixing properties by using randomized communication structures where each particle only communicates with a few neighbouring particles. The resulting algorithms converge at the usual Monte Carlo rate. This leads to efficient versions of distributed sequential Monte Carlo.