Quadratically regularized optimal transport on graphs
From MaRDI portal
Publication:3174762
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 1239298 (Why is no real title available?)
- scientific article; zbMATH DE number 1909499 (Why is no real title available?)
- scientific article; zbMATH DE number 2107836 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A Continuous Model of Transportation
- A Note on Asymptotic Joint Normality
- A Primal Method for Minimal Cost Flows with Applications to the Assignment and Transportation Problems
- A computational fluid mechanics solution to the Monge-Kantorovich mass transfer problem
- A parallel method for earth mover's distance
- A polynomial time primal network simplex algorithm for minimum cost flows
- Absolute continuity and summability of transport densities: simpler proofs and new estimates
- Adjustment of an Inverse Matrix Corresponding to a Change in One Element of a Given Matrix
- Algorithm 915: SuiteSparseQR: multifrontal multithreaded rank-revealing sparse QR factorization
- Analysis and generalizations of the linearized Bregman method
- Computations of optimal transport distance with Fisher information regularization
- Computing and Combinatorics
- Concerning nonnegative matrices and doubly stochastic matrices
- Earth mover's distances on discrete surfaces
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Faster approximation schemes for fractional multicommodity flow problems
- Generalized preconditioning and undirected minimum-cost flow
- Gradient flows of the entropy for finite Markov chains
- Incremental computation of pseudo-inverse of Laplacian
- Iterative Bregman projections for regularized transportation problems
- Monge's transport problem on a Riemannian manifold
- Negative-weight shortest paths and unit capacity minimum cost flow in \(\tilde{O}(m^{10/7}\log W)\) time (extended abstract)
- Network flows. Theory, algorithms, and applications.
- 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
- The earth mover's distance as a metric for image retrieval
- Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems
Cited in
(25)- Algorithms for Euclidean-regularised optimal transport
- Optimal transport problems regularized by generic convex functions: a geometric and algorithmic approach
- Approximate Wasserstein attraction flows for dynamic mass transport over networks
- Quadratically regularized optimal transport
- Discrete Optimal Transport with Independent Marginals is #P-Hard
- Regularized optimal transport and the rot mover's distance
- Ground metric learning on graphs
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
- scientific article; zbMATH DE number 7370538 (Why is no real title available?)
- Coupling matrix manifolds assisted optimization for optimal transport problems
- A generalized Brezis-Lieb lemma on graphs and its application to Kirchhoff type equations
- The dynamical Schrödinger problem in abstract metric spaces
- Empirical regularized optimal transport: statistical theory and applications
- Accelerated Bregman Primal-Dual Methods Applied to Optimal Transport and Wasserstein Barycenter Problems
- Quantum entropic regularization of matrix-valued optimal transport
- Quantitative stability of regularized optimal transport and convergence of Sinkhorn's algorithm
- Semi-discrete optimal transport: hardness, regularization and numerical solution
- Fast iterative solution of the optimal transport problem on graphs
- A structural model on a hypercube represented by optimal transport
- Uniform approximation of continuous couplings
- Geometry of graph partitions via optimal transport
- Computation of optimal transport on discrete metric measure spaces
- Multilevel optimal transport: a fast approximation of Wasserstein-1 distances
- Hausdorff and Wasserstein metrics on graphs and other structured data
- Stability and sample complexity of divergence regularized optimal transport
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)
