A simple Fourier analytic proof of the AKT optimal matching theorem

DOI10.1214/20-AAP1656zbMath1482.60011arXiv1909.06193OpenAlexW2972726987MaRDI QIDQ2075321

Sergey G. Bobkov, Michel Ledoux

Publication date: 14 February 2022

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

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

zbMATH Keywords

Fourier analysisempirical measureoptimal matchingAjtai-Komlós-Tusnády theoremheat kernel smoothing

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Order statistics; empirical distribution functions (62G30) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Heat and other parabolic equation methods for PDEs on manifolds (58J35) Existence of optimal solutions to problems involving randomness (49J55) Optimal transportation (49Q22)

Related Items

A fluctuation result for the displacement in the optimal matching problem, Berry-Esseen smoothing inequality for the Wasserstein metric on compact Lie groups, There is no stationary cyclically monotone Poisson matching in 2d, Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures, Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric, Optimal transport methods for combinatorial optimization over two random point sets, Equidistribution of random walks on compact groups. II: The Wasserstein metric, A Wasserstein inequality and minimal Green energy on compact manifolds, Wasserstein asymptotics for the empirical measure of fractional Brownian motion on a flat torus

Cites Work

• Constructive quantization: approximation by empirical measures
• On the rate of convergence in Wasserstein distance of the empirical measure
• Minimax grid matching and empirical measures
• Basic properties of strong mixing conditions. A survey and some open questions
• On optimal matchings
• Matching random samples in many dimensions
• Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
• The integrability of the square exponential transportation cost
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• Probability theory of classical Euclidean optimization problems
• Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
• A PDE approach to a 2-dimensional matching problem
• Wasserstein distance, Fourier series and applications
• Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
• Combinatorial Optimization Over Two Random Point Sets
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• Real Analysis and Probability
• Gravitational allocation on the sphere
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Comparison between W₂ distance and Ḣ⁻¹ norm, and Localization of Wasserstein distance
• Upper and Lower Bounds for Stochastic Processes
• The Speed of Mean Glivenko-Cantelli Convergence
• A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound
• Semicontinuity problems in the calculus of variations
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item