Ergodicity and Accuracy of Optimal Particle Filters for Bayesian Data Assimilation

Data assimilation refers to the methodology of combining dynamical models and observed data with the objective of improving state estimation. Most data assimilation algorithms are viewed as approximations of the Bayesian posterior (filtering distribution) on the signal given the observations. Some of these approximations are controlled, such as particle filters which may be refined to produce the true filtering distribution in the large particle number limit, and some are uncontrolled, such as ensemble Kalman filter methods which do not recover the true filtering distribution in the large ensemble limit. Other data assimilation algorithms, such as cycled 3DVAR methods, may be thought of as controlled estimators of the state, in the small observational noise scenario, but are also uncontrolled in general in relation to the true filtering distribution. For particle filters and ensemble Kalman filters it is of practical importance to understand how and why data assimilation methods can be effective when used with a fixed small number of particles, since for many large-scale applications it is not practical to deploy algorithms close to the large particle limit asymptotic. In this paper, the authors address this question for particle filters and, in particular, study their accuracy (in the small noise limit) and ergodicity (for noisy signal and observation) without appealing to the large particle number limit. The authors first overview the accuracy and minorization properties for the true filtering distribution, working in the setting of conditional Gaussianity for the dynamics-observation model. They then show that these properties are inherited by optimal particle filters for any fixed number of particles, and use the minorization to establish ergodicity of the filters. For completeness we also prove large particle number consistency results for the optimal particle filters, by writing the update equations for the underlying distributions as recursions. In addition to looking at the optimal particle filter with standard resampling, they derive all the above results for (what they term) the Gaussianized optimal particle filter and show that the theoretical properties are favorable for this method, when compared to the standard optimal particle filter.     

Particle filtering in the Dempster–Shafer theory

This paper derives a particle filter algorithm within the Dempster–Shafer framework. Particle filtering is a well-established Bayesian Monte Carlo technique for estimating the current state of a hidden Markov process using a fixed number of samples. When dealing with incomplete information or qualitative assessments of uncertainty, however, Dempster–Shafer models with their explicit representation of ignorance often turn out to be more appropriate than Bayesian models.The contribution of this paper is twofold. First, the Dempster–Shafer formalism is applied to the problem of maintaining a belief distribution over the state space of a hidden Markov process by deriving the corresponding recursive update equations, which turn out to be a strict generalization of Bayesian filtering. Second, it is shown how the solution of these equations can be efficiently approximated via particle filtering based on importance sampling, which makes the Dempster–Shafer approach tractable even for large state spaces. The performance of the resulting algorithm is compared to exact evidential as well as Bayesian inference.     

On the Stability and the Approximation of Branching Distribution Flows,with Applications to Nonlinear Multiple Target Filtering

We analyze the exponential stability properties of a class of measure-valued equations arising in nonlinear multi-target filtering problems. We also prove the uniform convergence properties w.r.t. the time parameter of a rather general class of stochastic filtering algorithms, including sequential Monte Carlo type models and mean field particle interpretation models. We illustrate these results in the context of the Bernoulli and the Probability Hypothesis Density filter, yielding what seems to be the first results of this kind in this subject.     

Sub-sample swapping for sequential Monte Carlo approximation of high-dimensional densities in the context of complex object tracking

In this paper, we address the problem of complex object tracking using the particle filter framework, which essentially amounts to estimate high-dimensional distributions by a sequential Monte Carlo algorithm. For this purpose, we first exploit Dynamic Bayesian Networks to determine conditionally independent subspaces of the object’s state space, which allows us to independently perform the particle filter’s propagations and corrections over small spaces. Second, we propose a swapping process to transform the weighted particle set provided by the update step of the particle filter into a “new particle set” better focusing on high peaks of the posterior distribution. This new methodology, called Swapping-Based Partitioned Sampling, is proved to be mathematically sound and is successfully tested and validated on synthetic video sequences for single or multiple articulated object tracking.     

基于粒子滤波算法的航迹误差分析

当前针对飞行预测的研究主要采用的是kalman算法,在解决非线性问题时存在着只能近似线性的而不够精确的问题.采用近年来受到广泛关注的粒子滤波算法,针对RNAV航路进行分析,结论中得到了对飞行误差仿真分析并对比了卡尔曼滤波仿真效果,证实了粒子滤波在航迹预测中更好的准确性.     

Particle Filters with Nudging in Multiscale Chaotic Systems: With Application to the Lorenz ’96 Atmospheric Model

This paper presents reduced-order nonlinear filtering schemes based on a theoretical framework that combines stochastic dimensional reduction and nonlinear filtering. Here, dimensional reduction is achieved for estimating the slow-scale process in a multiscale environment by constructing a filter using stochastic averaging results. The nonlinear filter is approximated numerically using the ensemble Kalman filter and particle filter. The particle filter is further adapted to the complexities of inherently chaotic signals. In particle filters, an ensemble of particles is used to represent the distribution of the state of the hidden signal. The ensemble is updated using observation data to obtain the best representation of the conditional density of the true state variables given observations. Particle methods suffer from the “curse of dimensionality,” an issue of particle degeneracy within a sample, which increases exponentially with system dimension. Hence, particle filtering in high dimensions can benefit from some form of dimensional reduction. A control is superimposed on particle dynamics to drive particles to locations most representative of observations, in other words, to construct a better prior density. The control is determined by solving a classical stochastic optimization problem and implemented in the particle filter using importance sampling techniques.

     

Coupling stochastic EM and approximate Bayesian computation for parameter inference in state-space models

We study the class of state-space models and perform maximum likelihood estimation for the model parameters. We consider a stochastic approximation expectation–maximization (SAEM) algorithm to maximize the likelihood function with the novelty of using approximate Bayesian computation (ABC) within SAEM. The task is to provide each iteration of SAEM with a filtered state of the system, and this is achieved using an ABC sampler for the hidden state, based on sequential Monte Carlo methodology. It is shown that the resulting SAEM-ABC algorithm can be calibrated to return accurate inference, and in some situations it can outperform a version of SAEM incorporating the bootstrap filter. Two simulation studies are presented, first a nonlinear Gaussian state-space model then a state-space model having dynamics expressed by a stochastic differential equation. Comparisons with iterated filtering for maximum likelihood inference, and Gibbs sampling and particle marginal methods for Bayesian inference are presented.     

Parameter estimation in general state-space models using particle methods

Particle filtering techniques are a set of powerful and versatile simulation-based methods to perform optimal state estimation in nonlinear non-Gaussian state-space models. If the model includes fixed parameters, a standard technique to perform parameter estimation consists of extending the state with the parameter to transform the problem into an optimal filtering problem. However, this approach requires the use of special particle filtering techniques which suffer from several drawbacks. We consider here an alternative approach combining particle filtering and gradient algorithms to perform batch and recursive maximum likelihood parameter estimation. An original particle method is presented to implement these approaches and their efficiency is assessed through simulation.     

Subcategories of Filter Tower Spaces

The concept of a convergence tower space, or equivalently, a convergence approach space is formulated here in the context of a Cauchy setting in order to include a completion theory. Subcategories of filter tower spaces are defined in terms of axioms involving a general t-norm, T, in order to include a broad range of spaces. A T-regular sequence for a filter tower space is defined and, moreover, it is shown that the category of T-regular objects is a bireflective subcategory of all filter tower spaces. A completion theory for subcategories of filter tower spaces is given.     

A Particle Filtering Approach for Tracking an Unknown Number of Objects with Dynamic Relations

In recent years there has been a growing interest on particle filters for solving tracking problems, thanks to their applicability to problems with continuous, non-linear and non-Gaussian state spaces, which makes them more suited than hidden Markov models, Kalman filters and their derivations, in many real world tasks. Applications include video surveillance, sensor fusion, tracking positions and behaviors of moving objects, situation assessment in civil and bellic scenarios, econometric and clinical data series analysis. In many environments it is possible to recognize classes of similar entities, like pedestrians or vehicles in a video surveillance system, or commodities in econometric. In this paper, a relational particle filter for tracking an unknown number of objects is presented which exploits possible interactions between objects to improve the quality of filtering. We will see that taking into account relations between objects will ease the tracking of objects in presence of occlusions and discontinuities in object dynamics. Experimental results on a benchmark data set are presented.     

Unscented filtering algorithm using two-step randomly delayed observations in nonlinear systems

An unscented filtering algorithm is derived for a class of nonlinear discrete-time stochastic systems using noisy observations which can be randomly delayed by one or two sample times. The update and the possible delays (of one and two sampling times) of any observation are modelled by using three Bernoulli random variables such that only one of them takes the value one. The algorithm performs in two-steps, prediction and update, and it uses a scaled unscented transformation to approximate the conditional mean and covariance of the state and observation at each time. The performance of the proposed filter is shown in a simulation example which uses a growth model with randomly delayed observations; in this example, the proposed filter is compared with the extended one obtained by linearizing the state and the observation equations and, also, with the unscented Kalman filter. A clear superiority of the proposed filter over the others is inferred.     

三状态样条滤波与平滑

本基于样条滤波理论，给出了三状态样条滤波与平滑方法。仿真计算与实例数据计算表明，该滤波与平滑方法具有较高的精度和稳定性。     

Dynamic Detection of Change Points in Long Time Series

We consider the problem of detecting change points (structural changes) in long sequences of data, whether in a sequential fashion or not, and without assuming prior knowledge of the number of these change points. We reformulate this problem as the Bayesian filtering and smoothing of a non standard state space model. Towards this goal, we build a hybrid algorithm that relies on particle filtering and Markov chain Monte Carlo ideas. The approach is illustrated by a GARCH change point model.     

Markov chain approximations to filtering equations for reflecting diffusion processes

Herein, we consider direct Markov chain approximations to the Duncan–Mortensen–Zakai equations for nonlinear filtering problems on regular, bounded domains. For clarity of presentation, we restrict our attention to reflecting diffusion signals with symmetrizable generators. Our Markov chains are constructed by employing a wide band observation noise approximation, dividing the signal state space into cells, and utilizing an empirical measure process estimation. The upshot of our approximation is an efficient, effective algorithm for implementing such filtering problems. We prove that our approximations converge to the desired conditional distribution of the signal given the observation. Moreover, we use simulations to compare computational efficiency of this new method to the previously developed branching particle filter and interacting particle filter methods. This Markov chain method is demonstrated to outperform the two-particle filter methods on our simulated test problem, which is motivated by the fish farming industry.     

Newton and Quasi-Newton Methods for Normal Maps with Polyhedral Sets

This paper is devoted to a search for a guaranteed counterpart of the stochastic Kalman filter. We study the guaranteed filtering of a linear system such that the phase state and external disturbance form a vector subject to an ellipsoidal bound. This seemingly exotic setup can be justified by an analogy with the observation of Gaussian processes. Unfortunately, the resulting guaranteed filtering supplies us an ellipsoid approximating the localization domain for the state vector, but not the localization domain itself, and turns out to be more difficult compared to the Kalman filter. Our main results consist of an explicit evaluation of the Hamiltonians. In principle, this permits us to write explicitly the equations of the guaranteed filter.     

Filtering of distributed parameter systems with pointwise disturbances

We consider in this article a filtering problem for a linear distributed parameter system where the input disturbances are located in points instead of being distributed. The observation process is assumed to be distributed inside the domain. Although formally one can derive equations for the Kalman filter and the Riccati equation, the complete justification of these equations leads to problems which cannot be solved by standard methods, in the sense that some new functional spaces need to be introduced. The objective of the paper is to give a rigorous treatment of this nonclassical filtering problem, which is relevant for applications.     

基于粒子滤波的改进型单值控制图

针对高度复杂小批量生产环境下的统计过程控制问题,提出基于粒子滤波的改进型单值控制图。通过状态空间模型描述过程运行特征,并运用粒子滤波技术估计过程的运行状态,以状态粒子群的均值为对象,运用平均移动极差控制图对正态分布过程的漂移进行监控。研究结果表明,该方法是小批量生产过程质量控制的有效工具。     

Stability of Feynman-Kac formulae with path-dependent potentials

Several particle algorithms admit a Feynman-Kac representation such that the potential function may be expressed as a recursive function which depends on the complete state trajectory. An important example is the mixture Kalman filter, but other models and algorithms of practical interest fall in this category. We study the asymptotic stability of such particle algorithms as time goes to infinity. As a corollary, practical conditions for the stability of the mixture Kalman filter, and a mixture GARCH filter, are derived. Finally, we show that our results can also lead to weaker conditions for the stability of standard particle algorithms for which the potential function depends on the last state only.     

On a class of SGS filters for LES with shape preserving concatenation properties

We develop a class of filter functions for large-eddy simulation which have the key property that multiple successive application even with different filter widths is equal to a single filtering employing filters from the same class but at an extended or equal filter width. In the context of the filter class development we obtain a functional delay equation which for special cases may be solved completely general. The presently developed class of filters may be used in conjunction with certain sub-grid scale models such as the approximate deconvolution model [3] where explicit multiple filtering is needed. Hence utilizing filters from the present class computational cost of filter evaluation may be considerably reduced.     

Large Deviation Principle for Optimal Filtering

Abstract. We derive a large deviation principle for the optimal filter where the signal and the observation processes take values in conuclear spaces. The approach follows from the framework established by the author in an earlier paper. The key is the verification of the exponential tightness for the optimal filtering process and the exponential continuity of the coefficients in the Zakai equation.