Consistency and Rates of Convergence


A large amount of theoretical work has been advanced on the subject of nonlinear particle filters in general.  In 1998, Kurtz and Xiong used particles to show existence and uniqueness to SPDEs including the filtering ones.  In 1999, Pierre Del Moral and Laurent Miclo completed a treatise on particle methods, especially the interacting one, but these works do not include MIBR or SERP, nor do they include all possible characterizations of performance.  Douglas Blount and Michael Kouritzin have proved consistency for MIBR.  David Ballantyne and Mike Kourtizin have proved convergence for SERP.  Both of these follow from a general result of Blount and Kouritzin.

In addition, Pierre Del Moral, Michael Kouritzin, and Laurent Miclo jointly developed and analyzed an improved interacting particle method (IIPM) that was not included in the Del Moral, Miclo 1999 treatise.  IIPM performs very similarly to MIBR.

As mentioned, the MITACS-PINTS team has introduced IIPM, MIBR and SERP for asymptotic solutions to continuous-discrete filtering problems with pathspace capabilities. 

Suppose that t Xt is a Markov process on a Polish space and we wish to calculate the measure-valued process T[0,T] ) = P({X, 0 T} ), where =  and  is a distorted, corrupted, partial  ">observation of . Then, in all three methods we construct a particle system with observation-dependent sampling on  initial particles whose empirical measure up to time T,, closely approximates[0,T] .  Specifically, we establish an unnormalized pathspace filtering equation and prove that an unnormalized empirical measure for our particle filter converges (as n) in distribution to the unique solution of this pathspace DMZ equation. Recently, Douglas Blount and Michael Kouritzin (2002) have established almost sure convergence for the finite dimensional distributions of approximations of a large class of historical measure-valued processes including many constructed from martingale problems, nonlinear martingale problems and SPDEs.  The conditions are general enough to handle all standard approximations of continuous or discrete-time filtering problems, in which the historical variant of the Duncan-Montensen-Zakai equation yields an almost surely unique solution.  Almost-sure consistency for our MIBR is thereby established.  The thesis of Ballantyne (2002) then applies this result to establish the same strong convergence for SERP.

There are several convergence results for IIPM and its intellectual progenitor, the classical interacting method in Del Moral, Kouritzin and Miclo (2002).  Douglas Blount and Michael Kouritzin are working on two other convergence results for empirical measures of particle systems including the systems produced by MIBR and SERP.  The first result establishes general conditions under which the empirical measure of the particle path converges (almost surely in the topology of weak convergence for Borel measures) to a desired historical measure-valued process.  This technique is to convert the finite dimensional distribution result of the previous paragraph to a full pathspace distributional convergence through new tightness arguments.  The second study will establish rates for this convergence in a more specific, non-historical setting. The rates are in terms of both the number of particles and the sampling rate of the observations. 

Kouritzin and Long are currently investigating the convergence of the parameters in our recursive least-squares parameter estimation and filtering algorithm.  The algorithm is designed assuming access to the true filter of the model with the current parameter estimate substituted in.  Unfortunately, in practice one only has access to a distribution that depends on all past estimates in some way.  Therefore, there are two natural steps to prove convergence:  (1) Prove convergence of the parameter estimates using the filter of the model with only the current parameter estimate substituted in.  This was done based on the method of convergence of the Ljung's scheme.   In particular, we combined ideas from Gerenscer (1992) and Kouritzin (1994) to complete this step.  (2) Prove a strong ergodic property establishing that the difference between the actual available distribution and the filtering distribution that we just used converges to zero.  To do this, we first suppose that the current and recent past estimates are very close to the true parameters.  Then, it is possible to show using Step (1) that the estimates get trapped and converge into the true estimates.  Next, one can use a coupling idea to keep the parameter estimates close long enough that they get trapped with some small probability.  Finally, we use renewal arguments to ensure that they get this close infinitely often.  The actual proof is quite involved and a few details are still being worked out.  Once this convergence is proven, it is possible to adapt arguments of Kushner and Budhiraja to show that the average filtering error also converges.  (We realize that there is a gap in Kunita's (1971) paper and so we have to be careful about the conditions required for the Kushner-Budhiraja argument.) 

MARKOV CHAIN METHODS OF FILTERING

Our motivation for REST came from our earlier Markov chain methods.  Whereas we have not as of yet been able to prove convergence for REST as the cell size decreases and the initial number of particles increases, we have been able to prove convergence for the Markov chain methods.  We believe that our proofs can eventually be generalized to handle REST.

Motivated by our Markov chain approximations of spatial signals (discussed below), Kouritzin, Long, and Sun developed a Markov chain method of filtering for signals that evolve in a regular bounded subset of Euclidean space.  This method differs from the standard Hidden Markov Model approach in the sense that the signal itself is not approximated but instead its unnormalized conditional distribution.  The result is an efficient, direct, computer workable approximation to the filtering equations that is not the (unnormalized) conditional distribution of some approximate predictive model.  Moreover, the computer code, while not quite as simple as that implementing particle methods, is easy to implement and do not suffer so dramatically from dimension-dependent signal problems as do traditional PDE equation solvers.

Kouritzin, Long, and Sun (2001) considered signals, described by Skorohod SDEs, that reflect at the boundary of a rectangular region of Euclidean space.  We used classical, continuous time observations.  Our approximation was done in two distinct steps:  we first employed the wideband approximations of the Zakai equation studied by Kushner and Huang (1985, 1986) and then devised a further Markov chain approximation using the technique we developed to approximate stochastic reaction-diffusion equations and discuss below.  The upshot of these approximations is an easily implemented filtering method that shares the benefit of working in higher dimensions with particle filters but runs faster than the best particle filter.  (It was the inspiration for REST.)  Naturally, there will always be more assumed conditions required on the underlying predictive model than is the case for particle filters.  We proved consistency of this method using Kushner and Huang's result, time change methods, Dirichlet forms, stochastic calculus, and stochastic convergence.