Monte Carlo sampling in dual space for approximating the empirical halfspace distance. (English) Zbl 0881.62067

Summary: The Kolmogorov-Smirnov distance is an important tool for constructing confidence sets and tests in univariate problems. In multivariate settings, an analogous role is played by the halfspace distance, which has the merit of being invariant under linear transformations. However, the evaluation of the halfspace distance between two samples is a computationally very intensive combinatorial problem even in moderate dimensions, which severely restricts the use of the halfspace distance, especially in resampling procedures.
To approximate this distance in a fast and data-dependent way, the notion of a dual measure is introduced. Based on geometric concepts, it will be shown how the above problem can be put as a density estimation problem using Monte Carlo sampling in a certain dual space. A central limit theorem for the empirical halfspace distance is derived and used as a gauge to compare the new procedure with a traditional random search.


62H99 Multivariate analysis
62G07 Density estimation
62G05 Nonparametric estimation
65C99 Probabilistic methods, stochastic differential equations
60F05 Central limit and other weak theorems
62B99 Sufficiency and information
Full Text: DOI