**Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?**

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Publication# The Scrambled Net Filter

Résumé

The standard Kalman filter is a powerful and widely used tool to perform prediction, filtering and smoothing in the fields of linear Gaussian state-space models. In its standard setting it has a simple recursive form which implies high computational efficiency. As the latter is essentially a least squares procedure optimality properties can be derived easily. These characteristics of the standard Kalman filter depend strongly on distributional and linearity assumptions of the model. If we consider nonlinear non-Gaussian state-space models all these properties and characteristics are no longer valid. Consequently there are different approaches on the robustification of the Kalman filter. One is based on the the ideas of minimax problems and influence curves. Others use numerical integration and Monte Carlo methods. Herein we propose a new filter by implementing a method of numerical integration, called scrambled net quadrature, which consists of a mixture of Monte Carlo methods and quasi-Monte Carlo methods, providing an integration error of order of magnitude $N^{-3/2}\log(N)^{(r-1)/2}$ in probability, where $r$ denotes dimension. We show that the point-wise bias of the posterior density estimate is of order of magnitude $N^{-3}\log(N)^{r-1}$ but grows linearly with time.

Official source

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés

Chargement

Publications associées

Chargement

Concepts associés (14)

Publications associées (3)

Filtre de Kalman

vignette| Concept de base du filtre de Kalman.
En statistique et en théorie du contrôle, le filtre de Kalman est un filtre à réponse impulsionnelle infinie qui estime les états d'un système dynamique

Calcul numérique d'une intégrale

En analyse numérique, il existe une vaste famille d’algorithmes dont le but principal est d’estimer la valeur numérique de l’intégrale définie sur un domaine particulier pour une fonction donnée (par

Méthode de Monte-Carlo

Une méthode de Monte-Carlo, ou méthode Monte-Carlo, est une méthode algorithmique visant à calculer une valeur numérique approchée en utilisant des procédés aléatoires, c'est-à-dire des techniques p

Chargement

Chargement

Chargement

In time series analysis state-space models provide a wide and flexible class. The basic idea is to describe an unobservable phenomenon of interest on the basis of noisy data. The first constituent of such a model is the so-called state equation, which characterises the unobserved state of the system. The second part is the so-called observation equation, which describes the observable variables as a function of the unobserved state. The purpose of the analysis of state-space models is to infer the relevant properties of the unobserved phenomenon from the observed data. A powerful tool to do so in the linear Gaussian setting is the Kalman filter. It provides a simple recursive computational scheme for the conditional expectation of the unobserved state given the observed data. However, since the Kalman filter is is linear in the data it is sensitive to outlying observations. A certain robustness of the procedure can easily be achieved by abandoning the Gaussianity assumption. On the other hand, the assumption of linearity is frequently found to be inadequate in practical situations and therefore needs to be generalised as well. However, without linearity and Gaussianity the simple recursive formulae of the Kalman filter are lost and the recursive computation of the conditional expectation must be replaced by approximations of ratios of high dimensional integral. Numerical and Monte Carlo integration techniques have been proposed for this purpose. The former yield powerful tools in low dimensional problems but suffer in high dimensional settings from the resulting computational burden. On the other hand Monte Carlo integration techniques lead to so-called particle filters, which provide computationally attractive tools even applicable in high dimensional problems. Although particle filters have some appealing properties they are not entirely convincing: the approximation error is relatively large; outliers may significantly affect the computational efficiency and in practical situations it is often very difficult to tune them adequately. Hence, we propose to adopt another integration method, the so-called scrambled net integration – a hybrid of numerical and Monte Carlo integration techniques. For the non-iterative approximation of integrals, this method has been proven to be often much more accurate than Monte Carlo methods as well as to deal well with the computational burden in high dimensions. We implement scrambled net integration in the general Kalman recursions and derive new prediction, filtering and smoothing algorithms. Further, we show that the approximation error remains stable during iterations and that the accuracy of the resulting state estimates is higher than that of particle filters. The resulting algorithms are more robust than the particle filter algorithm since their computational complexity is not influenced by outlying observations. In addition, we prove a central limit theorem for the estimator of the filter's expectation. Scrambled nets can also be used for hyper-parameter estimation since the likelihood of a general state-space model is a byproduct of the general Kalman recursions. They not only provide an approximation to the likelihood function but also a suitable grid over which it is maximised. The resulting estimation procedure is particularly attractive when dealing with high dimensional hyper-parameter spaces. Finally, one of the main difficulties when studying the properties of an unobserved phenomenon is designing a good general state-space model. Besides the determination of state and observation equations the problem of choosing appropriate noise distributions is crucial since they express the inherent uncertainty of the model used. From a practical point of view it is frequently completely unclear how to choose these noise distributions. Rather than relying on an uneducated guess of a single distributional model we propose to use several fundamentally different distributions and derive an adaptive filter providing a data-driven approach, which is naturally robust with respect to deviations from a distributional model.

We show that the liquid-to-crystal quantum phase transition in the Rokhsar-Kivelson dimer model on the two-dimensional triangular lattice occurs as a condensation of vortexlike excitations called "visons." This conclusion is drawn from numerical studies of the vison spectrum in the liquid phase by using the Green's function Monte Carlo method. We find that visons remain the lowest excitation throughout the liquid phase and that their gap decreases continuously to zero at the phase transition. The nature of the crystal phase and the second order of the phase transition are in agreement with an earlier prediction of Moessner and Sondhi.

2007The standard Kalman filter is a powerful and widely used tool to perform prediction, filtering and smoothing in the fields of linear Gaussian state-space models. In its standard setting it has a simple recursive form which implies high computational efficiency. As the latter is essentially a least squares procedure optimality properties can be derived easily. These characteristics of the standard Kalman filter depend strongly on distributional and linearity assumptions of the model. If we consider nonlinear non-Gaussian state-space models all these properties and characteristics are no longer valid. Consequently there are different approaches on the robustification of the Kalman filter. One is based on the the ideas of minimax problems and influence curves. Others use numerical integration and Monte Carlo methods. Herein we propose a new filter by implementing a method of numerical integration, called scrambled net quadrature, which consists of a mixture of Monte Carlo methods and quasi-Monte Carlo methods, providing an integration error of order of magnitude $N^{-3/2}\log(N)^{(r-1)/2}$ in probability, where $r$ denotes dimension. We show that the point-wise bias of the posterior density estimate is of order of magnitude $N^{-3}\log(N)^{r-1}$ but grows linearly with time.

2002