{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,30]],"date-time":"2022-11-30T05:57:52Z","timestamp":1669787872866},"reference-count":42,"publisher":"Oxford University Press (OUP)","issue":"4","license":[{"start":{"date-parts":[[2022,2,24]],"date-time":"2022-02-24T00:00:00Z","timestamp":1645660800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022,11,29]]},"abstract":"<jats:title>Summary<\/jats:title>\n               <jats:p>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.<\/jats:p>","DOI":"10.1093\/biomet\/asac015","type":"journal-article","created":{"date-parts":[[2022,2,22]],"date-time":"2022-02-22T20:15:39Z","timestamp":1645560939000},"page":"921-935","source":"Crossref","is-referenced-by-count":0,"title":["Particle filter efficiency under limited communication"],"prefix":"10.1093","volume":"109","author":[{"given":"Deborshee","family":"Sen","sequence":"first","affiliation":[{"name":"Department of Mathematical Sciences, University of Bath , Claverton Down, Bath BA2 7AY, U.K"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2022,2,24]]},"reference":[{"key":"2022112917593154600_B1","first-page":"1044","article-title":"Distributed stochastic gradient MCMC","author":"Ahn,","year":"2014","journal-title":"Proc. 31st Int. Conf. Machine Learning"},{"key":"2022112917593154600_B2","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/BF02579166","article-title":"Eigenvalues and expanders","volume":"6","author":"Alon,","year":"1986","journal-title":"Combinatorica"},{"key":"2022112917593154600_B3","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1111\/j.1467-9868.2009.00736.x","article-title":"Particle Markov chain Monte Carlo methods","volume":"72","author":"Andrieu,","year":"2010","journal-title":"J. R. Statist. Soc."},{"key":"2022112917593154600_B4","doi-asserted-by":"crossref","first-page":"697","DOI":"10.1214\/07-AOS574","article-title":"The pseudo-marginal approach for efficient Monte Carlo computations","volume":"37","author":"Andrieu,","year":"2009","journal-title":"Ann. Statist."},{"key":"2022112917593154600_B5","doi-asserted-by":"crossref","first-page":"1396","DOI":"10.1214\/13-AAP951","article-title":"On the stability of sequential Monte Carlo methods in high dimensions","volume":"24","author":"Beskos,","year":"2014","journal-title":"Ann. Appl. Prob."},{"key":"2022112917593154600_B6","doi-asserted-by":"crossref","first-page":"2442","DOI":"10.1109\/TSP.2005.849185","article-title":"Resampling algorithms and architectures for distributed particle filters","volume":"53","author":"Bolic,","year":"2005","journal-title":"IEEE Trans. Sig. Proces."},{"key":"2022112917593154600_B7","doi-asserted-by":"crossref","first-page":"2877","DOI":"10.1214\/13-AOS1172","article-title":"A general theory of particle filters in hidden Markov models and some applications","volume":"41","author":"Chan,","year":"2013","journal-title":"Ann. Statist."},{"key":"2022112917593154600_B8","doi-asserted-by":"crossref","first-page":"2385","DOI":"10.1214\/009053604000000698","article-title":"Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference","volume":"32","author":"Chopin,","year":"2004","journal-title":"Ann. Statist."},{"key":"2022112917593154600_B9","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1111\/j.1467-9868.2012.01046.x","article-title":"SMC2: an efficient algorithm for sequential analysis of state space models","volume":"75","author":"Chopin,","year":"2013","journal-title":"J. R. Statist. Soc."},{"key":"2022112917593154600_B10","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/S0246-0203(00)01064-5","article-title":"On the stability of interacting processes with applications to filtering and genetic algorithms","volume":"37","author":"Del Moral,","year":"2001","journal-title":"Ann. Inst. Henri Poincar\u00e9"},{"key":"2022112917593154600_B11","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1287\/15-SSY190","article-title":"Convergence properties of weighted particle islands with application to the double bootstrap algorithm","volume":"6","author":"Del Moral,","year":"2017","journal-title":"Stoch. Syst."},{"key":"2022112917593154600_B12","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780199641178.001.0001","article-title":"Time Series Analysis by State Space Methods","volume-title":"Oxford Statist. Sci. Ser.","author":"Durbin,","year":"2012"},{"key":"2022112917593154600_B13","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1214\/13-BA814","article-title":"An adaptive sequential Monte Carlo sampler","volume":"8","author":"Fearnhead,","year":"2013","journal-title":"Bayesian Anal."},{"key":"2022112917593154600_B14","doi-asserted-by":"crossref","DOI":"10.1090\/memo\/0910","volume-title":"A Proof of Alon\u2019s Second Eigenvalue Conjecture and Related Problems","author":"Friedman,","year":"2008"},{"key":"2022112917593154600_B15","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1049\/ip-f-2.1993.0015","article-title":"Novel approach to nonlinear\/non-Gaussian Bayesian state estimation","volume":"140","author":"Gordon,","year":"1993","journal-title":"IEE Proc. Radar Sig. Proces."},{"key":"2022112917593154600_B16","doi-asserted-by":"crossref","first-page":"20180084","DOI":"10.1098\/rsif.2018.0084","article-title":"Understanding the ontogeny of foraging behaviour: insights from combining marine predator bio-logging with satellite-derived oceanography in hidden Markov models","volume":"15","author":"Grecian,","year":"2018","journal-title":"J. R. Soc. Interface"},{"key":"2022112917593154600_B17","first-page":"11","article-title":"Exploring network structure, dynamics, and function using NetworkX","volume-title":"Proc. 7th Python Sci. Conf. (SciPy2008)","author":"Hagberg,","year":"2008"},{"key":"2022112917593154600_B18","doi-asserted-by":"crossref","first-page":"2508","DOI":"10.1016\/j.spa.2016.11.003","article-title":"Fluctuations, stability and instability of a distributed particle filter with local exchange","volume":"127","author":"Heine,","year":"2017","journal-title":"Stoch. Proces. Appl."},{"key":"2022112917593154600_B19","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1111\/sjos.12408","article-title":"Parallelizing particle filters with butterfly interactions","volume":"47","author":"Heine,","year":"2020","journal-title":"Scand. J. Statist."},{"key":"2022112917593154600_B20","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1093\/biomet\/asy074","article-title":"Unbiased Hamiltonian Monte Carlo with couplings","volume":"106","author":"Heng,","year":"2019","journal-title":"Biometrika"},{"key":"2022112917593154600_B21","doi-asserted-by":"crossref","first-page":"6711","DOI":"10.1118\/1.4934372","article-title":"Ultrasonic tracking of shear waves using a particle filter","volume":"42","author":"Ingle,","year":"2015","journal-title":"Med. Phys."},{"key":"2022112917593154600_B22","doi-asserted-by":"crossref","first-page":"218","DOI":"10.1016\/j.eswa.2017.07.019","article-title":"Opinion mining using ensemble text hidden Markov models for text classification","volume":"94","author":"Kang,","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"2022112917593154600_B23","doi-asserted-by":"crossref","first-page":"230","DOI":"10.1002\/sam.11280","article-title":"Forest resampling for distributed sequential Monte Carlo","volume":"9","author":"Lee,","year":"2016","journal-title":"Statist. Anal. Data Mining"},{"key":"2022112917593154600_B24","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1093\/biomet\/asy028","article-title":"Variance estimation in the particle filter","volume":"105","author":"Lee,","year":"2018","journal-title":"Biometrika"},{"key":"2022112917593154600_B25","doi-asserted-by":"crossref","first-page":"665","DOI":"10.1093\/biomet\/asx033","article-title":"Simple, scalable and accurate posterior interval estimation","volume":"104","author":"Li,","year":"2017","journal-title":"Biometrika"},{"key":"2022112917593154600_B26","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1080\/01621459.1995.10476549","article-title":"Blind deconvolution via sequential imputations","volume":"90","author":"Liu,","year":"1995","journal-title":"J. Am. Statist. Assoc."},{"key":"2022112917593154600_B27","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1175\/1520-0469(1963)020<0130:DNF>2.0.CO;2","article-title":"Deterministic nonperiodic flow","volume":"20","author":"Lorenz,","year":"1963","journal-title":"J. Atmosph. Sci."},{"key":"2022112917593154600_B28","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/s11265-011-0601-2","article-title":"Algorithm and parallel implementation of particle filtering and its use in waveform-agile sensing","volume":"65","author":"Miao,","year":"2011","journal-title":"J. Sig. Proces. Syst."},{"key":"2022112917593154600_B29","doi-asserted-by":"crossref","first-page":"1308","DOI":"10.1111\/2041-210X.12578","article-title":"moveHMM: an R package for the statistical modelling of animal movement data using hidden Markov models","volume":"7","author":"Michelot,","year":"2016","journal-title":"Meth. Ecol. Evolution"},{"key":"2022112917593154600_B30","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1109\/SAM.2014.6882385","article-title":"On the uniform asymptotic convergence of a distributed particle filter","volume-title":"2014 IEEE 8th Sensor Array and Multichannel Sig. Proces. Workshop (SAM)","author":"M\u00edguez,","year":"2014"},{"key":"2022112917593154600_B31","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1016\/j.sigpro.2015.11.015","article-title":"A proof of uniform convergence over time for a distributed particle filter","volume":"122","author":"M\u00edguez,","year":"2016","journal-title":"Sig. Proces."},{"key":"2022112917593154600_B32","article-title":"GPU acceleration of the particle filter: the Metropolis resampler","author":"Murray,","year":"2012","journal-title":"arXiv: 1202.6163v1"},{"key":"2022112917593154600_B33","doi-asserted-by":"crossref","first-page":"789","DOI":"10.1080\/10618600.2015.1062015","article-title":"Parallel resampling in the particle filter","volume":"25","author":"Murray,","year":"2016","journal-title":"J. Comp. Graph. Statist."},{"key":"2022112917593154600_B34","doi-asserted-by":"crossref","first-page":"989","DOI":"10.1002\/for.2447","article-title":"Long memory of financial time series and hidden Markov models with time-varying parameters","volume":"36","author":"Nystrup,","year":"2017","journal-title":"J. Forecasting"},{"key":"2022112917593154600_B35","article-title":"Scalable Bayesian inference for time series via divide-and-conquer","author":"Ou,","year":"2021","journal-title":"arXiv: 2106.11043v2"},{"key":"2022112917593154600_B36","doi-asserted-by":"publisher","DOI":"10.1155\/2017\/8180272","article-title":"Predicting social unrest events with hidden Markov models using GDELT","author":"Qiao,","year":"2017","journal-title":"Discrete Dynam. Nature Soc."},{"key":"2022112917593154600_B37","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1109\/MASSP.1986.1165342","article-title":"An introduction to hidden Markov models","volume":"3","author":"Rabiner,","year":"1986","journal-title":"IEEE ASSP Mag."},{"key":"2022112917593154600_B38","first-page":"78","article-title":"Bayes and big data: the consensus Monte Carlo algorithm","volume":"11","author":"Scott,","year":"2016","journal-title":"Int. J. Manag. Sci. Eng. Manag."},{"key":"2022112917593154600_B39","doi-asserted-by":"crossref","first-page":"377","DOI":"10.1017\/S0963548399003867","article-title":"Generating random regular graphs quickly","volume":"8","author":"Steger,","year":"1999","journal-title":"Combinat. Prob. Comp."},{"key":"2022112917593154600_B40","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/s11222-013-9429-x","article-title":"On parallel implementation of sequential Monte Carlo methods: the island particle model","volume":"25","author":"Verg\u00e9,","year":"2015","journal-title":"Statist. Comp."},{"key":"2022112917593154600_B41","doi-asserted-by":"crossref","first-page":"494","DOI":"10.3150\/14-BEJ666","article-title":"On the role of interaction in sequential Monte Carlo algorithms","volume":"22","author":"Whiteley,","year":"2016","journal-title":"Bernoulli"},{"key":"2022112917593154600_B42","doi-asserted-by":"crossref","first-page":"4711","DOI":"10.1109\/ACCESS.2020.3048241","article-title":"Performance analysis of resampling algorithms of parallel\/distributed particle filters","volume":"9","author":"Zhang,","year":"2020","journal-title":"IEEE Access"}],"container-title":["Biometrika"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/biomet\/advance-article-pdf\/doi\/10.1093\/biomet\/asac015\/43985653\/asac015.pdf","content-type":"application\/pdf","content-version":"am","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/109\/4\/921\/47415644\/asac015.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/biomet\/article-pdf\/109\/4\/921\/47415644\/asac015.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,29]],"date-time":"2022-11-29T18:00:33Z","timestamp":1669744833000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/biomet\/article\/109\/4\/921\/6535704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,24]]},"references-count":42,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2022,2,24]]},"published-print":{"date-parts":[[2022,11,29]]}},"URL":"https:\/\/doi.org\/10.1093\/biomet\/asac015","relation":{},"ISSN":["0006-3444","1464-3510"],"issn-type":[{"value":"0006-3444","type":"print"},{"value":"1464-3510","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022,12,1]]},"published":{"date-parts":[[2022,2,24]]}}}