Discrete Filtering Using Branching and Interacting Particle Systems
1999, v.5, Issue 3, 293-318
The stochastic filtering problem deals with the estimation of the current state of a signal process given the information supplied by an associate process, usually called the observation process. The aim of the current paper is to provide a unified and simple approach for proving the validity of a series of numerical algorithms designed for solving discrete time filtering problems. These algorithms appeared in various papers (see [D. Crisan and T.J. Lyons, Nonlinear filtering and measure valued processes, Probab. Theory and Relat. Fields, 1997, 109, 217-244; D. Crisan and T.J. Lyons, Convergence of a branching particle method to the solution of the Zakai equation, SIAM J. Appl. Probab., 1998, 58 (5), 1568-1590; D. Crisan, J. Gaines and T.J. Lyons, A particle approximation of the solution of the Kushner - Stratonovitch equation, To appear in Probab. Theory and Relat. Fields; P. Del Moral, Non-linear filtering: interacting particle solution, Markov Processes Relat. Fields, 1996, v.2, 555-580; P. Del Moral, Measure valued processes and interacting particle systems. Application to non linear filtering problems, Publications du Laboratoire de Statistiques et Probabilites, Universite Paul Sabatier, 1996, 15-96, To appear in Ann. Appl. Probab.; P. Del Moral, Filtrage non lineaire par systemes de particules en interaction, C. R. Acad. Sci. Paris, Ser. I, 1997, v. 325, 653-658; P. Del Moral and A. Guionnet, Large deviations for interacting particle systems, Applications to non linear filtering problems. Publications du Laboratoire de Statistiques et Probabilites, Universite Paul Sabatier, 1997, 05-97; P. Del Moral and A. Guionnet, A central limit theorem for non linear filtering using interacting particle systems. Publications du Laboratoire de Statistiques et Probabilites, Universite Paul Sabatier, 1997, 11-97; N.J. Gordon, D.J. Salmon and A.F.M. Smith, Novel approach to non-linear/non-Gaussian Bayesian state estimation, IEE Proceedings, Part F, 1993, v. 140 (2), 107-113]) and were treated using different techniques. The algorithms involve the use of a system of $n$ particles which evolve (mutate) in correlation with each other according to law of a given Markov process and, at fixed times, give birth to a number of offsprings. Several possible branching mechanisms are described and, after imposing some weak restrictions on the branching mechanism, the empirical measure associated to the particle systems is proven to converge (as $n$ tends to $\infty$) to a measure valued process which satisfies a two step recurrence relation. Finally the result is applied to discrete time filtering. In this case the limiting measure valued process is precisely conditional distribution of the signal given the observation.
Keywords: filtering,particle systems,branching algorithms,interacting algorithms,measure valued processes,numerical solutions