Branching and interacting particle systems. Approximations of Feynman-Kac formulae with applications to non-linear filtering

Del Moral, Pierre; Miclo, Laurent

Séminaire de probabilités de Strasbourg, Tome 34 (2000), pp. 1-145.

[1] J. Abela, D. Abramson, A. De Silval, M. Krishnamoorthy, and G. Mills. Computing optimal schedules for landing aircraft. Technical report, Department of Computer Systems Eng. R.M.I.T., Melbourne, May 1993.

[2] J.-M. Alliot, D. Delahaye, J.-L. Farges, and M. Schoenauer. Genetic algorithms for automatic regrouping of air traffic control sectors. In J. R. McDonnell, R. G. Reynolds, and D. B. Fogel, editors, Proceedings of the 4th Annual Conference on Evolutionary Programming, pages 657-672. MIT Press, March 1995.

[3] G. Ben Arous and M. Brunaud. Methode de laplace : étude variationnelle des fluctuations de diffusions de type "champ moyen". Stochastics, 31-32:79-144, 1990. | MR | Zbl

[4] R. Atar and O. Zeitouni. Exponential stability for nonlinear filtering. Annales de l'Institut Henri Poincaré, 33(6):697-725, 1997. | Numdam | MR | Zbl

[5] R. Atar and O. Zeitouni. Lyapunov exponents for finite state space nonlinear filtering. Society for Industrial and Applied Mathematics. Journal on Control and Optimization, 35(1):36-55, January 1997. | MR | Zbl

[6] J. Baker. Adaptative selection methods for genetic algorithms. In J. Grefenstette, editor, Proc. International Conf. on Genetic Algorithms and their Applications. L. Erlbaum Associates, 1985.

[7] J. Baker. Reducing bias and inefficiency in the selection algorithm. In J. Grefenstette, editor, Proc. of the Second International Conf. on Genetic Algorithms and their Applications. L. Erlbaum Associates, 1987.

[8] A. Bakirtzis, S. Kazarlis, and V. Petridis. A genetic algorithm solution to the economic dispatch problem. http://www.dai.ed.ac.uk/groups/evalg /eag_local_copies_of_papers.body.html.

[9] D. Bakry. L'hypercontractivité et son utilisation en théorie des semigroupes. In P. Bernard, editor,Lectures on Probability Theory. Ecole d'Eté de Probabilités de Saint-Flour XXII-1992, Lecture Notes in Mathematics 1581. Springer-Verlag, 1994. | MR | Zbl

[10] P. Barbe and P. Bertail. The Weighted Bootstrap. Lecture Notes in Statistics 98. Springer-Verlag, 1995. | Zbl

[11] E. Beadle and P. Djuric. A fast weighted Bayesian bootstrap filter for nonlinear model state estimation. Institute of Electrical and Electronics Engineers. Transactions on Aerospace and Electronic Systems, AES-33:338-343, January 1997.

[12] B.E. Benes. Exact finite-dimensional filters for certain diffusions with nonlinear drift. Stochastics, 5:65-92, 1981. | MR | Zbl

[13] E. Bolthausen. Laplace approximation for sums of independent random vectors i. Probability Theory and Related Fields, 72:305-318, 1986. | MR | Zbl

[14] C.L. Bridges and D.E. Goldberg. An analysis of reproduction and crossover in a binary-coded genetic algorithm. In J.J. Grefenstette, editor, Proc. of the Second International Conf. on Genetic Algorithms and their Applications. L. Erlbaum Associates, 1987.

[15] R.S. Bucy. Lectures on discrete time filtering, Signal Processing and Digital Filtering. Springer-Verlag, 1994. | MR | Zbl

[16] A. Budhiraja and D. Ocone. Exponential stability of discrete time filters for bounded observation noise. Systems and Control Letters, 30:185-193, 1997. | MR | Zbl

[17] Z. Cai, F. Le Gland, and H. Zhang. An adaptative local grid refinement method for nonlinear filtering. Technical report, INRIA, October 1995.

[18] H. Carvalho, P. Del Moral, A. Monin, and G. Salut. Optimal nonlinear filtering in gps/ins integration. Institute of Electrical and Electronics Engineers. Transactions on Aerospace and Electronic Systems, 33(3):835-850, July 1997.

[19] R. Cerf. Une théorie asymptotique des algorithmes génétiques. Thèse de doctorat, Université Montpellier II, March 1994.

[20] M. Chaleyat-Maurel and D. Michel. Des résultats de non existence de filtres de dimension finie. Comptes Rendus de l'Académie des Sciences de Paris. Série I. Mathématique, 296, 1983. | MR | Zbl

[21] D. Crisan, J. Gaines, and T.J. Lyons. A particle approximation of the solution of the kushner-stratonovitch equation. Society for Industrial and Applied Mathematics. Journal on Applied Mathematics, 58(5):1568-1590, 1998. | MR | Zbl

[22] D. Crisan and M. Grunwald. Large deviation comparison of branching algorithms versus resampling algorithm. Preprint, 1998.

[23] D. Crisan and T.J. Lyons. Nonlinear filtering and measure valued processes. Probability Theory and Related Fields, 109:217-244, 1997. | MR | Zbl

[24] D. Crisan, P. Del Moral, and T.J. Lyons. Interacting particle systems approximations of the Kushner-Stratonovitch equation. Advances in Applied Probability, 31(3), September 1999. | MR | Zbl

[25] D. Crisan, P. Del Moral, and T.J. Lyons. Non linear filtering using branching and interacting particle systems. Markov Processes and Related Fields, 5(3):293-319, 1999. | MR | Zbl

[26] G. Da Prato, M. Furhman, and P. Malliavin. Asymptotic ergodicity for the Zakai filtering equation. Comptes Rendus de l'Académie des Sciences de Paris. Série I. Mathématique, 321(5):613-616, 1995. | MR | Zbl

[27] E.B. Davies. Heat Kernels and Spectral Theory. Cambridge University Press, 1989. | MR | Zbl

[28] M. Davis. New approach to filtering for nonlinear systems. Institute of Electrical and Electronics Engineers. Proceedings, 128(5):166-172, 1981. Part D. | MR

[29] D. Dawson. Measure-valued Markov processes. In P.L. Hennequin, editor, Lectures on Probability Theory. Ecole d'Eté de Probabilités de Saint-Flour XXI-1991, Lecture Notes in Mathematics 1541. Springer-Verlag, 1993. | MR | Zbl

[30] P. Del Moral. Non-linear filtering: interacting particle resolution. Markov Processes and Related Fields, 2(4):555-581, 1996. | MR | Zbl

[31] P. Del Moral. Filtrage non linéaire par systèmes de particules en interaction. Comptes Rendus de l'Académie des Sciences de Paris. Série I. Mathématique, 325:653-658, 1997. | Zbl

[32] P. Del Moral. Maslov optimization theory: optimality versus randomness. In V.N. Kolokoltsov and V.P. Maslov, editors, Idempotency Analysis and its Applications, Mathematics and its Applications 401, pages 243-302. Kluwer Academic Publishers, Dordrecht/Boston/London, 1997. | MR

[33] P. Del Moral. Measure valued processes and interacting particle systems. Application to non linear filtering problems. The Annals of Applied Probability, 8(2):438-495, 1998. | MR | Zbl

[34] P. Del Moral. A uniform convergence theorem for the numerical solving of non linear filtering problems. Journal of Applied Probability, 35:873-884, 1998. | MR | Zbl

[35] P. Del Moral and A. Guionnet. Large deviations for interacting particle systems. Applications to non linear filtering problems. Stochastic Processes and their Applications, 78:69-95, 1998. | MR | Zbl

[36] P. Del Moral and A. Guionnet. On the stability of measure valued processes. Applications to non linear filtering and interacting particle systems. Publications du Laboratoire de Statistique et Probabilités, no 03-98, Université Paul Sabatier, 1998. | MR

[37] P. Del Moral and A. Guionnet. A central limit theorem for non linear filtering using interacting particle systems. The Annals of Applied Probability, 9(2):275-297, 1999. | MR | Zbl

[38] P. Del Moral and A. Guionnet. On the stability of measure valued processes with applications to filtering. Comptes Rendus de l'Académie des Sciences de Paris. Série I. Mathématique, 329:429-434, 1999. | MR | Zbl

[39] P. Del Moral and J. Jacod. Interacting particle filtering with discrete observations. Publications du Laboratoire de Statistiques et Probabilités, no 11-99, 1999.

[40] P. Del Moral and J. Jacod. The monte-carlo method for filtering with discrete time observations. central limit theorems. Publications du Laboratoire de Probabilités, no 515, 1999.

[41] P. Del Moral, J. Jacod, and P. Protter. The Monte Carlo method for filtering with discrete time observations. Publications du Laboratoire de Probabilités, no 453, June 1998.

[42] P. Del Moral and M. Ledoux. Convergence of empirical processes for interacting particle systems with applications to nonlinear filtering. to appear in Journal of Theoretical Probability, January 2000. | MR | Zbl

[43] P. Del Moral and L. Miclo. Asymptotic stability of non linear semigroup of Feynman-Kac type. Préprint, publications du Laboratoire de Statistique et Probabilités, no 04-99, 1999.

[44] P. Del Moral and L. Miclo. On the convergence and the applications of the generalized simulated annealing. SIAM Journal on Control and Optimization, 37(4):1222-1250, 1999. | MR | Zbl

[45] P. Del Moral and L. Miclo. A Moran particle system approximation of Feynman-Kac formulae. to appear in Stochastic Processes and their Applications, 2000. | MR | Zbl

[46] P. Del Moral, J.C. Noyer, and G. Salut. Résolution particulaire et traitement non-linéaire du signal : application radar/sonar. In Traitement du signal, September 1995. | Zbl

[47] P. Del Moral, G. Rigal, and G. Salut. Estimation et commande optimale non linéaire. Technical Report 2, LAAS/CNRS, March 1992. Contract D.R.E.T.-DIGILOG.

[48] B. Delyon and O. Zeitouni. Liapunov exponents for filtering problems. In M.H.A. Davis and R.J. Elliot, editors, Applied Stochastic Analysis, pages 511-521. Springer-Verlag, 1991. | MR | Zbl

[49] A. Dembo and O. Zeitouni. Large Deviations Techniques and Application. Jones and Bartlett, 1993. | MR | Zbl

[50] A.N. Van Der Vaart and J.A. Wellner. Weak Convergence and Empirical Processes with Applications to Statistics. Springer Series in Statistics. Springer, 1996. | MR | Zbl

[51] J.-D. Deuschel and D.W. Stroock. Large Deviations. Pure and applied mathematics 137. Academic Press, 1989. | MR | Zbl

[52] P. Diaconis and B. Efron. Méthodes de calculs statistiques intensifs sur ordinateurs. Pour la Science, 1983. translation of the American Scientist.

[53] R.L. Dobrushin. Central limit theorem for nonstationnary Markov chains, i,ii. Theory of Probability and its Applications, 1(1 and 4):66-80 and 330-385, 1956. | MR | Zbl

[54] E.B. Dynkin and A. Mandelbaum. Symmetric statistics, Poisson processes and multiple Wiener integrals. The Annals of Statistics, 11:739-745, 1983. | MR | Zbl

[55] S. Ethier and T. Kurtz. Markov Processes, Characterization and Convergence. Wiley series in probability and mathematical statistics. John Wiley and Sons, New York, 1986. | MR | Zbl

[56] M. Fujisaki, G. Kallianpur, and H. Kunita. Stochastic differential equations for the non linear filtering problem. Osaka J. Math., 1:19-40, 1972. | MR | Zbl

[57] F. Le Gland. Monte-Carlo methods in nonlinear filtering. In Proceedings of the 23rd IEEE Conference on Decision and Control, pages 31-32, Las Vegas, December 1984.

[58] F. Le Gland. High order time discretization of nonlinear filtering equations. In 28th IEEE CDC, pages 2601-2606, Tampa, 1989. | MR

[59] F. Le Gland, C. Musso, and N. Oudjane. An analysis of regularized interacting particle methods for nonlinear filtering. In Proceedings of the 3rd IEEE European Workshop on Computer-Intensive Methods in Control and Signal Processing, Prague, September 1998.

[60] D.E. Goldberg. Genetic algorithms and rule learning in dynamic control systems. In Proceedings of the First International Conference on Genetic Algorithms, pages 8-15, Hillsdale, NJ, 1985. L. Erlbaum Associates. | Zbl

[61] D.E. Goldberg. Simple genetic algorithms and the minimal deceptive problem. In L. Davis, editorGenetic Algorithms and Simulated Annealing. Pitman, 1987.

[62] D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Reading, MA, 1989. | Zbl

[63] D.E. Goldberg and P. Segrest. Finite Markov chain analysis of genetic algorithms. In J.J. Grefenstette, editor, Proc. of the 2nd Int. Conf. on Genetic Algorithms. L. Erlbaum Associates, 1987.

[64] N.J. Gordon, D.J. Salmon, and A.F.M. Smith. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F, 140:107-113, 1993.

[65] C. Graham and S. Méléard. Stochastic particle approximations for generalized Boltzmann models and convergence estimates. The Annals of Probability, 25(1):115-132, 1997. | MR | Zbl

[66] A. Guionnet. About precise Laplace's method; applications to fluctuations for mean field interacting particles. Preprint, 1997.

[67] J.H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975. | MR | Zbl

[68] J. Jacod and A.N. Shiryaev. Limit Theorems for Stochastic Processes. A Series of Comprehensive Studies in Mathematics 288. Springer-Verlag, 1987. | MR | Zbl

[69] J.M. Johnson and Y. Rahmat-Samii. Genetic algorithms in electromagnetics. In IEEE Antennas and Propagation Society International Symposium Digest, volume 2, pages 1480-1483, 1996.

[70] F. Jouve, L. Kallel, and M. Schoenauer. Mechanical inclusions identification by evolutionary computation. European Journal of Finite Elements, 5(5-6):619-648, 1996. | MR | Zbl

[71] F. Jouve, L. Kallel, and M. Schoenauer. Identification of mechanical inclusions. In D. Dagsgupta and Z. Michalewicz, editors, Evolutionary Computation in Engeneering, pages 477-494. Springer Verlag, 1997.

[72] G. Kallianpur and C. Striebel. Stochastic differential equations occuring in the estimation of continuous parameter stochastic processes. Tech. Rep. 103, Department of statistics, Univ. of Minnesota, September 1967.

[73] G. Kitagawa. Monte-Carlo filter and smoother for non-Gaussian nonlinear state space models. Journal on Computational and Graphical Statistics, 5(1):1-25, 1996. | MR

[74] H. Korezlioglu. Computation of filters by sampling and quantization. Technical Report 208, Center for Stochastic Processes, University of North Carolina, 1987.

[75] H. Korezlioglu and G. Maziotto. Modelization and filtering of discrete systems and discrete approximation of continuous systems. In Modélisation et Optimisation des Systèmes, VI Conférence INRIA, Nice, 1983.

[76] H. Korezlioglu and W.J. Runggaldier. Filtering for nonlinear systems driven by nonwhite noises: an approximating scheme. Stochastics and Stochastics Reports, 44(1-2):65-102, 1993. | MR | Zbl

[77] H. Kunita. Asymptotic behavior of nonlinear filtering errors of Markov processes. Journal of Multivariate Analysis, 1(4):365-393, 1971. | MR | Zbl

[78] H. Kunita. Ergodic properties nonlinear filtering processes. In K.C. Alexander and J.C. Watkins, editors, Spatial Stochastic Processes. Birkhaüser Boston, Boston, MA, 1991. | MR | Zbl

[79] S. Kusuoda and Y. Tamura. Gibbs measures for mean field potentials. J. Fac. Sci. Univ. Tokyo, Sect. IA, Math, 31, 1984. | MR | Zbl

[80] J.W. Kwiatkowski. Algorithms for index tracking. Technical report, Department of Business Studies, The University of Edinburgh, 1991. | MR

[81] R.S. Liptser and A.N. Shiryayev. Theory of Martingales. Dordrecht: Kluwer Academic Publishers, 1989. | MR | Zbl

[82] G.B. Di Masi, M. Pratelli, and W.G. Runggaldier. An approximation for the nonlinear filtering problem with error bounds. Stochastics, 14(4):247-271, 1985. | MR | Zbl

[83] S. Méléard. Asymptotic behaviour of some interacting particle systems; McKean-Vlasov and Boltzmann models. In D. Talay and L. Tubaro, editors, Probabilistic Models for Nonlinear Partial Differential Equations, Montecatini Terme, 1995, Lecture Notes in Mathematics 1627. Springer-Verlag, 1996. | MR | Zbl

[84] C. Musso and N. Oudjane. Regularization schemes for branching particle systems as a numerical solving method of the nonlinear filtering problem. In Proceedings of the Irish Signals Systems Conference, Dublin, June 1998. | MR

[85] C. Musso and N. Oudjane. Regularized particle schemes applied to the tracking problem. In International Radar Symposium, Munich, Proceedings, September 1998.

[86] Y. Nishiyama. Some central limit theorems for l∞-valued semimartingales and their applications. Probability Theory and Related Fields, 108:459-494, 1997. | MR | Zbl

[87] A. Nix and M.D. Vose. Modelling genetic algorithms with Markov chains. Annals of Mathematics and Artificial Intelligence, 5:79-88, 1991. | MR | Zbl

[88] D. Ocone and E. Pardoux. Asymptotic stability of the optimal filter with respect to its initial condition. Society for Industrial and Applied Mathematics.Journal on Control and Optimization, 34:226-243, 1996. | MR | Zbl

[89] D.L. Ocone. Topics in nonlinear filtering theory. Phd thesis, MIT, Cambridge, 1980.

[90] E. Pardoux. Filtrage non linéaire et équations aux dérivés partielles stochastiques associées. In P.L. Hennequin, editor, Ecole d'Eté de Probabilités de Saint-Flour XIX-1989, Lecture Notes in Mathematics 1464. Springer-Verlag, 1991. | MR | Zbl

[91] E. Pardoux and D. Talay. Approximation and simulation of solutions of stochastic differential equations. Acta Applicandae Mathematicae, 3(1):23-47, 1985. | MR | Zbl

[92] J. Picard. Approximation of nonlinear filtering problems and order of convergence. In Filtering and Control of Random Processes, Lecture Notes Control and Inf. Sc. 61. Springer, 1984. | MR | Zbl

[93] J. Picard. An estimate of the error in time discretization of nonlinear filtering problems. In C.I. Byrnes and A. Lindquist, editors, Proceedings of the 7th MTNS - Theory and Applications of nonlinear Control Systems, Stockholm, 1985, pages 401-412, Amsterdam, 1986. North-Holland Pub. | MR | Zbl

[94] J. Picard. Nonlinear filtering of one-dimensional diffusions in the case of a high signal-to-noise ratio. Society for Industrial and Applied Mathematics. Journal on Applied Mathematics, 16:1098-1125, 1986. | MR | Zbl

[95] S.T. Rachev. Probability Metrics and the Stability of Stochastic Models. Wiley, New York, 1991. | MR | Zbl

[96] D. Revuz and M. Yor. Continuous Martingales and Brownian Motion. Springer-Verlag, 1991. | MR | Zbl

[97] J. Shapcott. Index tracking: genetic algorithms for investment portfolio selection. Technical Report SS92-24, EPCC, September 1992.

[98] T. Shiga and H. Tanaka. Central limit theorem for a system of markovian particles with mean field interaction. Zeitschrift für Wahrscheinlichkeitstheorie verwandte Gebiete, 69, 1985. 439-459. | MR | Zbl

[99] A.N. Shiryaev. On stochastic equations in the theory of conditional Markov processes. Theor. Prob. Appl., 11:179-184, 1966.

[100] A.N. Shiryaev. Probability. Number 95 in Graduate Texts in Mathematics. Springer-Verlag, New-York, second edition, 1996. | MR | Zbl

[101] B. Simon. Trace ideals and their applications. London Mathematical Society Lecture Notes Series 35. Cambridge University Press, 1977. | MR | Zbl

[102] L. Stettner. On invariant measures of filtering processes. In K. Helmes and N. Kohlmann, editors, Stochastic Differential Systems, Proc. 4th Bad Honnef Conf. , Lecture Notes in Control and Inform. Sci., pages 279-292, 1989. | MR | Zbl

[103] L. Stettner. Invariant measures of pair state/approximate filtering process. In Colloq. Math. LXII, pages 347-352, 1991. | MR | Zbl

[104] R.L. Stratonovich. Conditional Markov processes. Theor. Prob. Appl., 5:156-178, 1960. | MR | Zbl

[105] D. Stroock and S.R.S. Varadhan. Multidimensional Diffusion Processes. Springer-Verlag, 1979. | MR | Zbl

[106] D.W. Stroock. An Introduction to the Theory of Large Deviations. Universitext. Springer-Verlag, New-York, 1984. | MR | Zbl

[107] M. Talagrand. Sharper bounds for Gaussian and empirical processes. The Annals of Probability, 22:28-76, 1994. | MR | Zbl

[108] D. Talay. Efficient numerical schemes for the approximation of expectations of functionals of the solution of s.d.e. and applications. In Filtering and Control of random processes (Paris, 1983), Lecture Notes in Control and Inform. Sci. 61, pages 294-313, Berlin-New York, 1984. Springer. | MR | Zbl

[109] H. Tanaka. Limit theorems for certain diffusion processes. In Proceedings of the Taniguchi Symp., Katata, 1982, pages 469-488, Tokyo, 1984. Kinokuniya. | MR | Zbl

[110] D. Treyer, D.S. Weile, and E. Michielsen. The application of novel genetic algorithms to electromagnetic problems. In Applied Computational Electromagnetics, Symposium Digest, volume 2, pages 1382-1386, Monterey, CA, March 1997.

[111] M.D. Vose. The Simple Genetic Algorithm, Foundations and Theory. The MIT Press Books, August 1999. | MR | Zbl

[112] D. Williams. Probability with Martingales. Cambridge Mathematical Textbooks, 1992. | MR | Zbl