Derivatives with respect to metrics and applications: subgradient marching algorithm (Q707576)

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 presented. Recovery of geodesic inverse problems such as travel time tomography is obtained by computing a local minimizer of a non-convex problem. A numerical tool to solve discrete variational problems that take into account geodesic distance between points is proposed. The application to landscape modeling and to traffic congestion are showed. Finally three representative applications illustrate the practical use of subgradient marching.