On the performance of parallelisation schemes for particle filtering
Abstract Considerable effort has been recently devoted to the design of schemes for the parallel implementation of sequential Monte Carlo (SMC) methods for dynamical systems, also widely known as particle filters (PFs). In this paper, we present a brief survey of recent techniques, with an emphasis...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
SpringerOpen
2018-05-01
|
| Series: | EURASIP Journal on Advances in Signal Processing |
| Subjects: | |
| Online Access: | http://link.springer.com/article/10.1186/s13634-018-0552-x |
| _version_ | 1818997031844184064 |
|---|---|
| author | Dan Crisan Joaquín Míguez Gonzalo Ríos-Muñoz |
| author_facet | Dan Crisan Joaquín Míguez Gonzalo Ríos-Muñoz |
| author_sort | Dan Crisan |
| collection | DOAJ |
| description | Abstract Considerable effort has been recently devoted to the design of schemes for the parallel implementation of sequential Monte Carlo (SMC) methods for dynamical systems, also widely known as particle filters (PFs). In this paper, we present a brief survey of recent techniques, with an emphasis on the availability of analytical results regarding their performance. Most parallelisation methods can be interpreted as running an ensemble of lower-cost PFs, and the differences between schemes depend on the degree of interaction among the members of the ensemble. We also provide some insights on the use of the simplest scheme for the parallelisation of SMC methods, which consists in splitting the computational budget into M non-interacting PFs with N particles each and then obtaining the desired estimators by averaging over the M independent outcomes of the filters. This approach minimises the parallelisation overhead yet still displays desirable theoretical properties. We analyse the mean square error (MSE) of estimators of moments of the optimal filtering distribution and show the effect of the parallelisation scheme on the approximation error rates. Following these results, we propose a time–error index to compare schemes with different degrees of parallelisation. Finally, we provide two numerical examples involving stochastic versions of the Lorenz 63 and Lorenz 96 systems. In both cases, we show that the ensemble of non-interacting PFs can attain the approximation accuracy of a centralised PF (with the same total number of particles) in just a fraction of its running time using a standard multicore computer. |
| first_indexed | 2024-12-20T21:39:10Z |
| format | Article |
| id | doaj.art-53b4f5ecb9fc409fbf248d213efadd96 |
| institution | Directory Open Access Journal |
| issn | 1687-6180 |
| language | English |
| last_indexed | 2024-12-20T21:39:10Z |
| publishDate | 2018-05-01 |
| publisher | SpringerOpen |
| record_format | Article |
| series | EURASIP Journal on Advances in Signal Processing |
| spelling | doaj.art-53b4f5ecb9fc409fbf248d213efadd962022-12-21T19:25:51ZengSpringerOpenEURASIP Journal on Advances in Signal Processing1687-61802018-05-012018111810.1186/s13634-018-0552-xOn the performance of parallelisation schemes for particle filteringDan Crisan0Joaquín Míguez1Gonzalo Ríos-Muñoz2Department of Mathematics of Imperial College LondonDepartment of Signal Theory and Communications, Universidad Carlos III de MadridDepartment of Signal Theory and Communications, Universidad Carlos III de MadridAbstract Considerable effort has been recently devoted to the design of schemes for the parallel implementation of sequential Monte Carlo (SMC) methods for dynamical systems, also widely known as particle filters (PFs). In this paper, we present a brief survey of recent techniques, with an emphasis on the availability of analytical results regarding their performance. Most parallelisation methods can be interpreted as running an ensemble of lower-cost PFs, and the differences between schemes depend on the degree of interaction among the members of the ensemble. We also provide some insights on the use of the simplest scheme for the parallelisation of SMC methods, which consists in splitting the computational budget into M non-interacting PFs with N particles each and then obtaining the desired estimators by averaging over the M independent outcomes of the filters. This approach minimises the parallelisation overhead yet still displays desirable theoretical properties. We analyse the mean square error (MSE) of estimators of moments of the optimal filtering distribution and show the effect of the parallelisation scheme on the approximation error rates. Following these results, we propose a time–error index to compare schemes with different degrees of parallelisation. Finally, we provide two numerical examples involving stochastic versions of the Lorenz 63 and Lorenz 96 systems. In both cases, we show that the ensemble of non-interacting PFs can attain the approximation accuracy of a centralised PF (with the same total number of particles) in just a fraction of its running time using a standard multicore computer.http://link.springer.com/article/10.1186/s13634-018-0552-xParticle filteringParallelisationConvergence analysisParticle islandsLorenz 63Lorenz 96 |
| spellingShingle | Dan Crisan Joaquín Míguez Gonzalo Ríos-Muñoz On the performance of parallelisation schemes for particle filtering EURASIP Journal on Advances in Signal Processing Particle filtering Parallelisation Convergence analysis Particle islands Lorenz 63 Lorenz 96 |
| title | On the performance of parallelisation schemes for particle filtering |
| title_full | On the performance of parallelisation schemes for particle filtering |
| title_fullStr | On the performance of parallelisation schemes for particle filtering |
| title_full_unstemmed | On the performance of parallelisation schemes for particle filtering |
| title_short | On the performance of parallelisation schemes for particle filtering |
| title_sort | on the performance of parallelisation schemes for particle filtering |
| topic | Particle filtering Parallelisation Convergence analysis Particle islands Lorenz 63 Lorenz 96 |
| url | http://link.springer.com/article/10.1186/s13634-018-0552-x |
| work_keys_str_mv | AT dancrisan ontheperformanceofparallelisationschemesforparticlefiltering AT joaquinmiguez ontheperformanceofparallelisationschemesforparticlefiltering AT gonzaloriosmunoz ontheperformanceofparallelisationschemesforparticlefiltering |