Derivatives with respect to metrics and applications: Subgradient Marching Algorithm
Benmansour, Fethallah; Carlier, Guillaume; Peyré, Gabriel; Santambrogio, Filippo (2010), Derivatives with respect to metrics and applications: Subgradient Marching Algorithm, Numerische Mathematik, 116, 3, p. 357-381. http://dx.doi.org/10.1007/s00211-010-0305-8
Type
Article accepté pour publication ou publiéExternal document link
http://hal.archives-ouvertes.fr/hal-00360971/en/Date
2010Journal name
Numerische MathematikVolume
116Number
3Publisher
Springer
Pages
357-381
Publication identifier
Metadata
Show full item recordAbstract (EN)
This paper introduces a subgradient descent algorithm to compute a Riemannian metric that minimizes an energy involving geodesic distances. The heart of the method is the Subgradient Marching Algorithm to compute the derivative of the geodesic distance with respect to the metric. The geodesic distance being a concave function of the metric, this algorithm computes an element of the subgradient in O(N 2 log(N)) operations on a discrete grid of N points. It performs a front propagation that computes a subgradient of a discrete geodesic distance. We show applications to landscape modeling and to traffic congestion. Both applications require the maximization of geodesic distances under convex constraints, and are solved by subgradient descent computed with our Subgradient Marching. We also show application to the inversion of travel time tomography, where the recovered metric is the local minimum of a non-convex variational problem involving geodesic distances.Subjects / Keywords
Travel Time Tomography; Traffic Congestion; Fast Marching Method; Subgradient Descent; Eikonal Equation; GeodesicsRelated items
Showing items related by title and author.
-
Peyré, Gabriel; Carlier, Guillaume; Benmansour, Fethallah; Santambrogio, Filippo (2009) Article accepté pour publication ou publié
-
Santambrogio, Filippo; Jimenez, Chloé; Carlier, Guillaume (2008) Article accepté pour publication ou publié
-
Santambrogio, Filippo; Carlier, Guillaume; Galichon, Alfred (2010) Article accepté pour publication ou publié
-
Santambrogio, Filippo; Carlier, Guillaume (2012) Article accepté pour publication ou publié
-
Brasco, Lorenzo; Carlier, Guillaume; Santambrogio, Filippo (2010) Article accepté pour publication ou publié