Dissipative numerical schemes on Riemannian manifolds with applications to gradient flows. (English) Zbl 1403.49029
Summary: This paper concerns an extension of discrete gradient methods to finite-dimensional Riemannian manifolds termed discrete Riemannian gradients, and their application to dissipative ordinary differential equations. This includes Riemannian gradient flow systems which occur naturally in optimization problems. The Itoh-Abe discrete gradient is formulated and applied to gradient systems, yielding a derivative-free optimization algorithm. The algorithm is tested on two eigenvalue problems and two problems from manifold valued imaging: interferometric synthetic aperture radar denoising and diffusion tensor imaging denoising.
MSC:
| 49M37 | Numerical methods based on nonlinear programming |
| 53B99 | Local differential geometry |
| 65K10 | Numerical optimization and variational techniques |
| 92C55 | Biomedical imaging and signal processing |
| 90C26 | Nonconvex programming, global optimization |
| 90C30 | Nonlinear programming |
| 90C56 | Derivative-free methods and methods using generalized derivatives |
Keywords:
geometric integration; discrete gradients; Riemannian manifolds; numerical optimization; InSAR denoising; DTI denoisingReferences:
| [1] | P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization Algorithms on Matrix Manifolds, Princeton University Press, Princeton, NJ, 2009. · Zbl 1147.65043 |
| [2] | R. L. Adler, J.-P. Dedieu, J. Y. Margulies, M. Martens, and M. Shub, Newton’s method on Riemannian manifolds and a geometric model for the human spine, IMA J. Numer. Anal., 22 (2002), pp. 359–390. · Zbl 1056.92002 |
| [3] | R. P. Brent, An algorithm with guaranteed convergence for finding a zero of a function, Comput. J., 14 (1971), pp. 422–425. · Zbl 0231.65046 |
| [4] | R. W. Brockett, Dynamical systems that sort lists, diagonalize matrices and solve linear programming problems, in Proceedings of the 27th IEEE Conference on Decision and Control, IEEE, 1988, pp. 799–803. |
| [5] | E. Celledoni, S. Eidnes, B. Owren, and T. Ringholm, Energy Preserving Methods on Riemannian Manifolds, preprint, , 2018. · Zbl 1395.65062 |
| [6] | E. Celledoni and B. Owren, A class of intrinsic schemes for orthogonal integration, SIAM J. Numer. Anal., 40 (2002), pp. 2069–2084. · Zbl 1034.65054 |
| [7] | E. Celledoni and B. Owren, Preserving first integrals with symmetric Lie group methods, Discrete Contin. Dyn. Syst., 34 (2014), pp. 977–990. · Zbl 1278.65097 |
| [8] | P. Cook, Y. Bai, S. Nedjati-Gilani, K. Seunarine, M. Hall, G. Parker, and D. Alexander, Camino: Open-source diffusion-MRI reconstruction and processing, in Proceedings of ISMRM, Seattle, WA, 2006. |
| [9] | R. M. Goldstein, H. A. Zebker, and C. L. Werner, Satellite radar interferometry: Two-dimensional phase unwrapping, Radio Sci., 23 (1988), pp. 713–720. |
| [10] | O. Gonzalez, Time integration and discrete Hamiltonian systems, J. Nonlinear Sci., 6 (1996), pp. 449–467. · Zbl 0866.58030 |
| [11] | V. Grimm, R. I. McLachlan, D. I. McLaren, G. Quispel, and C. Schönlieb, Discrete gradient methods for solving variational image regularisation models, J. Phys. A, 50 (2017), 295201. · Zbl 1371.94146 |
| [12] | H. Gudbjartsson and S. Patz, The Rician distribution of noisy MRI data, Magn. Reson. Med., 34 (1995), pp. 910–914. |
| [13] | E. Hairer and C. Lubich, Energy-diminishing integration of gradient systems, IMA J. Numer. Anal., 34 (2013), pp. 452–461. · Zbl 1321.65115 |
| [14] | E. Hairer, C. Lubich, and G. Wanner, Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations, Springer Ser. Comput. Math. 31, Springer, New York, 2006. · Zbl 1094.65125 |
| [15] | E. Hairer and G. Wanner, Solving Ordinary Differential Equations. II, 2nd ed., Springer Ser. Comput. Math. 14, Springer, New York, 1996. · Zbl 0859.65067 |
| [16] | A. Harten, P. D. Lax, and B. van Leer, On upstream differencing and Godunov-type schemes for hyperbolic conservation laws, SIAM Rev., 25 (1983), pp. 35–61. · Zbl 0565.65051 |
| [17] | A. Humphries and A. Stuart, Runge–Kutta methods for dissipative and gradient dynamical systems, SIAM J. Numer. Anal., 31 (1994), pp. 1452–1485. · Zbl 0807.34057 |
| [18] | T. Itoh and K. Abe, Hamiltonian-conserving discrete canonical equations based on variational difference quotients, J. Comput. Phys., 76 (1988), pp. 85–102. · Zbl 0656.70015 |
| [19] | S. Lang, Fundamentals of Differential Geometry, Grad. Texts in Math. 191, Springer, New York, 2012. |
| [20] | J. M. Lee, Riemannian Manifolds: An Introduction to Curvature, Grad. Texts in Math. 176, Springer, New York, 2006. |
| [21] | R. I. McLachlan, G. R. W. Quispel, and N. Robidoux, Geometric integration using discrete gradients, Philos. Trans. A, 357 (1999), pp. 1021–1045. · Zbl 0933.65143 |
| [22] | T. Ringholm, J. Lazić, and C.-B. Schönlieb, Variational image regularization with Euler’s elastica using a discrete gradient scheme, SIAM J. Imaging Sci., to appear. · Zbl 1426.49031 |
| [23] | F. Rocca, C. Prati, and A. Ferretti, An overview of ERS-SAR interferometry, in Proceedings of the ERS Symposium “Space in the Service of our Environment,” 1997. |
| [24] | P. A. Rosen, S. Hensley, I. R. Joughin, F. K. Li, S. N. Madsen, E. Rodriguez, and R. M. Goldstein, Synthetic aperture radar interferometry, Proc. IEEE, 88 (2000), pp. 333–382. |
| [25] | S. Sato, T. Matsuo, H. Suzuki, and D. Furihata, A Lyapunov-type theorem for dissipative numerical integrators with adaptive time-stepping, SIAM J Numer. Anal., 53 (2015), pp. 2505–2518. · Zbl 1330.65194 |
| [26] | M. Shub, Some remarks on dynamical systems and numerical analysis, in Proceedings of the 7th ELAM, 1986, pp. 69–92. |
| [27] | E. Strekalovskiy and D. Cremers, Total variation for cyclic structures: Convex relaxation and efficient minimization, in Proceedings of CVPR, IEEE, 2011, pp. 1905–1911. |
| [28] | C. Udriste, Convex Functions and Optimization Methods on Riemannian Manifolds, Math. Appl. 297, Springer, New York, 1994. · Zbl 0932.53003 |
| [29] | F. W. Warner, Foundations of Differentiable Manifolds and Lie Groups, Grad. Texts in Math. 94, Springer, New York, 2013. |
| [30] | A. Weinmann, L. Demaret, and M. Storath, Total variation regularization for manifold-valued data, SIAM J. Imaging Sci., 7 (2014), pp. 2226–2257. · Zbl 1309.65071 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
