A Sparse Multiscale Algorithm for Dense Optimal Transport
Schmitzer, Bernhard (2016), A Sparse Multiscale Algorithm for Dense Optimal Transport, Journal of Mathematical Imaging and Vision, 56, 2, p. 238-259. 10.1007/s10851-016-0653-9
Type
Article accepté pour publication ou publiéExternal document link
https://arxiv.org/abs/1510.05466v2Date
2016Journal name
Journal of Mathematical Imaging and VisionVolume
56Number
2Publisher
Kluwer Academic Publishers
Pages
238-259
Publication identifier
Metadata
Show full item recordAbstract (EN)
Discrete optimal transport solvers do not scale well on dense large problems since they do not explicitly exploit the geometric structure of the cost function. In analogy to continuous optimal transport, we provide a framework to verify global optimality of a discrete transport plan locally. This allows the construction of an algorithm to solve large dense problems by considering a sequence of sparse problems instead. The algorithm lends itself to being combined with a hierarchical multiscale scheme. Any existing discrete solver can be used as internal black-box. We explicitly describe how to select the sparse sub-problems for several cost functions, including the noisy squared Euclidean distance. Significant reductions in run-time and memory requirements have been observed.Subjects / Keywords
Optimal transport; Convex optimization; Sparsity; MultiscaleRelated items
Showing items related by title and author.
-
Schmitzer, Bernhard (2016) Document de travail / Working paper
-
Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier (2018) Article accepté pour publication ou publié
-
Carlier, Guillaume; Duval, Vincent; Peyré, Gabriel; Schmitzer, Bernhard (2017) Article accepté pour publication ou publié
-
Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier (2010) Article accepté pour publication ou publié
-
Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier (2018) Article accepté pour publication ou publié