Lookahead strategies for sequential Monte Carlo. (English) Zbl 1332.62144

Summary: Based on the principles of importance sampling and resampling, sequential Monte Carlo (SMC) encompasses a large set of powerful techniques dealing with complex stochastic dynamic systems. Many of these systems possess strong memory, with which future information can help sharpen the inference about the current state. By providing theoretical justification of several existing algorithms and introducing several new ones, we study systematically how to construct efficient SMC algorithms to take advantage of the “future” information without creating a substantially high computational burden. The main idea is to allow for lookahead in the Monte Carlo process so that future information can be utilized in weighting and generating Monte Carlo samples, or resampling from samples of the current state.


62G09 Nonparametric statistical resampling methods
65C05 Monte Carlo methods
65C40 Numerical analysis or methods applied to Markov chains
62M10 Time series, auto-correlation, regression, etc. in statistics (GARCH)
Full Text: DOI arXiv Euclid


[1] Andrieu, C., Doucet, A. and Holenstein, R. (2010). Particle Markov chain Monte Carlo methods. J. R. Stat. Soc. Ser. B Stat. Methodol. 72 269-342. · Zbl 1184.65001 · doi:10.1111/j.1467-9868.2009.00736.x
[2] Avitzour, D. (1995). Stochastic simulation Bayesian approach to multitarget tracking. IEE Proceedings on Radar , Sonar and Navigation 142 41-44.
[3] Briers, M., Doucet, A. and Maskell, S. (2010). Smoothing algorithms for state-space models. Ann. Inst. Statist. Math. 62 61-89. · Zbl 1422.62297 · doi:10.1007/s10463-009-0236-2
[4] Carpenter, J., Clifford, P. and Fearnhead, P. (1999). An improved particle for non-linear problems. IEE Proceedings on Radar , Sonar and Navigation 146 2-7.
[5] Carter, C. K. and Kohn, R. (1994). On Gibbs sampling for state space models. Biometrika 81 541-553. · Zbl 0809.62087 · doi:10.1093/biomet/81.3.541
[6] Carvalho, C. M., Johannes, M. S., Lopes, H. F. and Polson, N. G. (2010). Particle learning and smoothing. Statist. Sci. 25 88-106. · Zbl 1328.62541 · doi:10.1214/10-STS325
[7] Chen, R. and Liu, J. S. (2000). Mixture Kalman filters. J. R. Stat. Soc. Ser. B Stat. Methodol. 62 493-508. · Zbl 0953.62100 · doi:10.1111/1467-9868.00246
[8] Chen, R., Wang, X. and Liu, J. S. (2000). Adaptive joint detection and decoding in flat-fading channels via mixture Kalman filtering. IEEE Trans. Inform. Theory 46 2079-2094. · Zbl 1001.94008 · doi:10.1109/18.868479
[9] Chopin, N. (2002). A sequential particle filter method for static models. Biometrika 89 539-551. · Zbl 1036.62062 · doi:10.1093/biomet/89.3.539
[10] Chopin, N. (2004). Central limit theorem for sequential Monte Carlo methods and its application to Bayesian inference. Ann. Statist. 32 2385-2411. · Zbl 1079.65006 · doi:10.1214/009053604000000698
[11] Clapp, T. C. and Godsill, S. J. (1997). Bayesian blind deconvolution for mobile communications. In Proceedings of IEE Colloqium on Adaptive Signal Processing for Mobile Communication Systems 9 1-6. IET.
[12] Clapp, T. C. and Godsill, S. J. (1999). Fixed-lag smoothing using sequential importance sampling. In Bayesian Statistics 6 (J. M. Bernardo, J. O. Berger, A. P. Dawid and A. F. M. Smith, eds.) 743-752. Oxford Univ. Press, Oxford. · Zbl 1179.62110
[13] Crisan, D. and Lyons, T. (2002). Minimal entropy approximations and optimal algorithms. Monte Carlo Methods Appl. 8 343-355. · Zbl 1018.65014 · doi:10.1515/mcma.2002.8.4.343
[14] Del Moral, P. (2004). Feynman-Kac Formulae : Genealogical and Interacting Particle Systems with Applications . Springer, New York. · Zbl 1130.60003
[15] Douc, R., Garivier, E., Moulines, E. and Olsson, J. (2009). On the forward filtering backward smoothing particle approximations of the smoothing distribution in general state space models. Working paper, Institut Télécom, Paris.
[16] Doucet, A., Briers, M. and Sénécal, S. (2006). Efficient block sampling strategies for sequential Monte Carlo methods. J. Comput. Graph. Statist. 15 693-711. · doi:10.1198/106186006X142744
[17] Doucet, A., de Freitas, N. and Gordon, N., eds. (2001). Sequential Monte Carlo Methods in Practice . Springer, New York. · Zbl 0967.00022
[18] Fearnhead, P. (2002). Markov chain Monte Carlo, sufficient statistics, and particle filters. J. Comput. Graph. Statist. 11 848-862. · doi:10.1198/106186002835
[19] Fearnhead, P. and Clifford, P. (2003). On-line inference for hidden Markov models via particle filters. J. R. Stat. Soc. Ser. B Stat. Methodol. 65 887-899. · Zbl 1059.62098 · doi:10.1111/1467-9868.00421
[20] Fearnhead, P., Wyncoll, D. and Tawn, J. (2010). A sequential smoothing algorithm with linear computational cost. Biometrika 97 447-464. · Zbl 1406.62093 · doi:10.1093/biomet/asq013
[21] Fong, W., Godsill, S. J., Doucet, A. and West, M. (2002). Monte Carlo smoothing with application to speekch enhancement. IEEE Trans. Signal Process. 50 438-449.
[22] Gilks, W. R. and Berzuini, C. (2001). Following a moving target-Monte Carlo inference for dynamic Bayesian models. J. R. Stat. Soc. Ser. B Stat. Methodol. 63 127-146. · Zbl 0976.62021 · doi:10.1111/1467-9868.00280
[23] Godsill, S. J., Doucet, A. and West, M. (2004). Monte Carlo smoothing for non-linear time series. J. Amer. Statist. Assoc. 50 438-449. · Zbl 1089.62517
[24] Godsill, S. J. and Vermaak, J. (2004). Models and algorithms for tracking using trans-dimensional sequential Monte Carlo. Proc. IEEE ICASSP 3 976-979.
[25] Gordon, N. J., Salmond, D. J. and Smith, A. F. M. (1993). Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings on Radar and Signal Processing 140 107-113.
[26] Guo, D., Wang, X. and Chen, R. (2004). Multilevel mixture Kalman filter. EURASIP J. Appl. Signal Process. 15 2255-2266. · Zbl 1175.93223 · doi:10.1155/S1110865704403229
[27] Hürzeler, M. and Künsch, H. R. (1995). Monte Carlo approximations for general state space models. Research Report 73, ETH, Zürich.
[28] Ikoma, N., Ichimura, N., Higuchi, T. and Maeda, H. (2001). Maneuvering target tracking by using particle filter. In Joint 9 th IFSA World Congress and 20 th NAFIPS International Conference 4 2223-2228. IEEE.
[29] Kantas, N., Doucet, A., Singh, S. S. and Maciejowski, J. M. (2009). An overview of sequential Monte Carlo methods for parameter estimation in general state-space models. In 15 th IFAC Symposium on System Identification .
[30] Kim, S., Shephard, N. and Chib, S. (1998). Stochastic volatility: Likelihood inference and comparison with ARCH models. Review of Economic Studies 65 361-393. · Zbl 0910.90067 · doi:10.1111/1467-937X.00050
[31] Kitagawa, G. (1996). Monte Carlo filter and smoother for non-Gaussian nonlinear state space models. J. Comput. Graph. Statist. 5 1-25.
[32] Kong, A., Liu, J. S. and Wong, W. H. (1994). Sequential imputations and Bayesian missing data problems. J. Amer. Statist. Assoc. 89 278-288. · Zbl 0800.62166 · doi:10.2307/2291224
[33] Kotecha, J. H. and Djurić, P. M. (2003). Gaussian sum particle filtering. IEEE Trans. Signal Process. 51 2602-2612. · Zbl 1369.94196 · doi:10.1109/TSP.2003.816754
[34] Liang, J., Chen, R. and Zhang, J. (2002). Statistical geometry of packing defects of lattice chain polymer from enumeration and sequential Monte Carlo method. J. Chem. Phys. 117 3511-3521.
[35] Lin, M. T., Zhang, J. L., Cheng, Q. and Chen, R. (2005). Independent particle filters. J. Amer. Statist. Assoc. 100 1412-1421. · Zbl 1117.62388 · doi:10.1198/016214505000000349
[36] Liu, J. S. (2001). Monte Carlo Strategies in Scientific Computing . Springer, New York. · Zbl 0991.65001
[37] Liu, J. S. and Chen, R. (1995). Blind deconvolution via sequential imputations. J. Amer. Statist. Assoc. 90 567-576. · Zbl 0826.62062 · doi:10.2307/2291068
[38] Liu, J. S. and Chen, R. (1998). Sequential Monte Carlo methods for dynamic systems. J. Amer. Statist. Assoc. 93 1032-1044. · Zbl 1064.65500 · doi:10.2307/2669847
[39] Liu, J. S., Chen, R. and Wong, W. H. (1998). Rejection control and sequential importance sampling. J. Amer. Statist. Assoc. 93 1022-1031. · Zbl 1064.65501 · doi:10.2307/2669846
[40] Marshall, A. W. (1956). The use of multi-stage sampling schemes in Monte Carlo computations. In Symposium on Monte Carlo Methods (M. A. Meyer, ed.) 123-140. Wiley, New York.
[41] Pitt, M. K. (2002). Smooth particle filters for likelihood and maximisation. Technical report, Univ. Warwick.
[42] Pitt, M. K. and Shephard, N. (1999). Filtering via simulation: Auxiliary particle filters. J. Amer. Statist. Assoc. 94 590-599. · Zbl 1072.62639 · doi:10.2307/2670179
[43] Rosenbluth, M. N. and Rosenbluth, A. W. (1955). Monte Carlo calculation of the average extension of molecular chains. J. Chem. Phys. 23 356-359.
[44] van der Merwe, R., Doucet, A., de Freitas, N. and Wan, E. (2002). The unscented particle filter. In Advances in Neural Information Processing Systems ( NIPS 13) (T. K. Leen, T. G. Dietterich and V. Tresp, eds.). MIT Press, Cambridge, MA.
[45] Wang, X., Chen, R. and Guo, D. (2002). Delayed pilot sampling for mixture Kalman filter with application in fading channels. IEEE Trans. Signal Process. 50 241-264.
[46] Zhang, J. L. and Liu, J. S. (2002). A new sequential importance sampling method and its application to the two-dimensional hydrophobic-hydrophilic model. J. Chem. Phys. 117 3492-3498.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.