The empirical cost of optimal incomplete transportation

DOI10.1214/12-AOP812zbMATH Open1291.60011arXiv1310.0924MaRDI QIDQ378795FDOQ378795

Carlos Matrán, Eustasio Del Barrio

Publication date: 12 November 2013

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

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.

Full work available at URL: https://arxiv.org/abs/1310.0924

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

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)

Cites Work

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

Cited In (4)

• Parametrization of Random Vectors in Polynomial Chaos Expansions via Optimal Transportation
• The integrability of the square exponential transportation cost
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• An explicit bound on the transportation cost distance

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)