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), p. 1-145 / Harvested from Numdam

Détail

Publié le : 2000-01-01

MR 1768060 | Zbl 0963.60040 | 5 citations dans Numdam

Bibliographie

[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 1080535 | Zbl 0705.60046

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

[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 1430282 | Zbl 0940.93073

[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 1307413 | Zbl 0856.47026

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

[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 643062 | Zbl 0458.60030

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

[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 1288080 | Zbl 0802.93058

[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 1455877 | Zbl 0901.93066

[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 719280 | Zbl 0529.60038

[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 1637870 | Zbl 0915.93060

[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 1477650 | Zbl 0888.93056

[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 1742696 | Zbl 0947.60040

[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 1710982 | Zbl 0967.93088

[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 1356563 | Zbl 0838.60039

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

[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 631971

[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 1242575 | Zbl 0799.60080

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

[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 0890.60096

[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 1447629

[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 1624949 | Zbl 0937.60038

[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 1671237 | Zbl 0940.60060

[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 1653296 | Zbl 0934.60026

[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 1710091

[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 1687359 | Zbl 0938.60022

[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 1710091 | Zbl 0935.92001

[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 1744985 | Zbl 0954.60014

[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 1691939 | Zbl 0928.60046

[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 1741805 | Zbl 1030.65004

[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 0885.94004

[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 1108433 | Zbl 0738.60033

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

[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 1385671 | Zbl 0862.60002

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

[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 86436 | Zbl 0093.15001

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

[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 838085 | Zbl 0592.60049

[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 336801 | Zbl 0242.93051

[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 1039100

[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 0675.68045

[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 0721.68056

[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 1428502 | Zbl 0873.60076

[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 441393 | Zbl 0317.68006

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

[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 1436837 | Zbl 0924.73321

[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 1380850

[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 1276930 | Zbl 0786.60058

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

[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 1144099 | Zbl 0742.60062

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

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

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

[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 805124 | Zbl 0566.60046

[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 1431299 | Zbl 0864.60077

[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 1722661

[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 1465638 | Zbl 0895.60025

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

[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 1372912 | Zbl 1035.93508

[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 1108184 | Zbl 0732.60050

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

[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 874832 | Zbl 0539.93078

[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 935393 | Zbl 0615.93068

[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 866283 | Zbl 0617.93057

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

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

[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 787607 | Zbl 0607.60095

[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 1368405 | Zbl 0835.60002

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

[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 1236074 | Zbl 0683.93082

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

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

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

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

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

[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 874837 | Zbl 0542.93077

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

[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 1713436 | Zbl 0952.65048

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