A simple Fourier analytic proof of the AKT optimal matching theorem
From MaRDI portal
(Redirected from Publication:2075321)
Existence of optimal solutions to problems involving randomness (49J55) Optimal transportation (49Q22) Heat and other parabolic equation methods for PDEs on manifolds (58J35) Geometric probability and stochastic geometry (60D05) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Order statistics; empirical distribution functions (62G30)
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
- 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
- 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?)
- Introduction to strong mixing conditions. Vol. 3.
- Mass transportation problems. Vol. 1: Theory. Vol. 2: Applications
- Matching random samples in many dimensions
- Matching Theorems and Empirical Discrepancy Computations using Majorizing Measures
- 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 integrability of the square exponential transportation cost
- The Speed of Mean Glivenko-Cantelli Convergence
- 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
(16)- 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
- A fluctuation result for the displacement in the optimal matching problem
- Berry-Esseen smoothing inequality for the Wasserstein metric on compact Lie groups
- The double matching problem: Analytic and real frequency solutions
- 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
- A unifying approach to distributional limits for empirical optimal transport
- Limit distribution theory for smooth \(p\)-Wasserstein distances
- Correction to: ``Transport inequalities on Euclidean spaces for non-Euclidean metrics
- Sharp PDE estimates for random two-dimensional bipartite matching with power cost function
- Optimal matching problem on the Boolean cube
- Convergence of empirical optimal transport in unbounded settings
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)
