×

Can local particle filters beat the curse of dimensionality? (English) Zbl 1325.60058

Summary: The discovery of particle filtering methods has enabled the use of nonlinear filtering in a wide array of applications. Unfortunately, the approximation error of particle filters typically grows exponentially in the dimension of the underlying model. This phenomenon has rendered particle filters of limited use in complex data assimilation problems. In this paper, we argue that it is often possible, at least in principle, to develop local particle filtering algorithms whose approximation error is dimension-free. The key to such developments is the decay of correlations property, which is a spatial counterpart of the much better understood stability property of nonlinear filters. For the simplest possible algorithm of this type, our results provide under suitable assumptions an approximation error bound that is uniform both in time and in the model dimension. More broadly, our results provide a framework for the investigation of filtering problems and algorithms in high dimensions.

MSC:

60G35 Signal detection and filtering (aspects of stochastic processes)
62M20 Inference from stochastic processes and prediction
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J10 Markov chains (discrete-time Markov processes on discrete state spaces)
65C05 Monte Carlo methods
68Q87 Probability in computer science (algorithm analysis, random structures, phase transitions, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv Euclid

References:

[1] Apte, A., Jones, C. K. R. T., Stuart, A. M. and Voss, J. (2008). Data assimilation: Mathematical and statistical perspectives. Internat. J. Numer. Methods Fluids 56 1033-1046. · Zbl 1384.62300
[2] Beskos, A., Crisan, D., Jasra, A. and Whiteley, N. (2014). Error bounds and normalizing constants for sequential Monte Carlo in high dimensions. Adv. Appl. Probab. · Zbl 1291.65009
[3] Bickel, P., Li, B. and Bengtsson, T. (2008). Sharp failure rates for the bootstrap particle filter in high dimensions. In Pushing the Limits of Contemporary Statistics : Contributions in Honor of Jayanta K. Ghosh. Inst. Math. Stat. Collect. 3 318-329. IMS, Beachwood, OH.
[4] Blank, M. (1997). Discreteness and Continuity in Problems of Chaotic Dynamics. Translations of Mathematical Monographs 161 . Amer. Math. Soc., Providence, RI. · Zbl 0881.58047
[5] Cappé, O., Moulines, E. and Rydén, T. (2005). Inference in Hidden Markov Models . Springer, New York. · Zbl 1080.62065
[6] Del Moral, P. and Guionnet, A. (2001). On the stability of interacting processes with applications to filtering and genetic algorithms. Ann. Inst. Henri Poincaré Probab. Stat. 37 155-194. · Zbl 0990.60005
[7] Dobrushin, R. L., Kryukov, V. I. and Toom, A. L., eds. (1990). Stochastic Cellular Systems : Ergodicity , Memory , Morphogenesis . Manchester Univ. Press, Manchester.
[8] Georgii, H.-O. (2011). Gibbs Measures and Phase Transitions , 2nd ed. de Gruyter Studies in Mathematics 9 . de Gruyter, Berlin. · Zbl 1225.60001
[9] Law, K. J. H. and Stuart, A. M. (2012). Evaluating data assimilation algorithms. Mon. Weather Rev. 140 3757-3782. · Zbl 1349.00174
[10] Lebowitz, J. L., Maes, C. and Speer, E. R. (1990). Statistical mechanics of probabilistic cellular automata. J. Stat. Phys. 59 117-170. · Zbl 1083.82522
[11] Majda, A. J. and Harlim, J. (2012). Filtering Complex Turbulent Systems . Cambridge Univ. Press, Cambridge. · Zbl 1250.93002
[12] Martinelli, F. (2004). Relaxation times of Markov chains in statistical mechanics and combinatorial structures. In Probability on Discrete Structures. Encyclopaedia Math. Sci. 110 175-262. Springer, Berlin. · Zbl 1206.82058
[13] Rebeschini, P. and van Handel, R. (2014). Phase transitions in nonlinear filtering. Preprint. Available at . arXiv:1401.6450 · Zbl 1351.37043
[14] Rebeschini, P. and van Handel, R. (2014). Comparison theorems for Gibbs measures. Preprint. Available at . arXiv:1308.4117 · Zbl 1302.82029
[15] Snyder, C. (2011). Particle filters, the “optimal” proposal and high-dimensional systems. In Proceedings of the ECMWF Seminar on Data Assimilation for Atmosphere and Ocean .
[16] Snyder, C., Bengtsson, T., Bickel, P. and Anderson, J. (2008). Obstacles to high-dimensional particle filtering. Mon. Weather Rev. 136 4629-4640.
[17] Tatikonda, S. C. and Jordan, M. I. (2002). Loopy belief propagation and Gibbs measures. In Proceedings of the Eighteenth Conference on Uncertainty in Artificial Intelligence 493-500. Morgan Kaufmann, San Francisco, CA.
[18] Tong, X. T. and van Handel, R. (2014). Conditional ergodicity in infinite dimension. Ann. Probab. 42 2243-2313. · Zbl 1351.37032
[19] van Leeuwen, P. J. (2009). Particle filtering in geophysical systems. Mon. Weather Rev. 137 4089-4114.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.