The empirical cost of optimal incomplete transportation

DOI10.1214/12-AOP812MaRDI QIDQ378795zbMATH OpenFDO

Authors Carlos Matrán, Eustasio Del Barrio

Publication date 12 November 2013

Published in The Annals of Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1310.0924, https://projecteuclid.org/euclid.aop/1378991834

zbMATH Keywords

optimal transportationrates of convergenceoptimal incomplete transportationoptimal matchingoptimal partial matchingrandom quantization

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Combinatorial probability (60C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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 $dgeq3$ the rate is the same as in classical optimal transportation, but in low dimension it is (much) higher than the classical rate.

Recommendations

• Central limit theorems for empirical transportation cost in general dimension
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• Rates of convergence for partial mass problems
• Asymptotics for transportation cost in high dimensions
• Inverse optimal transport

Cites work

• scientific article; zbMATH DE number 3586221 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1909499 (Why is no real title available?)
• scientific article; zbMATH DE number 272681 (Why is no real title available?)
• Asymptotics for transportation cost in high dimensions
• Concentration inequalities and model selection. Ecole d'Eté de Probabilités de Saint-Flour XXXIII -- 2003.
• Concentration inequalities using the entropy method
• Foundations of quantization for probability distributions
• Free boundaries in optimal transport and Monge-Ampère obstacle problems
• Limit theorems for multi-dimensional random quantizers
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• Matching random samples in many dimensions
• On optimal matchings
• Optimal Transport
• Rates of convergence for partial mass problems
• Similarity of samples and trimming
• Some asymptotic theory for the bootstrap
• The integrability of the square exponential transportation cost
• The optimal partial transport problem
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• Uniqueness and approximate computation of optimal incomplete transportation plans

Cited in

(8)

• Uniqueness and approximate computation of optimal incomplete transportation plans
• Central limit theorems for empirical transportation cost in general dimension
• An explicit bound on the transportation cost distance
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Rates of convergence for partial mass problems
• Parametrization of Random Vectors in Polynomial Chaos Expansions via Optimal Transportation
• Sharp convergence rates for empirical optimal transport with smooth costs
• The integrability of the square exponential transportation cost

This page was built for publication: The empirical cost of optimal incomplete transportation

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