A simple Fourier analytic proof of the AKT optimal matching theorem

DOI10.1214/20-AAP1656zbMATH Open1482.60011arXiv1909.06193OpenAlexW2972726987MaRDI QIDQ2075321FDOQ2075321

S. G. Bobkov, Michel Ledoux

Publication date: 14 February 2022

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

Abstract: We present a short and elementary proof of the Ajtai-Koml'os-Tusn'ady (AKT) optimal matching theorem in dimension 2 via Fourier analysis and a smoothing argument. The upper bound applies to more general families of samples, including dependent variables, of interest in the study of rates of convergence for empirical measures. Following the recent pde approach by L. Ambrosio, F. Stra and D. Trevisan, we also adapt a simple proof of the lower bound.

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

Recommendations

• scientific article; zbMATH DE number 434647
• A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound
• On the optimal map in the 2-dimensional random matching problem
• Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
• scientific article; zbMATH DE number 434648

zbMATH Keywords

Fourier analysisempirical measureoptimal matching[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Ajtai-Koml%EF%BF%BD%EF%BF%BDs-Tusn%EF%BF%BD%EF%BF%BDdy+theorem&go=Go Ajtai-Koml��s-Tusn��dy theorem]heat kernel smoothing

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

• Equidistribution of random walks on compact groups. II: The Wasserstein metric
• Wasserstein asymptotics for the empirical measure of fractional Brownian motion on a flat torus
• Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric
• Berry-Esseen smoothing inequality for the Wasserstein metric on compact Lie groups
• A unifying approach to distributional limits for empirical optimal transport
• Limit distribution theory for smooth \(p\)-Wasserstein distances
• A fluctuation result for the displacement in the optimal matching problem
• There is no stationary cyclically monotone Poisson matching in 2d
• The double matching problem: Analytic and real frequency solutions
• Optimal transport methods for combinatorial optimization over two random point sets
• Correction to: ``Transport inequalities on Euclidean spaces for non-Euclidean metrics
• A Wasserstein inequality and minimal Green energy on compact manifolds
• Sharp PDE estimates for random two-dimensional bipartite matching with power cost function
• Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures

This page was built for publication: A simple Fourier analytic proof of the AKT optimal matching theorem

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