• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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.05466v2
Date
2016
Journal name
Journal of Mathematical Imaging and Vision
Volume
56
Number
2
Publisher
Kluwer Academic Publishers
Pages
238-259
Publication identifier
10.1007/s10851-016-0653-9
Metadata
Show full item record
Author(s)
Schmitzer, Bernhard
Abstract (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; Multiscale

Related items

Showing items related by title and author.

  • Thumbnail
    Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems 
    Schmitzer, Bernhard (2016) Document de travail / Working paper
  • Thumbnail
    Scaling Algorithms for Unbalanced Transport Problems 
    Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier (2018) Article accepté pour publication ou publié
  • Thumbnail
    Convergence of Entropic Schemes for Optimal Transport and Gradient Flows 
    Carlier, Guillaume; Duval, Vincent; Peyré, Gabriel; Schmitzer, Bernhard (2017) Article accepté pour publication ou publié
  • Thumbnail
    An Interpolating Distance between Optimal Transport and Fisher-Rao 
    Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier (2010) Article accepté pour publication ou publié
  • Thumbnail
    Unbalanced Optimal Transport: Dynamic and Kantorovich Formulations 
    Chizat, Lénaïc; Peyré, Gabriel; Schmitzer, Bernhard; Vialard, François-Xavier (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo