Preconditioning of optimal transport

Max Kuang; Estebang Tabak

doi:10.1137/16M1074953

Preconditioning of optimal transport

Max Kuang, Estebang Tabak

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

A preconditioning procedure is developed for the L2 and more general optimal transport problems. The procedure is based on a family of affine map pairs which transforms the original measures into two new measures that are closer to each other while preserving the optimality of solutions. It is proved that the preconditioning procedure minimizes the remaining transportation cost among all admissible affine maps. The procedure can be used on both continuous measures and finite sample sets from distributions. In numerical examples, the procedure is applied to multivariate normal distributions, to a two-dimensional shape transform problem, and to color-transfer problems.

Original language	English (US)
Pages (from-to)	A1793-A1810
Journal	SIAM Journal on Scientific Computing
Volume	39
Issue number	4
DOIs	https://doi.org/10.1137/16M1074953
State	Published - 2017

Keywords

Matrix factorization
Optimal transport
Preconditioning

ASJC Scopus subject areas

Computational Mathematics
Applied Mathematics

Access to Document

10.1137/16M1074953

Cite this

@article{3d434fcf1860492db42b1af16323a9b8,

title = "Preconditioning of optimal transport",

abstract = "A preconditioning procedure is developed for the L2 and more general optimal transport problems. The procedure is based on a family of affine map pairs which transforms the original measures into two new measures that are closer to each other while preserving the optimality of solutions. It is proved that the preconditioning procedure minimizes the remaining transportation cost among all admissible affine maps. The procedure can be used on both continuous measures and finite sample sets from distributions. In numerical examples, the procedure is applied to multivariate normal distributions, to a two-dimensional shape transform problem, and to color-transfer problems.",

keywords = "Matrix factorization, Optimal transport, Preconditioning",

author = "Max Kuang and Estebang Tabak",

note = "Funding Information: ∗Submitted to the journal{\textquoteright}s Methods and Algorithms for Scientific Computing section May 12, 2016; accepted for publication (in revised form) May 17, 2017; published electronically August 31, 2017. http://www.siam.org/journals/sisc/39-4/M107495.html Funding: This work was supported by grants from the Office of Naval Research and the NYU-AIG Partnership on Global Resilience. †Courant Institute, New York University, New York, NY 10012 (kuang@cims.nyu.edu, tabak@ cims.nyu.edu). Publisher Copyright: {\textcopyright} 2017 SIAM.",

year = "2017",

doi = "10.1137/16M1074953",

language = "English (US)",

volume = "39",

pages = "A1793--A1810",

journal = "SIAM Journal of Scientific Computing",

issn = "1064-8275",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Preconditioning of optimal transport

AU - Kuang, Max

AU - Tabak, Estebang

N1 - Funding Information: ∗Submitted to the journal’s Methods and Algorithms for Scientific Computing section May 12, 2016; accepted for publication (in revised form) May 17, 2017; published electronically August 31, 2017. http://www.siam.org/journals/sisc/39-4/M107495.html Funding: This work was supported by grants from the Office of Naval Research and the NYU-AIG Partnership on Global Resilience. †Courant Institute, New York University, New York, NY 10012 (kuang@cims.nyu.edu, tabak@ cims.nyu.edu). Publisher Copyright: © 2017 SIAM.

PY - 2017

Y1 - 2017

N2 - A preconditioning procedure is developed for the L2 and more general optimal transport problems. The procedure is based on a family of affine map pairs which transforms the original measures into two new measures that are closer to each other while preserving the optimality of solutions. It is proved that the preconditioning procedure minimizes the remaining transportation cost among all admissible affine maps. The procedure can be used on both continuous measures and finite sample sets from distributions. In numerical examples, the procedure is applied to multivariate normal distributions, to a two-dimensional shape transform problem, and to color-transfer problems.

AB - A preconditioning procedure is developed for the L2 and more general optimal transport problems. The procedure is based on a family of affine map pairs which transforms the original measures into two new measures that are closer to each other while preserving the optimality of solutions. It is proved that the preconditioning procedure minimizes the remaining transportation cost among all admissible affine maps. The procedure can be used on both continuous measures and finite sample sets from distributions. In numerical examples, the procedure is applied to multivariate normal distributions, to a two-dimensional shape transform problem, and to color-transfer problems.

KW - Matrix factorization

KW - Optimal transport

KW - Preconditioning

UR - http://www.scopus.com/inward/record.url?scp=85028649917&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028649917&partnerID=8YFLogxK

U2 - 10.1137/16M1074953

DO - 10.1137/16M1074953

M3 - Article

AN - SCOPUS:85028649917

SN - 1064-8275

VL - 39

SP - A1793-A1810

JO - SIAM Journal of Scientific Computing

JF - SIAM Journal of Scientific Computing

IS - 4

ER -

Preconditioning of optimal transport

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this