An iterative scheme for solving the optimal transportation problem

DOI10.1007/S00526-013-0673-XzbMATH Open1297.49051arXiv1208.5172OpenAlexW2062515210MaRDI QIDQ406682FDOQ406682

Authors: Jun Kitagawa 

Publication date: 9 September 2014

Published in: Calculus of Variations and Partial Differential Equations (Search for Journal in Brave)

Abstract: We demonstrate an iterative scheme to approximate the optimal transportation problem with a discrete target measure under certain standard conditions on the cost function. Additionally, we give a finite upper bound on the number of iterations necessary for the scheme to terminate, in terms of the error tolerance and number of points in the support of the discrete target measure.

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

Recommendations

• A fast approach to optimal transport: the back-and-forth method
• Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach
• Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
• Iterative Bregman projections for regularized transportation problems
• Discrete optimal transport: complexity, geometry and applications

zbMATH Keywords

iterative schemediscrete target measureoptimal transportation problem

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Variational problems in a geometric measure-theoretic setting (49Q20) Monge-Ampère equations (35J96) Discrete approximations in optimal control (49M25)

Cites Work

• Optimal Transport
• On the regularity of solutions of optimal transportation problems
• Regularity of potential functions of the optimal transportation problem
• Regularity of optimal maps on the sphere: the quadratic cost and the reflector antenna
• On the numerical solution of the equation \(\frac{\partial ^ 2z\partial ^ 2z}{\partial x^ 2\partial y^ 2}-(\frac{\partial ^ 2z}{\partial x\partial y})^ 2=f\) and its discretizations. I
• Continuity, curvature, and the general covariance of optimal transportation
• On the design of a reflector antenna. II
• Title not available (Why is that?)
• Determination of reflector surfaces from near-field scattering data. II: Numerical solution
• Computational algorithms for constructing reflectors

Cited In (24)

• On the numerical solution of the near field refractor problem
• Approximation properties of slice-matching operators
• Optimal transport: discretization and algorithms
• A damped Newton algorithm for generated Jacobian equations
• The boundary method for semi-discrete optimal transport partitions and Wasserstein distance computation
• Title not available (Why is that?)
• Optimal transport via a Monge-Ampère optimization problem
• An overview of mathematical modeling of geometric optics problems involving refraction
• Fast iterative solvers for an optimal transport problem
• A stochastic multi-layer algorithm for semi-discrete optimal transport with applications to texture synthesis and style transfer
• Convergence of a Newton algorithm for semi-discrete optimal transport
• A simple method for the optimal transportation
• An iterative method for generated Jacobian equations
• Far-field reflector problem and intersection of paraboloids
• Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
• Iterative scheme for solving optimal transportation problems arising in reflector design
• The transport map computed by iterated function system
• On the Degeneracy of Optimal Transportation
• An iteration method for the solution of the transport problem with an additional linear restriction and an estimate of the number of iterations
• The application of weights in the weighted arithmetic mean to obtain the optimal solution of Degenerate Transportation Problem
• Title not available (Why is that?)
• On the numerical solution of the far field refractor problem
• Multivariate ranks and quantiles using optimal transport: consistency, rates and nonparametric testing
• A Newton algorithm for semidiscrete optimal transport with storage fees

This page was built for publication: An iterative scheme for solving the optimal transportation problem

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