A parallel method for earth mover's distance

DOI10.1007/s10915-017-0529-1zbMath1398.65124OpenAlexW2744789862MaRDI QIDQ1747622

Ernest K. Ryu, Wilfrid Gangbo, Wotao Yin, Wuchen Li, Stanley J. Osher

Publication date: 26 April 2018

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10915-017-0529-1

zbMATH Keywords

primal-dual algorithmoptimal transportcompressed sensingearth mover's distance\(L_1\) regularization

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Variational problems in a geometric measure-theoretic setting (49Q20) Parallel numerical computation (65Y05)

Related Items

Generalized unnormalized optimal transport and its fast algorithms, Supervised Optimal Transport, An efficient algorithm for matrix-valued and vector-valued optimal mass transport, Quadratically Regularized Optimal Transport on Graphs, A structure-preserving finite element discretization for the time-dependent Nernst-Planck equation, A mean field game inverse problem, Vector and Matrix Optimal Mass Transport: Theory, Algorithm, and Applications, Tropical optimal transport and Wasserstein distances, Unbalanced and partial \(L_1\) Monge-Kantorovich problem: a scalable parallel first-order method, Numerical solution of Monge-Kantorovich equations via a dynamic formulation, Deforming Surface Meshes, Dynamical optimal transport of nonlinear control-affine systems, On the Convergence of Continuous and Discrete Unbalanced Optimal Transport Models for 1-Wasserstein Distance, On computing medians of marked point process data under edit distance, Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM, Fast sinkhorn. II: Collinear triangular matrix and linear time accurate computation of optimal transport, A machine learning framework for geodesics under spherical Wasserstein-Fisher-Rao metric and its application for weighted sample generation, A second-order numerical method for the aggregation equations, Unnormalized optimal transport, Multilevel Optimal Transport: A Fast Approximation of Wasserstein-1 Distances, \(p\)-Laplace diffusion for distance function estimation, optimal transport approximation, and image enhancement, Topological data assimilation using Wasserstein distance, Computational Methods for First-Order Nonlocal Mean Field Games with Applications, Acceleration of primal-dual methods by preconditioning and simple subproblem procedures, Fast Entropic Regularized Optimal Transport Using Semidiscrete Cost Approximation, On the Computation of Kantorovich--Wasserstein Distances Between Two-Dimensional Histograms by Uncapacitated Minimum Cost Flows, Solving Large-Scale Optimization Problems with a Convergence Rate Independent of Grid Size, Diagnosing forward operator error using optimal transport, A particle-evolving method for approximating the optimal transport plan

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Nonlinear total variation based noise removal algorithms
• Augmented Lagrangian methods for transport optimization, mean field games and degenerate elliptic equations
• Absolute continuity and summability of transport densities: simpler proofs and new estimates
• The earth mover's distance as a metric for image retrieval
• A first-order primal-dual algorithm for convex problems with applications to imaging
• A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
• An optimal transport approach for seismic tomography: application to 3D full waveform inversion
• Optimal Transport with Proximal Splitting
• Convergence Analysis of Primal-Dual Algorithms for a Saddle-Point Problem: From Contraction Perspective
• The Split Bregman Method for L1-Regularized Problems
• Differential equations methods for the Monge-Kantorovich mass transfer problem
• Proximal Methods for Stationary Mean Field Games with Local Couplings
• Earth mover's distances on discrete surfaces
• A numerical solution to Monge’s problem with a Finsler distance as cost
• Bregman Iterative Algorithms for $\ell_1$-Minimization with Applications to Compressed Sensing
• A Continuous Model of Transportation