Derivatives with respect to metrics and applications: subgradient marching algorithm
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.
- A note on two problems in connexion with graphs
- A Viscosity Solutions Approach to Shape-From-Shading
- Accounting for the definition domain of the forward map in traveltime tomography—application to the inversion of prismatic reflections
- An adjoint state method for three-dimensional transmission traveltime tomography using first-arrivals
- Computing geodesic paths on manifolds
- Efficient algorithms for globally optimal trajectories
- Fast methods for the Eikonal and related Hamilton– Jacobi equations on unstructured meshes
- Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching
- scientific article; zbMATH DE number 3783507 (Why is no real title available?)
- scientific article; zbMATH DE number 1302349 (Why is no real title available?)
- Numerical approximation of continuous traffic congestion equilibria
- Numerical Geometry of Non-Rigid Shapes
- Optimal Riemannian distances preventing mass transfer
- Optimal Transportation with Traffic Congestion and Wardrop Equilibria
- Ordered Upwind Methods for Static Hamilton--Jacobi Equations: Theory and Algorithms
- Stable iterative reconstruction algorithm for nonlinear traveltime tomography
- A continuous theory of traffic congestion and Wardrop equilibria
- Fast-marching methods for curvature penalized shortest paths
- Ground metric learning on graphs
- An inverse eikonal method for identifying ventricular activation sequences from epicardial activation maps
- Algorithmic construction of the subdifferential from directional derivatives
- A Modica-Mortola approximation for the Steiner problem
- Connected Coulomb columns: analysis and numerics
- A Projected Subgradient Method for the Computation of Adapted Metrics for Dynamical Systems
- Analysis of Regularized Kantorovich--Rubinstein Metric and Its Application to Inverse Gravity Problems
- Phase field models for thin elastic structures with topological constraint
- A phase-field approximation of the perimeter under a connectedness constraint
- Numerical approximation of the Steiner problem in dimension 2 and 3
- Approximation of length minimization problems among compact connected sets
- On scalar metrics that maximize geodesic distances in the plane
- Transport densities and congested optimal transport problem in the Heisenberg group
This page was built for publication: Derivatives with respect to metrics and applications: subgradient marching algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q707576)
