Curse-of-dimensionality revisited: Collapse of importance sampling in very high-dimensional systems.

November, 2005
Report Number: 
Bo Li, Thomas Bengtsson, Peter Bickel

It has been widely realized that Monte Carlo methods (approximation via a sample ensemble) may fail in large scale systems. This work offers some theoretical insight into this phenomenon. In the context of a particle filter (as well as in general importance samplers), we demonstrate that the maximum of the weights associated with the sample ensemble members converges to one as both sample size and system dimension tends to infinity. Under fairly weak assumptions, this convergence is shown to hold for both a Gaussian case and for a more general case with iid kernels. Similar singularity behavior is also shown to hold for non-Gaussian, spherically symmetric kernels (e.g. multivariate Cauchy distribution). In addition, in certain large scale settings, we show that the estimator of an expectation based on importance sampling converges weakly to a law, rather than the target constant. Our work is presented and discussed in the context of atmospheric data assimilation for numerical weather prediction.

PDF File: 
Postscript File: