Support points (Q1991669)

For a continuous distribution function \(F\) with finite mean on \(\mathbb{R}^p\), the authors introduce a new method for constructing a set of representative points for \(F\), called support points. These are defined as those points \(\mathbf{x}_1,\ldots,\mathbf{x}_n\) minimizing the energy distance \(E(F,F_n)\), where \(F_n\) is the empirical distribution function of \(\mathbf{x}_1,\ldots,\mathbf{x}_n\) and the energy distance is defined by \[ E(F,F_n)=2\mathbb{E}\|\mathbf{X}-\mathbf{Y}\|_2-\mathbb{E}\|\mathbf{X}-\mathbf{X}'\|_2-\mathbb{E}\|\mathbf{Y}-\mathbf{Y}'\|_2\,, \] where \(\mathbf{X},\mathbf{X}'\overset{IID}{\sim}F\) and \(\mathbf{Y},\mathbf{Y}'\overset{IID}{\sim}F_n\). The distributional convergence of these support points to \(F\) is shown. The authors also establish a Koksma-Hlawka-type inequality, giving an upper bound for \(|\int g(\mathbf{x})\,d[F-F_n](\mathbf{x})|^2\) proportional to \(E(F,F_n)\) for a large class of integrands \(g\), together with an existence result for the error convergence rate and a discussion of the advantages of support points over existing Monte Carlo techniques in terms of this error rate. The proofs take advantage of duality between powers of the Euclidean distance and its Fourier transform. Two algorithms are also given for the generation of support points, with simulations to illustrate their use. In these simulations, empirical running times appear to grow almost linearly in the dimension \(p\), and quadratically in the number \(n\) of support points used. Further simulations illustrate the improved performance that support points can offer in numerical integration compared to other methods. The paper concludes with a discussion of two applications; the first is to uncertainty propagation in expensive simulations, and the second uses support points as an alternative to MCMC thinning for Bayesian computation.