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 (29)

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

This page was built for publication: A parallel method for earth mover's distance