A gradient-descent method for curve fitting on Riemannian manifolds. (English) Zbl 1245.65017

Samir, Chafik; Absil, P.-A.; Srivastava, Anuj; Klassen, Eric

Found. Comput. Math. 12, No. 1, 49-73 (2012).

For given data points \(p_0,\ldots,p_N\) on a closed Riemannian manifold of \({\mathbb R}^n\) and time instants \(0=t_0 < t_1 < \ldots < t_N =1\), the authors consider the problem of finding a curve \(\gamma\) on \(M\) that best approximates the data points at the given instants while being as “regular” as possible. They study an optimization problem with two objective functions, namely a fitting function \[ E_d(\gamma) = \frac{1}{2}\, \sum_{i=0}^N d^2(\gamma(t_i), p_i)\,, \] where \(d\) denotes the distance function on \(M\), and a regularity function \(E_s(\gamma)\). In the first case, the regularity function is the mean squared velocity of \(\gamma\), i.e. \[ E_s(\gamma) = \frac{1}{2}\, \int_0^1 \|\dot{ \gamma}(t)\|^2 \, dt\,. \] In the second case, \(E_s(\gamma)\) is the mean squared acceleration of \(\gamma\). Then the authors search for an optimizer of the objective function \(E(\gamma) = E_d(\gamma) + \lambda \, E_s(\gamma)\), where \(\lambda >0\) is a smoothing parameter, using a steepest descent method in a set of curves \(\gamma\) on \(M\). The steepest descent direction, defined in the sense of first order and second order Palais metric, respectively, is shown to admit analytical expressions involving parallel transport and covariant integral along curves. The method is illustrated on fitting problems in \(M={\mathbb R}^2\) and the unit sphere.

Reviewer: Manfred Tasche (Rostock)

MSC:

65D10	Numerical smoothing, curve fitting
65K10	Numerical optimization and variational techniques
49M30	Other numerical methods in calculus of variations (MSC2010)
49J15	Existence theories for optimal control problems involving ordinary differential equations

Keywords:

curve fitting; Riemannian manifold; optimization problem; fitting function; regularity function; steepest descent method; Palais metric; geodesic distance; unit sphere

References:

[1]	P.A. Absil, K.A. Gallivan, Accelerated line-search and trust-region methods, SIAM J. Numer. Anal. 47(2), 997–1018 (2009). · Zbl 1191.65067
[2]	P.A. Absil, R. Mahony, B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim. 6(2), 531–547 (2005). · Zbl 1092.90036
[3]	P.A. Absil, R. Mahony, R. Sepulchre, Optimization Algorithms on Matrix Manifolds (Princeton University Press, Princeton, 2008). · Zbl 1147.65043
[4]	P.A. Absil, J. Trumpf, R. Mahony, B. Andrews, All roads lead to Newton: feasible second-order methods for equality-constrained optimization, Technical report UCL-INMA-2009.024 (2009).
[5]	C. Altafini, The de Casteljau algorithm on SE(3), in Nonlinear Control in the Year 2000 (2000), pp. 23–34. · Zbl 1239.70013
[6]	D.P. Bertsekas, Nonlinear Programming (Athena Scientific, Belmont, 1995).
[7]	W.M. Boothby, An Introduction to Differentiable Manifolds and Riemannian Geometry, revised 2nd edn. (Academic Press, San Diego, 2003). · Zbl 0333.53001
[8]	M. Camarinha, F. Silva Leite, P. Crouch, Splines of class C k on non-Euclidean spaces, IMA J. Math. Control Inf. 12(4), 399–410 (1995). · Zbl 0860.58013
[9]	M.P. do Carmo, Riemannian Geometry. Mathematics: Theory & Applications (Birkhäuser Boston, Boston, 1992). Translated from the second Portuguese edition by Francis Flaherty.
[10]	I. Chavel, Riemannian Geometry, 2nd edn. Cambridge Studies in Advanced Mathematics, vol. 98 (Cambridge University Press, Cambridge, 2006). A modern introduction.
[11]	P. Crouch, G. Kun, F. Silva Leite, The de Casteljau algorithm on the Lie group and spheres, J. Dyn. Control Syst. 5, 397–429 (1999). · Zbl 0961.53027
[12]	P. Crouch, F. Silva Leite, Geometry and the dynamic interpolation problem, in Proc. Am. Control Conf. (Boston, 26–29 July, 1991), pp. 1131–1136.
[13]	P. Crouch, F. Silva Leite, The dynamic interpolation problem: on Riemannian manifolds, Lie groups, and symmetric spaces, J. Dyn. Control Syst. 1(2), 177–202 (1995). · Zbl 0946.58018
[14]	N. Dyn, Linear and nonlinear subdivision schemes in geometric modeling, in Foundations of Computational Mathematics, Hong Kong, 2008. London Math. Soc. Lecture Note Ser., vol. 363 (Cambridge University Press Cambridge, 2009), pp. 68–92. · Zbl 1179.65025
[15]	S. Gallot, D. Hulin, J. Lafontaine, Riemannian Geometry, 3rd edn. Universitext (Springer, Berlin, 2004).
[16]	K. Hüper, F. Silva Leite, On the geometry of rolling and interpolation curves on S n , SO n , and Grassmann manifolds, J. Dyn. Control Syst. 13(4), 467–502 (2007). · Zbl 1140.58005
[17]	J. Jakubiak, F. Silva Leite, R.C. Rodrigues, A two-step algorithm of smooth spline generation on Riemannian manifolds, J. Comput. Appl. Math. 194(2), 177–191 (2006). · Zbl 1101.65012
[18]	P.E. Jupp, J.T. Kent, Fitting smooth paths to spherical data, J. R. Stat. Soc. Ser. C 36(1), 34–46 (1987). · Zbl 0613.62086
[19]	H. Karcher, Riemannian center of mass and mollifier smoothing, Commun. Pure Appl. Math. 30(5), 509–541 (1977). · Zbl 0354.57005
[20]	E. Klassen, A. Srivastava, Geodesic between 3D closed curves using path straightening, in European Conference on Computer Vision, ed. by A. Leonardis, H. Bischof, A. Pinz (eds.), (2006), pp. 95–106.
[21]	A. Kume, I.L. Dryden, H. Le, Shape-space smoothing splines for planar landmark data, Biometrika 94(3), 513–528 (2007). · Zbl 1134.62044
[22]	M. Lazard, J. Tits, Domaines d’injectivité de l’application exponentielle, Topology 4, 315–322 (1965/1966). · Zbl 0156.03203
[23]	J.M. Lee, Riemannian Manifolds: An Introduction to Curvature. Graduate Texts in Mathematics, vol. 176 (Springer, New York, 2007).
[24]	A. Linnér, Symmetrized curve-straightening, Differ. Geom. Appl. 18(2), 119–146 (2003). · Zbl 1035.53093
[25]	L. Machado, F.S. Leite, K. Krakowski, Higher-order smoothing splines versus least squares problems on Riemannian manifolds, J. Dyn. Control Syst. 16(1), 121–148 (2010). · Zbl 1203.65028
[26]	L. Machado, F. Silva Leite, Fitting smooth paths on Riemannian manifolds, Int. J. Appl. Math. Stat. 4(J06), 25–53 (2006). · Zbl 1138.65012
[27]	L. Machado, F. Silva Leite, K. Hüper, Riemannian means as solutions of variational problems, LMS J. Comput. Math. 9, 86–103 (2006) (electronic). · Zbl 1111.58010
[28]	J.W. Milnor, Morse Theory (Princeton University Press, Princeton, 1963).
[29]	L. Noakes, G. Heinzinger, B. Paden, Cubic splines on curved spaces, IMA J. Math. Control Inf. 6(4), 465–473 (1989). · Zbl 0698.58018
[30]	B. O’Neill, Semi-Riemannian Geometry. Pure and Applied Mathematics, vol. 103 (Academic Press [Harcourt Brace Jovanovich Publishers], New York, 1983).
[31]	R.S. Palais, Morse theory on Hilbert manifolds, Topology 2, 299–340 (1963). · Zbl 0122.10702
[32]	T. Popiel, L. Noakes, Bézier curves and C 2 interpolation in Riemannian manifolds, J. Approx. Theory 148(2), 111–127 (2007). · Zbl 1129.53011
[33]	C. Samir, P.A. Absil, A. Srivastava, E. Klassen, A gradient-descent method for curve fitting on Riemannian manifolds, Tech. Rep. UCL-INMA-2009.023-v3, Université catholique de Louvain (2010). · Zbl 1245.65017
[34]	T. Shingel, Interpolation in special orthogonal groups, IMA J. Numer. Anal. 29(3), 731–745 (2009). · Zbl 1175.65023
[35]	G. Smyrlis, V. Zisis, Local convergence of the steepest descent method in Hilbert spaces, J. Math. Anal. Appl. 300(2), 436–453 (2004). · Zbl 1062.65060
[36]	A.J. Tromba, A general approach to Morse theory, J. Differ. Geom. 12(1), 47–85 (1977). · Zbl 0344.58012
[37]	J. Wallner, E. Nava Yazdani, P. Grohs, Smoothness properties of Lie group subdivision schemes. Multiscale Model. Simul. 6(2), 493–505 (2007) (electronic). · Zbl 1144.41003