A simple Fourier analytic proof of the AKT optimal matching theorem
From MaRDI portal
Publication:2075321
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)
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.
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
Cites work
- scientific article; zbMATH DE number 434646 (Why is no real title available?)
- scientific article; zbMATH DE number 434647 (Why is no real title available?)
- scientific article; zbMATH DE number 434648 (Why is no real title available?)
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- A PDE approach to a 2-dimensional matching problem
- A Simple Proof of the $O( \sqrt{n} \log^{3 / 4} n )$ Upright Matching Bound
- Basic properties of strong mixing conditions. A survey and some open questions
- Combinatorial Optimization Over Two Random Point Sets
- Comparison between \(W_2\) distance and \(\dot{H}^{-1}\) norm, and localization of Wasserstein distance
- Constructive quantization: approximation by empirical measures
- Gravitational allocation on the sphere
- Introduction to strong mixing conditions. Vol. 3.
- Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
- Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
- Matching random samples in many dimensions
- Minimax grid matching and empirical measures
- On optimal matchings
- On the rate of convergence in Wasserstein distance of the empirical measure
- One-dimensional empirical measures, order statistics, and Kantorovich transport distances
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Probability theory of classical Euclidean optimization problems
- Real Analysis and Probability
- Semicontinuity problems in the calculus of variations
- The Speed of Mean Glivenko-Cantelli Convergence
- The integrability of the square exponential transportation cost
- The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
- Tight bounds for minimax grid matching with applications to the average case analysis of algorithms
- Upper and lower bounds for stochastic processes. Modern methods and classical problems
- Wasserstein distance, Fourier series and applications
Cited in
(14)- A unifying approach to distributional limits for empirical optimal transport
- Limit distribution theory for smooth \(p\)-Wasserstein distances
- Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric
- A Wasserstein inequality and minimal Green energy on compact manifolds
- Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
- Berry-Esseen smoothing inequality for the Wasserstein metric on compact Lie groups
- Sharp PDE estimates for random two-dimensional bipartite matching with power cost function
- Equidistribution of random walks on compact groups. II: The Wasserstein metric
- The double matching problem: Analytic and real frequency solutions
- A fluctuation result for the displacement in the optimal matching problem
- Wasserstein asymptotics for the empirical measure of fractional Brownian motion on a flat torus
- Optimal transport methods for combinatorial optimization over two random point sets
- Correction to: ``Transport inequalities on Euclidean spaces for non-Euclidean metrics
- There is no stationary cyclically monotone Poisson matching in 2d
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)
