Name
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. In this paper, we characterize a quadratic regularizer for transport with linear ground distance 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1137/17M1132665 | SIAM JOURNAL ON SCIENTIFIC COMPUTING |
Keywords | Field | DocType |
optimal transportation,graphs,matching,flow | Convergence (routing),Flow network,Discrete mathematics,Uniqueness,Mathematical optimization,Quadratic growth,Quadratic equation,Probability distribution,Regularization (mathematics),Mathematics,Regularization perspectives on support vector machines | Journal |
Volume | Issue | ISSN |
40 | 4 | 1064-8275 |
Citations | PageRank | References |
1 | 0.35 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Montacer Essid | 1 | 1 | 0.35 |
| Justin Solomon | 2 | 827 | 48.48 |