A PDE approach to a 2-dimensional matching problem

DOI10.1007/S00440-018-0837-XzbMATH Open1480.60017arXiv1611.04960OpenAlexW2963434094WikidataQ62043464 ScholiaQ62043464MaRDI QIDQ1729699FDOQ1729699

Authors: Luigi Ambrosio, Federico Stra, Dario Trevisan 

Publication date: 28 February 2019

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: We prove asymptotic results for 2-dimensional random matching problems. In particular, we obtain the leading term in the asymptotic expansion of the expected quadratic transportation cost for empirical measures of two samples of independent uniform random variables in the square. Our technique is based on a rigorous formulation of the challenging PDE ansatz by S. Caracciolo et al. (Phys. Rev. E, {�f 90} 012118, 2014) that "linearise" the Monge-Amp`ere equation.

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

Recommendations

• Convergence of asymptotic costs for random Euclidean matching problems
• Finer estimates on the \(2\)-dimensional matching problem
• New estimates on the matching problem
• On the quadratic random matching problem in two-dimensional domains
• On the optimal map in the 2-dimensional random matching problem

zbMATH Keywords

optimal transportgeometric probabilityminimal matching

Mathematics Subject Classification ID

Optimal transportation (49Q22) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Geometric probability and stochastic geometry (60D05) Matching models (91B68)

Cites Work

• Gradient flows in metric spaces and in the space of probability measures
• On optimal matchings
• Asymptotics for transportation cost in high dimensions
• Probability theory of classical Euclidean optimization problems
• Almost sure convergence of the minimum bipartite matching functional in Euclidean space
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• The concentration of measure phenomenon
• Combinatorial Optimization Over Two Random Point Sets
• Curvature and the eigenvalues of the Laplacian
• Some Properties of Viscosity Solutions of Hamilton-Jacobi Equations
• Bakry-Émery curvature-dimension condition and Riemannian Ricci curvature bounds
• On the equivalence of the entropic curvature-dimension condition and Bochner's inequality on metric measure spaces
• Nonlinear Diffusion Equations and Curvature Conditions in Metric Measure Spaces
• Title not available (Why is that?)
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• The transportation cost from the uniform measure to the empirical measure in dimension \(\geq 3\)
• Analysis and geometry on groups
• Title not available (Why is that?)
• On the rate of convergence in Wasserstein distance of the empirical measure
• Upper and lower bounds for stochastic processes. Modern methods and classical problems
• Topics in Harmonic Analysis Related to the Littlewood-Paley Theory. (AM-63)
• Semicontinuity problems in the calculus of variations
• Minimax grid matching and empirical measures
• Analysis and geometry of Markov diffusion operators
• Duality on gradient estimates and Wasserstein controls
• Heat kernel bounds on metric measure spaces and some applications
• Analysis for diffusion processes on Riemannian manifolds
• Optimal transport from Lebesgue to Poisson
• A Topological Application of the Isoperimetric Inequality
• Differential equations methods for the Monge-Kantorovich mass transfer problem
• Matching random samples in many dimensions
• Title not available (Why is that?)
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• Equivalent semigroup properties for the curvature-dimension condition
• Limit theorems for random normalized distortion
• Title not available (Why is that?)
• The Trace of the Heat Kernel in Lipschitz Domains
• On the stochastic convergence of representations based on Wasserstein metrics
• On optimal matching of Gaussian samples

Cited In (55)

• Limit distribution theory for smooth \(p\)-Wasserstein distances
• Central limit theorems for general transportation costs
• Annealed quantitative estimates for the quadratic 2D-discrete random matching problem
• On minimum spanning trees for random Euclidean bipartite graphs
• Sharp PDE estimates for random two-dimensional bipartite matching with power cost function
• On optimal matching of Gaussian samples. III
• A simple Fourier analytic proof of the AKT optimal matching theorem
• The Dyck bound in the concave 1-dimensional random assignment model
• Wasserstein convergence rates for empirical measures of subordinated processes on noncompact manifolds
• Wasserstein asymptotics for the empirical measure of fractional Brownian motion on a flat torus
• Central limit theorems for combinatorial optimization problems on sparse Erdős-Rényi graphs
• Random matching in 2D with exponent 2 for Gaussian densities
• Empirical measures and random walks on compact spaces in the quadratic Wasserstein metric
• The Wasserstein distance to the circular law
• Asymptotics of smoothed Wasserstein distances
• Gravitational allocation for uniform points on the sphere
• Berry-Esseen smoothing inequality for the Wasserstein metric on compact Lie groups
• Uniform rates of the Glivenko-Cantelli convergence and their use in approximating Bayesian inferences
• Precise limit in Wasserstein distance for conditional empirical measures of Dirichlet diffusion processes
• Convergence of asymptotic costs for random Euclidean matching problems
• Convergence in Wasserstein distance for empirical measures of Dirichlet diffusion processes on manifolds
• A fluctuation result for the displacement in the optimal matching problem
• Convergence in Wasserstein distance for empirical measures of semilinear SPDEs
• Wasserstein convergence rate for empirical measures on noncompact manifolds
• On optimal matching of Gaussian samples
• Finer estimates on the \(2\)-dimensional matching problem
• On the quadratic random matching problem in two-dimensional domains
• Penalization of barycenters in the Wasserstein space
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Random assignment problems on \(2d\) manifolds
• Some results on the optimal matching problem for the Jacobi model
• Limit theorems in Wasserstein distance for empirical measures of diffusion processes on Riemannian manifolds
• Asymptotics for Strassen's optimal transport problem
• There is no stationary cyclically monotone Poisson matching in 2d
• On the optimal map in the 2-dimensional random matching problem
• Optimal transport methods for combinatorial optimization over two random point sets
• Sequential propagation of chaos for mean-field BSDE systems
• \(q\)-moment estimates for the singular \(p\)-Laplace equation and applications
• Euclidean random matching in 2D for non-constant densities
• A variational approach to regularity theory in optimal transportation
• Empirical approximation to invariant measures for McKean-Vlasov processes: mean-field interaction vs self-interaction
• Title not available (Why is that?)
• Empirical measures: regularity is a counter-curse to dimensionality
• A Wasserstein inequality and minimal Green energy on compact manifolds
• Average optimal cost for the Euclidean TSP in one dimension
• Wasserstein convergence for empirical measures of subordinated diffusions on Riemannian manifolds
• Asymptotic analysis of the optimal cost in some transportation problems with random locations
• Large and moderate deviations for matching problems and empirical discrepancies
• One-dimensional empirical measures, order statistics, and Kantorovich transport distances
• New estimates on the matching problem
• Optimal Matching of Random Samples and Rates of Convergence of Empirical Measures
• Riesz energy, \(L^2\) discrepancy, and optimal transport of determinantal point processes on the sphere and the flat torus
• Antithetic multilevel sampling method for nonlinear functionals of measure
• On the Wasserstein distance between classical sequences and the Lebesgue measure
• The rival coffee shop problem

This page was built for publication: A PDE approach to a 2-dimensional matching problem

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