• 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

Fast Transport Optimization for Monge Costs on the Circle

Delon, Julie; Salomon, Julien; Sobolevski, Andrei (2010), Fast Transport Optimization for Monge Costs on the Circle, SIAM Journal on Applied Mathematics, 70, 7, p. 2239-2258. http://dx.doi.org/10.1137/090772708

Type
Article accepté pour publication ou publié
External document link
http://hal.archives-ouvertes.fr/hal-00362834/en/
Date
2010
Journal name
SIAM Journal on Applied Mathematics
Volume
70
Number
7
Publisher
SIAM
Pages
2239-2258
Publication identifier
http://dx.doi.org/10.1137/090772708
Metadata
Show full item record
Author(s)
Delon, Julie
Salomon, Julien
Sobolevski, Andrei
Abstract (EN)
Consider the problem of optimally matching two measures on the circle, or equivalently two periodic measures on the real line, and suppose the cost of matching two points satisfies the Monge condition. We introduce a notion of locally optimal transport plan, motivated by the weak KAM (Aubry-Mather) theory, and show that all locally optimal transport plans are conjugate to shifts. This theory is applied to a transportation problem arising in image processing: for two sets of point masses, both of which have the same total mass, find an optimal transport plan with respect to a given cost function that satisfies the Monge condition. For the case of N real-valued point masses we present an O(N log epsilon) algorithm that approximates the optimal cost within epsilon; when all masses are integer multiples of 1/M, the algorithm gives an exact solution in O(N log M) operations.
Subjects / Keywords
Monge-Kantorovich problem; Aubry-Mather (weak KAM) theory; Optimization and Control

Related items

Showing items related by title and author.

  • Thumbnail
    Local matching indicators for concave transport costs 
    Sobolevski, Andrei; Salomon, Julien; Delon, Julie (2010) Article accepté pour publication ou publié
  • Thumbnail
    Local Matching Indicators for Transport Problems with Concave Costs 
    Delon, Julie; Salomon, Julien; Sobolevski, Andrei (2012) Article accepté pour publication ou publié
  • Thumbnail
    Minimum-weight perfect matching for non-intrinsic distances on the line 
    Delon, Julie; Salomon, Julien; Sobolevski, Andrei (2012) Article accepté pour publication ou publié
  • Thumbnail
    Regularization of transportation maps for color and contrast transfer 
    Rabin, Julien; Delon, Julie; Gousseau, Yann (2010) Communication / Conférence
  • Thumbnail
    Explicit lower bounds for the cost of fast controls for some 1-D parabolic or dispersive equations, and a new lower bound concerning the uniform controllability of the 1-D transport–diffusion equation 
    Lissy, Pierre (2015) 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