The empirical cost of optimal incomplete transportation

Abstract

We consider the problem of optimal incomplete transportation between the empirical measure on an i.i.d. uniform sample on the d-dimensional unit cube $[0,1{]}^d$ and the true measure. This is a family of problems lying in between classical optimal transportation and nearest neighbor problems. We show that the empirical cost of optimal incomplete transportation vanishes at rate $O_P(n^{-1/d})$, where n denotes the sample size. In dimension $d\ge 3$ the rate is the same as in classical optimal transportation, but in low dimension it is (much) higher than the classical rate.

Published in at http://dx.doi.org/10.1214/12-AOP812 the Annals of Probability (http://www.imstat.org/aop/) by the Institute of Mathematical Statistics (http://www.imstat.org)

References in corpus (1)

• Similarity of samples and trimming