Derivatives with respect to metrics and applications: subgradient marching algorithm
type: Item
instance of: scholarly article
title: Derivatives with respect to metrics and applications: subgradient marching algorithm
zbMATH Open document ID: 1202.65078
published in: Numerische Mathematik
publication date: 2010-10-08T00:00:00Z
review text: This paper is concerned with variational problem involving geodesic distances. The aim of the authors is to find a Riemannian metric that optimizes an energy taking into account pairwise geodesic distances according to the metric. The optimization of the metric is obtained using a gradient descent scheme. The optimization of a metric \(\xi\) that solves general variational problem of the following form \[ \min_{\xi \in C} \varepsilon(\xi)= \sum_{s,t} \varepsilon_{s,t} (d_\xi (x_s, x_t))+J(\xi),\tag{1} \] is considered. Here \(C\) is a convex set of constraints, for each pair of points \(s_s, x_t \in \Omega\) (a domain \(\Omega \subset\mathbb R^d)\), \(\varepsilon_{s,t}\) is an interaction functional, \(J\) is a convex regularization functional and \(d_\xi\) is the geodesic distance according to \(\xi\). An isotropic Riemannian metric \(\xi\) on \(\Omega\) defines a weight \(\xi(x)\) which penalizes a curve \(\gamma (t)\) passing through a point \(x= \gamma(t) \in \Omega\). The geodesic distance is the minimal length of rectifiable curves joining two points \(x_s, x_t \in \Omega\) \[ d_\xi (x_s, x_t) = \min_{\gamma (0) = x_s, \gamma(1) = x_t} L_\xi (\gamma).\tag{2} \] where the length of a curve is defined as \[ L_\xi (\gamma) = \int_0^1 |\gamma'(t)|\xi (\gamma(t))dt.\tag{3} \] Here the mapping \(\xi \rightarrow d_\xi(x_s, x_t)\) is concave, as the minimum (2) of linear functions of \(\xi\). The energy \(\varepsilon\) is thus convex as long as each interaction functional \(\varepsilon_{s,t}\) is convex and non-increasing. Two particular instantes of (1) where the energy is convex are considered. A global minimizer due to author's method is found. A non-convex problem (for which a local minimizer of \(\varepsilon\) is computed) is proposed. Main contribution is an algorithm to compute the gradient of the geodesic distance according to the metric. A new projected gradient descent algorithm to optimize a metric with respect to an energy involving geodesic distances is p…
Mathematics Subject Classification ID: 65K10
Mathematics Subject Classification ID: 65D25
Mathematics Subject Classification ID: 49K27
Mathematics Subject Classification ID: 49M25
zbMATH DE Number: 5797345
zbMATH Keywords: subgradient descent algorithm
zbMATH Keywords: Riemannian metric
zbMATH Keywords: energy
zbMATH Keywords: geodesic distance
zbMATH Keywords: concave function
zbMATH Keywords: minimizer
zbMATH Keywords: subgradient
zbMATH Keywords: discrete grid of \(N\) points
zbMATH Keywords: non-convex variational problem
zbMATH Keywords: convex constraints
zbMATH Keywords: inversion
zbMATH Keywords: travel time tomography
zbMATH Keywords: local minimum
zbMATH Keywords: recovered metric
zbMATH Keywords: regularization
author: Fethallah Benmansour
author: Guillaume Carlier
author: Gabriel Peyré
author: Filippo Santambrogio
reviewed by: Jan Lovíšek
describes a project that uses: SQPlab
MaRDI profile type: Publication
full work available at URL: s00211-010-0305-8
OpenAlex ID: W1969617809
cites work: Numerical approximation of continuous traffic congestion equilibria
cites work: Stable iterative reconstruction algorithm for nonlinear traveltime tomography
cites work: Numerical Geometry of Non-Rigid Shapes
cites work: Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching
cites work: Optimal Riemannian distances preventing mass transfer
cites work: Optimal Transportation with Traffic Congestion and Wardrop Equilibria
cites work: Accounting for the definition domain of the forward map in traveltime tomography—application to the inversion of prismatic reflections
cites work: A note on two problems in connexion with graphs
cites work: Computing geodesic paths on manifolds
cites work: An adjoint state method for three-dimensional transmission traveltime tomography using first-arrivals
cites work: Q3961832
cites work: A Viscosity Solutions Approach to Shape-From-Shading
cites work: Q4247633
cites work: Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
cites work: Fast methods for the Eikonal and related Hamilton– Jacobi equations on unstructured meshes
cites work: Efficient algorithms for globally optimal trajectories
DOI: 10.1007/S00211-010-0305-8
description: scientific article; zbMATH DE number 5797345