Quadratically regularized optimal transport on graphs
From MaRDI portal
Publication:3174762
DOI10.1137/17M1132665zbMATH Open1394.65041arXiv1704.08200OpenAlexW2962792820MaRDI QIDQ3174762FDOQ3174762
Authors: Montacer Essid, Justin Solomon 
Publication date: 18 July 2018
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: Optimal transportation provides a means of lifting distances between points on a geometric domain to distances between signals over the domain, expressed as probability distributions. On a graph, transportation problems can be used to express challenging tasks involving matching supply to demand with minimal shipment expense; in discrete language, these become minimum-cost network flow problems. Regularization typically is needed to ensure uniqueness for the linear ground distance case and to improve optimization convergence; state-of-the-art techniques employ entropic regularization on the transportation matrix. In this paper, we explore a quadratic alternative to entropic regularization for transport over a graph. We theoretically analyze the behavior of quadratically-regularized graph transport, characterizing how regularization affects the structure of flows in the regime of small but nonzero regularization. We further exploit elegant second-order structure in the dual of this problem to derive an easily-implemented Newton-type optimization algorithm.
Full work available at URL: https://arxiv.org/abs/1704.08200
Recommendations
Numerical optimization and variational techniques (65K10) Programming involving graphs or networks (90C35) Flows in graphs (05C21) Transportation, logistics and supply chain management (90B06)
Cites Work
- Network flows. Theory, algorithms, and applications.
- The earth mover's distance as a metric for image retrieval
- Title not available (Why is that?)
- Concerning nonnegative matrices and doubly stochastic matrices
- Title not available (Why is that?)
- On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are Known
- Optimal transport for applied mathematicians. Calculus of variations, PDEs, and modeling
- Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
- Title not available (Why is that?)
- A polynomial time primal network simplex algorithm for minimum cost flows
- Gradient flows of the entropy for finite Markov chains
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- Iterative Bregman projections for regularized transportation problems
- Incremental computation of pseudo-inverse of Laplacian
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Title not available (Why is that?)
- A Note on Asymptotic Joint Normality
- Analysis and generalizations of the linearized Bregman method
- Computing and Combinatorics
- Monge's transport problem on a Riemannian manifold
- Absolute continuity and summability of transport densities: simpler proofs and new estimates
- A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
- A Continuous Model of Transportation
- A parallel method for earth mover's distance
- Earth mover's distances on discrete surfaces
- Computations of optimal transport distance with Fisher information regularization
- Faster approximation schemes for fractional multicommodity flow problems
- Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
- Generalized preconditioning and undirected minimum-cost flow
Cited In (25)
- Hausdorff and Wasserstein metrics on graphs and other structured data
- Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
- Computation of optimal transport on discrete metric measure spaces
- Geometry of graph partitions via optimal transport
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- Algorithms for Euclidean-regularised optimal transport
- A structural model on a hypercube represented by optimal transport
- Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
- A generalized Brezis-Lieb lemma on graphs and its application to Kirchhoff type equations
- Quantum entropic regularization of matrix-valued optimal transport
- Ground metric learning on graphs
- Empirical regularized optimal transport: statistical theory and applications
- Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
- Quadratically regularized optimal transport
- Uniform approximation of continuous couplings
- Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach
- Approximate Wasserstein attraction flows for dynamic mass transport over networks
- Stability and sample complexity of divergence regularized optimal transport
- Title not available (Why is that?)
- Coupling matrix manifolds assisted optimization for optimal transport problems
- The dynamical Schrödinger problem in abstract metric spaces
- Regularized optimal transport and the rot mover's distance
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
- Fast iterative solution of the optimal transport problem on graphs
Uses Software
This page was built for publication: Quadratically regularized optimal transport on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3174762)
