Randers distances are an asymmetric generalization of Riemannian distances, and arise in optimal control problems subject to a drift term, among other applications. We show that Randers eikonal equation can be approximated by a logarithmic transformation of an anisotropic second order linear equation, generalizing Varadhan’s formula for Riemannian manifolds. Based on this observation, we establish the convergence of a numerical method for computing Randers distances, from point sources or from a domain’s boundary, on Cartesian grids of dimension 2 and 3, which is consistent at order 2/3, and uses tools from low-dimensional algorithmic geometry for best efficiency. We also propose a numerical method for optimal transport problems whose cost is a Randers distance, exploiting the linear structure of our discretization and generalizing previous works in the Riemannian case. Numerical experiments illustrate our results.
Keywords: Randers metric, Varadhan’s formula, Hamilton-Jacobi equation, viscosity solutions, finite-difference scheme, convergence analysis
@article{COCV_2022__28_1_A45_0,
author = {Bonnans, J. Fr\'ed\'eric and Bonnet, Guillaume and Mirebeau, Jean-Marie},
title = {A linear finite-difference scheme for approximating randers distances on cartesian grids},
journal = {ESAIM: Control, Optimisation and Calculus of Variations},
year = {2022},
publisher = {EDP-Sciences},
volume = {28},
doi = {10.1051/cocv/2022043},
mrnumber = {4448807},
zbl = {1504.65235},
language = {en},
url = {https://www.numdam.org/articles/10.1051/cocv/2022043/}
}
TY - JOUR AU - Bonnans, J. Frédéric AU - Bonnet, Guillaume AU - Mirebeau, Jean-Marie TI - A linear finite-difference scheme for approximating randers distances on cartesian grids JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2022 VL - 28 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/cocv/2022043/ DO - 10.1051/cocv/2022043 LA - en ID - COCV_2022__28_1_A45_0 ER -
%0 Journal Article %A Bonnans, J. Frédéric %A Bonnet, Guillaume %A Mirebeau, Jean-Marie %T A linear finite-difference scheme for approximating randers distances on cartesian grids %J ESAIM: Control, Optimisation and Calculus of Variations %D 2022 %V 28 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/cocv/2022043/ %R 10.1051/cocv/2022043 %G en %F COCV_2022__28_1_A45_0
Bonnans, J. Frédéric; Bonnet, Guillaume; Mirebeau, Jean-Marie. A linear finite-difference scheme for approximating randers distances on cartesian grids. ESAIM: Control, Optimisation and Calculus of Variations, Tome 28 (2022), article no. 45. doi: 10.1051/cocv/2022043
[1] , and , On the Ginzburg-Landau model of a superconducting ball in a uniform field. Annales de l'IHP Analyse non linéaire (2006) 237–267. | MR | Zbl | Numdam | DOI
[2] , , et al., Zermelo navigation on Riemannian manifolds. J. Differ. Geometry 66 (2004) 377–435. | MR | Zbl
[3] and , Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Modern Birkhäuser Classics, Birkhauser, Basel (1997). | Zbl | DOI
[4] and , Exit time problems in optimal control and vanishing viscosity method. SIAM J. Control Optim. 26 (1988) 1133–1148. | MR | Zbl | DOI
[5] and , A Strong Comparison Result for the Bellman equation arising in stochastic exit time control problems and its applications. Comm. Partial Differ. Equ. 23 (1998) 1995–2033. | MR | Zbl | DOI
[6] and , Convergence of approximation schemes for fully nonlinear second order equations. Asymptotic Anal. 4 (1991) 271–283. | MR | Zbl | DOI
[7] , and , A numerical solution to Monge’s problem with a Finsler distance as cost. ESAIM: MMNA 52 (2018) 2133–2148. | MR | Zbl | Numdam | DOI
[8] , The Sinkhorn algorithm, parabolic optimal transport and geometric Monge-Ampère equations. Numer. Math. 145 (2020) 771–836. | MR | Zbl | DOI
[9] and , Recherche opérationnelle. Aspects mathématiques et applications. Ellipse (2016).
[10] , and , Monotone and second order consistent scheme for the two dimensional Pucci equation (2020). | MR | Zbl
[11] , and , Second order monotone finite differences discretization of linear anisotropic differential operators. Math. Comput. 90 (2021) 2671–2703. | MR | Zbl
[12] and , Spatially dispersionless, unconditionally stable FC-AD solvers for variable-coefficient PDEs. J. Sci. Comput. 58 (2014) 331–366. | MR | Zbl | DOI
[13] , Control of an elliptic problem with pointwise state constraints. SIAM J. Control Optim. 24 (1986) 1309–1318. | MR | Zbl | DOI
[14] , and , Global minimum for a Finsler Elastica minimal path approach. Int. J. Comput. Vis. 122 (2017) 458–483. | MR | Zbl | DOI
[15] , and , The Hopf-Cole transformation, topological solitons and multiple fusion solutions for the -dimensional Burgers system. Phys. Lett. A 380 (2016) 9–14. | MR | Zbl | DOI
[16] and , Finsler geometry, An approach via Randers spaces (2012). | MR | Zbl
[17] , , , and , Faster wasserstein distance estimation with the Sinkhorn divergence. Adv. Neural Inf. Process. Syst. 33 (2020).
[18] , and , Finsler geodesics evolution model for region based active contours, in Proceedings of the British Machine Vision Conference (BMVC), edited by and . BMVA Press (2016) 22.1–22.12.
[19] , , , , , and , Solving directed laplacian systems in nearly- linear time through sparse LU factorizations, in 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), IEEE (2018) 898–909. | MR | Zbl | DOI
[20] and , Low-dimensional lattices. VI. Voronoi reduction of three-dimensional lattices. Proc. R. Soc. A 436 (1992) 55–68. | MR | Zbl
[21] , and , User’s guide to viscosity solutions of second order partial differential equations. Bull. Amer. Math. Soc. 27 (1992) 1–67. | MR | Zbl | DOI
[22] , , and , A Survey of Algorithms for Geodesic Paths and Distances. Preprint (2020). | arXiv
[23] , and , Geodesics in heat: a new approach to computing distance based on heat flow. ACM Trans. Graph. 32 (2013) 152:1–152:11. | DOI
[24] , and , The heat method for distance computation. Commun. ACM 60 (2017) 90–99. | DOI
[25] , Sinkhorn distances: lightspeed computation of optimal transport, in Proc. 26th International Conference on Neural Information Processing Systems — Volume 2 (2013) 2292–2300.
[26] , and , Minimal entropy conditions for Burgers equation. Quart. Appl. Math. 62 (2004) 687–700. | MR | Zbl | DOI
[27] , , and , Optimal paths for variants of the 2D and 3D Reeds-Shepp car with applications in image analysis. J. Math. Imag. Vision (2018) 1–33. | MR | Zbl
[28] and , Theory and practice of finite elements, vol. 159. Springer Science and Business Media (2013). | MR | Zbl
[29] and , Sparse non-negative stencils for anisotropic diffusion. J. Math. Imag. Vision 49 (2014) 123–147. | MR | Zbl | DOI
[30] and , Uniqueness and transport density in Monge’s mass transportation problem. Calc. Variat. Partial Differ. Equ. 15 (2002) 81–113. | MR | Zbl | DOI
[31] , The partial differential equation . Commun. Pure Appl. Math. 3 (1950) 201–230. | MR | Zbl | DOI
[32] , , and , The convection-diffusion-reaction equation in non-Hilbert Sobolev spaces: a direct proof of the inf-sup condition and stability of Galerkin’s method. Comput. Methods Appl. Math. 19 (2019) 503–522. | MR | Zbl | DOI
[33] and , A high order spectral volume solution to the Burgers’ equation using the Hopf-Cole transformation. Int. J. Numer. Methods Fluids 69 (2012) 781–801. | MR | Zbl | DOI
[34] , Elementary proof for Sion’s minimax theorem. Kodai Math. J. 11 (1988) 5–7. | MR | Zbl | DOI
[35] and , Anisotropic voronoi diagrams and guaranteed-quality anisotropic mesh generation, in Proceedings of the nineteenth annual symposium on Computational geometry (2003) 191–200. | Zbl | DOI
[36] , A survey of the Schrodinger problem and some of its connections with optimal transport. Discr. Continu. Dyn. Syst. 34 (2014) 1533. | MR | Zbl | DOI
[37] and , Inverses of 2 x 2 block matrices. Comput. Math. Appl. 43 (2002) 119–129. | MR | Zbl | DOI
[38] , and , Regularity of potential functions of the optimal transportation problem. Arch. Ratl. Mech. Anal. 177 (2005) 151–183. | MR | Zbl | DOI
[39] , Efficient fast marching with Finsler metrics. Numer. Math. 126 (2014) 515–557. | MR | Zbl | DOI
[40] , Minimal stencils for discretizations of anisotropic PDEs preserving causality or the maximum principle. SIAM J. Numer. Anal. 54 (2016) 1582–1611. | MR | Zbl | DOI
[41] , Fast-marching methods for curvature penalized shortest paths. J. Math. Imag. Vision 60 (2018) 784–815. | MR | Zbl | DOI
[42] , Riemannian fast-marching on cartesian grids, using voronoi’s first reduction of quadratic forms. SIAM J. Numer. Anal. 57 (2019) 2608–2655. | MR | Zbl | DOI
[43] , Convergent difference schemes for degenerate elliptic and parabolic equations: Hamilton-Jacobi equations and free boundary problems. SIAM J. Numer. Anal. 44 (2006) 879–895. | MR | Zbl | DOI
[44] and , Heat flow on Finsler manifolds. Commun. Pure Appl. Math. 62 (2009) 1386–1433. | MR | Zbl | DOI
[45] , Cole-Hopf transformation as numerical tool for the Burgers equation. Appl. Comput. Math 8 (2009) 107–113. | MR | Zbl
[46] , On an asymmetrical metric in the four-space of general relativity. Phys. Rev. 59 (1941) 195–199. | MR | Zbl | DOI
[47] , Uber die Binaren und Ternären Quadratischen Formen. J. Reine Angew. Math. 77 (1874) 143–229. | MR | JFM
[48] and , Ordered upwind methods for static Hamilton-Jacobi equations. Proc. Natl. Acad. Sci. USA 98 (2001) 11069–11074. | MR | Zbl | DOI
[49] , A relationship between arbitrary positive matrices and doubly stochastic matrices. Ann. Math. Stat. 35 (1964) 876–879. | MR | Zbl | DOI
[50] , , , , , , and , Convolutional Wasserstein distances: efficient optimal transportation on geometric domains. ACM Trans. Graph. 34 (2015) 66:1–66:11. | Zbl | DOI
[51] , , and , Earth mover’s distances on discrete surfaces. ACM Trans. Graphics 33 (2014) 1–12. | Zbl | DOI
[52] , On the behavior of the fundamental solution of the heat equation with variable coefficients. Comm. Pure Appl. Math. 20 (1967) 431–455. | MR | Zbl | DOI
[53] , Optimal transport: old and new, vol. 338. Springer (2009). | MR | Zbl | DOI
[54] , , and , Geodesic via asymmetric heat diffusion based on Finsler metric, in Asian Conference on Computer Vision. Springer (2018) 371–386.
[55] and , Geodesic distance and curves through isotropic and anisotropic heat equations on images and surfaces. J. Math. Imag. Vision 55 (2016) 210–228. | MR | Zbl | DOI
Cité par Sources :
The first author was partially supported by the FiME Lab Research Initiative (Institut Europlace de Finance).
