Implicit Sampling, with Application to Data Assimilation

Abstract

There are many computational tasks, in which it is necessary to sample a given probability density function (or pdf for short), i.e., to use a computer to construct a sequence of independent random vectors x _i (i = 1, 2, …), whose histogram converges to the given pdf. This can be difficult because the sample space can be huge, and more importantly, because the portion of the space, where the density is significant, can be very small, so that one may miss it by an ill-designed sampling scheme. Indeed, Markovchain Monte Carlo, the most widely used sampling scheme, can be thought of as a search algorithm, where one starts at an arbitrary point and one advances step-by-step towards the high probability region of the space. This can be expensive, in particular because one is typically interested in independent samples, while the chain has a memory. The authors present an alternative, in which samples are found by solving an algebraic equation with a random right-hand side rather than by following a chain; each sample is independent of the previous samples. The construction in the context of numerical integration is explained, and then it is applied to data assimilation.

Keywords

Importance sampling / Bayesian estimation / Particle filter / Implicit filter / Data assimilation

References

[1] Doucet A., de Freitas N., Gordon N.. Sequential Monte Carlo Methods in Practice, 2001, New York: Springer-Verlag

[2] Chorin A. J., Hald O. H.. Stochastic Tools in Mathematics and Science, 2009 2nd edition New York: Springer-Verlag

[3] Morzfeld M., Tu X., Atkins E., Chorin A. J.. A random map implementation of implicit filters. J. Comput. Phys., 2012, 231: 2049-2066

[4] Morzfeld M., Chorin A. J.. Implicit particle filtering for models with partial noise, and an application to geomagnetic data assimilation. Nonlin. Processes Geophys., 2012, 19: 365-382

[5] Kloeden P. E., Platen E.. Numerical Solution of Stochastic Differential Equations, 1999 3rd edition New York: Springer-Verlag

[6] Chorin A. J., Tu X.. Implicit sampling for particle filters. Proc. Nat. Acad. Sc. USA, 2009, 106: 17249-17254

[7] Chorin A. J., Morzfeld M., Tu X.. Implicit particle filters for data assimilation. Commun. Appl. Math. Comput. Sci., 2010, 5(2): 221-240

[8] Arulampalam M. S., Maskell S., Gordon N., Clapp T.. A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking. IEEE Trans. Signal Process, 2002, 10: 197-208

[9] Bickel, P., Li, B. and Bengtsson, T., Sharp failure rates for the bootstrap particle filter in high dimensions, Pushing the Limits of Contemporary Statistics: Contributions in Honor of Jayanta K. Ghosh, 2008, 318–329.

[10] Snyder C. C., Bengtsson T., Bickel P., Anderson J.. Obstacles to high-dimensional particle filtering. Mon. Wea. Rev., 2008, 136: 4629-4640

[11] Gordon N. J., Salmon D. J., Smith A. F. M.. Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEEE Proceedings F on Radar and Signal Processing, 1993, 140: 107-113

[12] Doucet A., Godsill S., Andrieu C.. On sequential Monte Carlo sampling methods for Bayesian filtering. Statistics and Computing, 2000, 50: 174-188

[13] Del Moral P.. Feynman-Kac Formulae, 2004, New York: Springer-Verlag

[14] Del Moral P.. Measure-valued processes and interacting particle systems. Application to nonlinear filtering problems. Annals of Applied Probability, 1998, 8(2): 438-495

[15] Zaritskii V. S., Shimelevich L. I.. Monte Carlo technique in problems of optimal data processing. Automation and Remote Control, 1975, 12: 95-103

[16] Kalman R. E.. A new approach to linear filtering and prediction theory. Trans. ASME, Ser. D, 1960, 82: 35-48

[17] Kalman R. E., Bucy R. S.. New results in linear filtering and prediction theory. Trans. ASME, Ser. D, 1961, 83: 95-108

[18] Evensen G.. Data Assimilation, 2007, New York: Springer-Verlag

[19] Zakai M.. On the optimal filtering of diffusion processes. Zeit. Wahrsch., 1969, 11: 230-243

[20] Talagrand O., Courtier P.. Variational assimilation of meteorological observations with the adjoint vorticity equation. I: Theory. Q. J. R. Meteorol. Soc., 1987, 113: 1311-1328

[21] Bennet A. F., Leslie L. M., Hagelberg C. R., Powers P. E.. A cyclone prediction using a barotropic model initialized by a general inverse method. Mon. Weather Rev., 1993, 121: 1714-1728

[22] Courtier P., Thepaut J. N., Hollingsworth A.. A strategy for operational implementation of 4D-var, using an incremental appoach. Q. J. R. Meteorol. Soc., 1994, 120: 1367-1387

[23] Courtier P.. Dual formulation of four-dimensional variational assimilation. Q. J. R. Meteorol. Soc., 1997, 123: 2449-2461

[24] Talagrand O.. Assimilation of observations, an introduction. J. R. Meteorol. Soc. of Japan, 1997, 75(1): 191-209

[25] Tremolet Y.. Accounting for an imperfect model in 4D-var. Q. J. R. Meteorol. Soc., 2006, 621(132): 2483-2504

[26] Atkins, E., Morzfeld, M. and Chorin, A. J., Implicit particle methods and their connection to variational data assimilation, Mon. Weather Rev., in press.

[27] Kuramoto Y., Tsuzuki T.. On the formation of dissipative structures in reaction-diffusion systems. Progr. Theoret. Phys., 1975, 54: 687-699

[28] Sivashinsky G.. Nonlinear analysis of hydrodynamic instability in laminar flames, Part I, Derivation of basic equations. Acta Astronaut., 1977, 4: 1177-1206

[29] Chorin A. J., Krause P.. Dimensional reduction for a Bayesian filter. PNAS, 2004, 101: 15013-15017

[30] Jardak M., Navon I. M., Zupanski M.. Comparison of sequential data assimilation methods for the Kuramoto-Sivashinsky equation. Int. J. Numer. Methods Fluids, 2009, 62: 374-402

[31] Lord G. J., Rougemont J.. A numerical scheme for stochastic PDEs with Gevrey regularity. IMA Journal of Numerical Analysis, 2004, 24: 587-604

[32] Jentzen A., Kloeden P. E.. Overcoming the order barrier in the numerical approximation of stochastic partial differential equations with additive space-time noise. Proc. R. Soc. A, 2009, 465: 649-667

[33] Fletcher R.. Practical Methods of Optimization, 1987, New York: Wiley

[34] Nocedal J., Wright S. T.. Numerical Optimization, 2006 2nd edition New York: Springer-Verlag