SPADE: Sequential-clustering Particle Annihilation via Discrepancy Estimation

arXiv2005.05129MaRDI QIDQ6340455FDOQ6340455

Authors: Sihong Shao, Yunfeng Xiong 

Publication date: 11 May 2020

Abstract: For an empirical signed measure $mu=frac1Nleft(su{m}_{i=1}^{P}delt{a}_{x_i}-su{m}_{i=1}^{M}delt{a}_{y_i}ight)$, particle annihilation (PA) removes $N_A$ particles from both ${x_i}_{i=1}^P$ and ${y_i}_{i=1}^M$ simultaneously, yielding another empirical signed measure $u$ such that $intfdu$ approximates to $intfdmu$ within an acceptable accuracy for suitable test functions $f$. Such annihilation of particles carrying opposite importance weights has been extensively utilized for alleviating the numerical sign problem in particle simulations. In this paper, we propose an algorithm for PA in high-dimensional Euclidean space based on hybrid of clustering and matching, dubbed the Sequential-clustering Particle Annihilation via Discrepancy Estimation (SPADE). It consists of two steps: Adaptive clustering of particles via controlling their number-theoretic discrepancies, and independent random matching among positive and negative particles in each cluster. Both deterministic error bounds by the Koksma-Hlawka inequality and non-asymptotic random error bounds by concentration inequalities are proved to be affected by two factors. One factor measures the irregularity of point distributions and reflects their discrete nature. The other relies on the variation of test function and is influenced by the continuity. Only the latter implicitly depends on dimensionality $d$, implying that SPADE can be immune to the curse of dimensionality for a wide class of test functions. Numerical experiments up to $d=1080$ validate our theoretical discoveries.

Mathematics Subject Classification ID

Density estimation (62G07) Sampling theory, sample surveys (62D05) Nonparametric statistical resampling methods (62G09) Irregularities of distribution, discrepancy (11K38) Numerical approximation of high-dimensional functions; sparse grids (65D40)

This page was built for publication: SPADE: Sequential-clustering Particle Annihilation via Discrepancy Estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6340455)