FACTOID # 10: The total number of state executions in 2005 was 60: 19 in Texas and 41 elsewhere. The racial split was 19 Black and 41 White.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Ensemble Kalman filter

Contents

The ensemble Kalman filter (EnKF) is a recursive filter suitable for problems with a large number of variables, such as discretizations of partial differential equations in geophysical models. The EnKF originated as a version of the Kalman filter for large problems (essentially, the covariance matrix is replaced by the sample covariance), and it is now an important data assimilation component of ensemble forecasting. EnKF is related to the particle filter (in this context, a particle is the same thing as ensemble member) but the EnKF makes the assumption that all probability distributions involved are Gaussian; when it is applicable, it is much more efficient than the particle filter. This article briefly describes the derivation and practical implementation of the basic version of EnKF, and reviews several extensions. Infinite impulse response (IIR) filters have an impulse response function which is non-zero over an infinite length of time. ... In mathematics, a partial differential equation (PDE) is a relation involving an unknown function of several independent variables and its partial derivatives with respect to those variables. ... The Kalman filter is an efficient recursive filter that estimates the state of a dynamic system from a series of incomplete and noisy measurements. ... In statistics and probability theory, the covariance matrix is a matrix of covariances between elements of a vector. ... Data assimilation (DA) is a method used in the weather forecasting process in which observations of the current (and possibly, past) weather are combined with a previous forecast for that time to produce the meteorological `analysis; the best estimate of the current state of the atmosphere. ... Ensemble forecasting is a method used by modern operational forecast centers to account for sensitive dependency on initial conditions. ... Result of particle filtering (red line) based on observed data generated from the blue line ( Much larger image) Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. ... The normal distribution, also called Gaussian distribution by scientists (named after Carl Friedrich Gauss due to his rigorous application of the distribution to astronomical data (Havil, 2003)) is a probability distribution of great importance in many fields. ... Result of particle filtering (red line) based on observed data generated from the blue line ( Much larger image) Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. ...


Introduction

The Ensemble Kalman Filter (EnKF) is a Monte-Carlo implementation of the Bayesian update problem: Given a probability density function (pdf) of the state of the modeled system (the prior, called often the forecast in geosciences) and the data likelihood, the Bayes theorem is used to to obtain the pdf after the data likelihood has been taken into account (the posterior, often called the analysis). This is called a Bayesian update. The Bayesian update is combined with advancing the model in time, incorporating new data from time to time. The original Kalman Filter[1] assumes that all pdfs are Gaussian (the Gaussian assumption) and provides algebraic formulas for the change of the mean and the covariance matrix by the Bayesian update, as well as a formula for advancing the covariance matrix in time provided the system is linear. However, maintaining the covariance matrix is not feasible computationally for high-dimensional systems. For this reason, EnKFs were developed.[2][3] EnKFs represent the distribution of the system state using a collection of state vectors, called an ensemble, and replace the covariance matrix by the sample covariance computed from the ensemble. The ensemble is operated with as if it was a random sample, but the ensemble members are really not independent - the EnKF ties them together. One advantage of EnKFs is that advancing the pdf in time is achieved by simply advancing each member of the ensemble. For a survey of EnKF and related data assimilation techniques, see.[4] A version of this article is also available as the technical report.[5] Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations. ... In mathematics, a probability density function (pdf) serves to represent a probability distribution in terms of integrals. ... A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence. ... Bayes theorem is a result in probability theory, which gives the conditional probability distribution of a random variable A given B in terms of the conditional probability distribution of variable B given A and the marginal probability distribution of A alone. ... The posterior probability can be calculated by Bayes theorem from the prior probability and the likelihood function. ... The Kalman filter is an efficient recursive filter that estimates the state of a dynamic system from a series of incomplete and noisy measurements. ... The normal distribution, also called Gaussian distribution by scientists (named after Carl Friedrich Gauss due to his rigorous application of the distribution to astronomical data (Havil, 2003)) is a probability distribution of great importance in many fields. ... In statistics, mean has two related meanings: Look up mean in Wiktionary, the free dictionary. ... In statistics and probability theory, the covariance matrix is a matrix of covariances between elements of a vector. ... An example of 500 mb geopotential height prediction from a numerical weather prediction model Numerical weather prediction is the science of predicting the weather using mathematical models of the atmosphere. ... This article is in need of attention from an expert on the subject. ...


A derivation of the EnKF

The Kalman Filter

Let us review first the Kalman filter. Let denote the n-dimensional state vector of a model, and assume that it has Gaussian probability distribution with mean and covariance Q, i.e., its pdf is The Kalman filter is an efficient recursive filter that estimates the state of a dynamic system from a series of incomplete and noisy measurements. ... Quite literally, quantum state describes the state of a quantum system. ... The normal distribution, also called Gaussian distribution by scientists (named after Carl Friedrich Gauss due to his rigorous application of the distribution to astronomical data (Havil, 2003)) is a probability distribution of great importance in many fields. ...

Here and below, means proportional; a pdf is always scaled so that its integral over the whole space is one. This probability distribution, called the prior, was evolved in time by running the model and now is to be updated to account for new data. It is natural to assume that the error distribution of the data is known; data have to come with an error estimate, otherwise they are meaningless. Here, the data is assumed to have Gaussian pdf with covariance R and mean , where H is the so-called the observation matrix. The covariance matrix R describes the estimate of the error of the data; if the random errors in the entries of the data vector are independent, R is diagonal and its diagonal entries are the squares of the standard deviation (“error size”) of the error of the corresponding entries of the data vector . The value is what the value of the data would be for the state in the absence of data errors. Then the probability density of the data conditional of the system state , called the data likelihood, is A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence. ... In probability and statistics, the standard deviation of a probability distribution, random variable, or population or multiset of values is a measure of the spread of its values. ... In statistics, a likelihood function is a conditional probability function considered a function of its second argument with its first argument held fixed, thus: and also any other function proportional to such a function. ...

The pdf of the state and the data likelihood are combined to give the new probability density of the system state conditional on the value of the data (the posterior) by the Bayes theorem, In statistics, a likelihood function is a conditional probability function considered a function of its second argument with its first argument held fixed, thus: and also any other function proportional to such a function. ... The posterior probability can be calculated by Bayes theorem from the prior probability and the likelihood function. ... Bayes theorem is a result in probability theory, which gives the conditional probability distribution of a random variable A given B in terms of the conditional probability distribution of variable B given A and the marginal probability distribution of A alone. ...

The data is fixed once it is received, so denote the posterior state by instead of and the posterior pdf by . It can be shown by algebraic manipulations[6] that the posterior pdf is also Gaussian,

with the posterior mean and covariance given by the Kalman update formulas

where

is the so-called Kalman gain matrix. The Kalman filter is an efficient recursive filter that estimates the state of a dynamic system from a series of incomplete and noisy measurements. ...


The Ensemble Kalman Filter

The EnKF is a Monte Carlo approximation of the Kalman filter, which avoids evolving the covariance matrix of the pdf of the state vector . Instead, the distribution an ensemble

X is an matrix whose columns are the ensemble members, and it is called the prior ensemble. Ideally, ensemble members would form a sample from the prior distribution. However, the ensemble members are not in general independent except in the initial ensemble, since every EnKF step ties them together. They are deemed to be approximately independent, and all calculations proceed as if they actually were independent. In signal processing, sampling is the reduction of a continuous signal to a discrete signal. ...


Replicate the data into an matrix

so that each column consists of the data vector plus a random vector from the n-dimensional normal distribution N(0,R). If, in addition, the columns of X are a sample from the prior probability distribution, then the columns of A prior probability is a marginal probability, interpreted as a description of what is known about a variable in the absence of some evidence. ...

form a sample from the posterior probability distribution. The EnKF is now obtained[7] simply by replacing the state covariance Q in Kalman gain matrix by the sample covariance C computed from the ensemble members (called the ensemble covariance). The posterior probability can be calculated by Bayes theorem from the prior probability and the likelihood function. ...


Implementation

Basic formulation

Here we follow.[8][9] Suppose the ensemble matrix X and the data matrix D are as above. The ensemble mean and the covariance are

where

and denotes the matrix of all ones of the indicated size.


The posterior ensemble Xp is then given by

where the perturbed data matrix D is as above. Since C can be written as

one can see that the posterior ensemble consists of linear combinations of members of the prior ensemble.


Note that since R is a covariance matrix, it is always positive semidefinite and usually positive definite, so the inverse above exists and the formula can be implemented by the Choleski decomposition.[10] In,[8][9] R is replaced by the sample covariance and the inverse is replaced by a pseudoinverse, computed using the Singular Value Decomposition (SVD) . In mathematics, the Cholesky decomposition, named after André-Louis Cholesky, is a matrix decomposition of a positive_definite matrix into a lower triangular matrix and the conjugate transpose of the lower triangular matrix. ... In mathematics, and in particular linear algebra, the pseudoinverse of an matrix is a generalization of the inverse matrix. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...


Since these formulas are matrix operations with dominant Level 3 operations,[11] they are suitable for efficient implementation using software packages such as LAPACK (on serial and shared memory computers) and ScaLAPACK (on distributed memory computers).[10] Instead of computing the inverse of a matrix and multiplying by it, it is much better (several times cheaper and also more accurate) to compute the Choleski decomposition of the matrix and treat the multiplication by the inverse as solution of a linear system with many simultaneous right-hand sides.[11] Basic Linear Algebra Subprograms (BLAS) are routines which perform basic linear algebra operations such as vector and matrix multiplication. ... LAPACK, the Linear Algebra PACKage, is a software library for numerical computing written in Fortran 77. ... In computer hardware, shared memory refers to a (typically) large block of random access memory that can be accessed by several different central processing units (CPUs) in a multiple-processor computer system. ... The ScaLAPACK (or Scalable LAPACK) library includes a subset of LAPACK routines redesigned for distributed memory MIMD parallel computers. ... Distributed memory is a concept used in parallel computing. ... In mathematics and especially linear algebra, an n-by-n matrix A is called invertible, non-singular or regular if there exists another n-by-n matrix B such that AB = BA = In, where In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. ... In mathematics, the Cholesky decomposition, named after André-Louis Cholesky, is a matrix decomposition of a positive_definite matrix into a lower triangular matrix and the conjugate transpose of the lower triangular matrix. ...


Observation matrix-free implementation

It is usually inconvenient to construct and operate with the matrix H explicitly; instead, a function of the form

is more natural to compute. The function h is called the observation function or, in the inverse problems context, the forward operator. The value of is what the value of the data would be for the state assuming the measurement is exact. Then the posterior ensemble can be rewritten as An inverse problem is the task that often occurs in many branches of science and mathematics where the values of some model parameter(s) must be obtained from the observed data. ... An inverse problem is the task that often occurs in many branches of science and mathematics where the values of some model parameter(s) must be obtained from the observed data. ...

where

and

with

Consequently, the ensemble update can be computed by evaluating the observation function h on each ensemble member once and the matrix H does not need to be known explicitly. This formula holds also[10] for an observation function with a fixed offset , which also does not need to be known explicitly. The above formula has been commonly used for a nonlinear observation function h, such as the position of a hurricane vortex.[12] In that case, the observation function is essentially approximated by a linear function from its values at ensemble members. This article is about weather phenomena. ... Vortex created by the passage of an aircraft wing, revealed by coloured smoke A vortex (pl. ...


Implementation for a large number of data points

For a large number m of data points, the multiplication by P − 1 becomes a bottleneck. The following alternative formula is advantageous when the number of data points m is large (such as when assimilating gridded or pixel data) and the data error covariance matrix R is diagonal (which is the case when the data errors are uncorrelated), or cheap to decompose (such as banded due to limited covariance distance). Using the Sherman–Morrison–Woodbury formula[13]

(R + UVT) − 1 = R − 1R − 1U(I + VTR − 1U) − 1VTR − 1,

with

gives

which requires only the solution of systems with the matrix R (assumed to be cheap) and of a system of size N with m right-hand sides. See[10] for operation counts.


Further extensions

The EnKF version described here involves randomization of data. For filters without randomization of data, see.[14][15][16]


Since the ensemble covariance is rank deficient (there are many more state variables, typically millions, than the ensemble members, typically less than a hundred), it has large terms for pairs of points that are spatially distant. Since in reality the values of physical fields at distant locations are not that much correlated, the covariance matrix is tapered off artificially based on the distance, which gives rise to localized EnKF algorithms.[17][18] In probability theory and statistics, correlation, also called correlation coefficient, is a numeric measure of the strength of linear relationship between two random variables. ...


For nonlinear problems, EnKF can create posterior ensemble with non-physical states. This can be alleviated by regularization, such as penalization of states with large spatial gradients.[7] Tikhonov regularization is the most commonly used method of regularization of ill-posed problems. ... Penalty methods are a certain class of algorithms to solve constraint optimization problems. ... For other uses, see Gradient (disambiguation). ...


For problems with coherent features, such as firelines, squall lines, and rain fronts, there is a need to adjust the simulation state by distorting the state in space as well as by an additive correction to the state. The morphing EnKF[19][20] employs intermediate states, obtained by techniques borrowed from image registration and morphing, instead of linear combinations of states. A squall or squall line is a line of thunderstorms with a common leading convection line, or mesocyclone, which tends to create a powerful gust front. ... In computer vision, sets of data acquired by sampling the same scene or object at different times, or from different perspectives, will be in different coordinate systems. ... To meet Wikipedias quality standards, this article or section may require cleanup. ...


EnKFs rely on the Gaussian assumption, though they are of course used in practice for nonlinear problems, where the Gaussian assumption is not satisfied. Related filters attempting to relax the Gaussian assumption in EnKF while preserving its advantages include filters that fit the state pdf with multiple Gaussian kernels,[21] filters that approximate the state pdf by Gaussian mixtures,[22] a variant of the particle filter with computation of particle weights by density estimation,[20] and a variant of the particle filter with thick tailed data pdf to alleviate particle filter degeneracy.[23] Result of particle filtering (red line) based on observed data generated from the blue line ( Much larger image) Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. ... In probability and statistics, density estimation is the construction of an estimate, based on observed data, of an unobservable underlying probability density function. ... The Cauchy-Lorentz distribution, named after Augustin Cauchy, is a continuous probability distribution with probability density function where x0 is the location parameter, specifying the location of the peak of the distribution, and γ is the scale parameter which specifies the half-width at half-maximum (HWHM). ... Result of particle filtering (red line) based on observed data generated from the blue line ( Much larger image) Particle filter methods, also known as Sequential Monte Carlo (SMC), are sophisticated model estimation techniques based on simulation. ...


References

  1. ^ R. E. Kalman, A new approach to linear filtering and prediction problems, Transactions of the ASME -- Journal of Basic Engineering, Series D, 82 (1960), pp. 35--45.
  2. ^ G. Evensen, Sequential data assimilation with nonlinear quasi-geostrophic model using Monte Carlo methods to forecast error statistics, Journal of Geophysical Research, 99 (C5) (1994), pp. 143--162.
  3. ^ P. Houtekamer and H. L. Mitchell, Data assimilation using an ensemble Kalman filter technique, Monthly Weather Review, 126 (1998), pp. 796--811.
  4. ^ G. Evensen, Data assimilation : The ensemble Kalman filter, Springer, Berlin, 2007.
  5. ^ J. Mandel, A brief tutorial on the ensemble Kalman filter, CCM Report 242, University of Colorado at Denver and Health Sciences Center, February 2007. report
  6. ^ B. D. O. Anderson and J. B. Moore, Optimal filtering, Prentice-Hall, Englewood Cliffs, N.J., 1979.
  7. ^ a b C. J. Johns and J. Mandel, A two-stage ensemble Kalman filter for smooth data assimilation. Environmental and Ecological Statistics, in print. Special issue, Conference on New Developments of Statistical Analysis in Wildlife, Fisheries, and Ecological Research, Oct 13-16, 2004, Columbia, MI. CCM Report 221, University of Colorado at Denver and Health Sciences Center, 2005. report
  8. ^ a b G. Burgers, P. J. van Leeuwen, and G. Evensen, Analysis scheme in the ensemble Kalman filter, Monthly Weather Review, 126 (1998), pp. 1719--1724.
  9. ^ a b G. Evensen, The ensemble Kalman filter: Theoretical formulation and practical implementation, Ocean Dynamics, 53 (2003), pp. 343--367.
  10. ^ a b c d J. Mandel, Efficient implementation of the ensemble Kalman filter. CCM Report 231, University of Colorado at Denver and Health Sciences Center. link, June 2006.
  11. ^ a b G. H. Golub and C. F. V. Loan, Matrix Computations, Johns Hopkins Univ. Press, 1989. Second Edition.
  12. ^ Y. Chen and C. Snyder, Assimilating vortex position with an ensemble Kalman filter. Monthly Weather Review, to appear, 2006. preprint.
  13. ^ W. W. Hager, Updating the inverse of a matrix, SIAM Rev., 31 (1989), pp. 221--239.
  14. ^ J. L. Anderson, An ensemble adjustment Kalman filter for data assimilation, Monthly Weather Review, 129 (1999), pp. 2884--2903.
  15. ^ G. Evensen, Sampling strategies and square root analysis schemes for the EnKF, Ocean Dynamics, 54 (2004), pp. 539--560.
  16. ^ M. K. Tippett, J. L. Anderson, C. H. Bishop, T. M. Hamill, and J. S. Whitaker, Ensemble square root filters, Monthly Weather Review, 131 (2003), pp. 1485--1490.
  17. ^ J. L. Anderson, A local least squares framework for ensemble filtering, Monthly Weather Review, 131 (2003), pp. 634--642.
  18. ^ E. Ott, B. R. Hunt, I. Szunyogh, A. V. Zimin, E. J. Kostelich, M. Corazza, E. Kalnay, D. Patil, and J. A. Yorke, A local ensemble Kalman filter for atmospheric data assimilation, Tellus A, 56 (2004), pp. 415--428.
  19. ^ J. D. Beezley and J. Mandel, Morphing ensemble Kalman filters. Tellus A, submitted. CCM Report 240, University of Colorado at Denver and Health Sciences Center, February 2007, report.
  20. ^ a b J. Mandel and J. D. Beezley, Predictor-corrector and morphing ensemble filters for the assimilation of sparse data into high dimensional nonlinear systems. CCM Report 239, University of Colorado at Denver and Health Sciences Center. report, November 2006. 11th Symposium on Integrated Observing and Assimilation Systems for the Atmosphere, Oceans, and Land Surface (IOAS-AOLS), CD-ROM, Paper 4.12, 87th American Meteorological Society Annual Meeting, San Antonio, TX, January 2007, link.
  21. ^ J. L. Anderson and S. L. Anderson, A Monte Carlo implementation of the nonlinear filtering problem to produce ensemble assimilations and forecasts, Monthly Weather Review, 127 (1999), pp. 2741--2758.
  22. ^ T. Bengtsson, C. Snyder, and D. Nychka, Toward a nonlinear ensemble filter for high dimensional systems, Journal of Geophysical Research - Atmospheres, 108(D24) (2003), pp. STS 2--1--10. preprint.
  23. ^ P. van Leeuwen, A variance-minimizing filter for large-scale applications, Monthly Weather Review, 131 (2003), pp. 2071--2084.

See also


 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m