Newton's method for path following problems on manifolds [Elektronische Ressource] / vorgelegt von Markus Baumann

Sujets

• Mathematics

Informations

• Publié par: julius-maximilians-universitat_wurzburg
• Publié le: 01 janvier 2008
• Nombre de lectures: 20
• Langue: Deutsch

Extrait

Newton’s Method for
Path-Following Problems
on Manifolds
Dissertation zur Erlangung des naturwissenschaftlichen Doktorgrades der Bayerischen
Julius-Maximilians-Universit˜at Wurzburg˜
vorgelegt von
Markus Baumann
aus
Erlenbach am Main
Wurzburg˜ 2008Eingereicht am:
bei der Fakult˜at fur˜ Mathematik und Informatik
der Bayerischen Julius-Maximilians-Universit˜at Wurzburg˜
1. Gutachter: Prof. Dr. Uwe Helmke
2. Gutachter: Prof. Dr. Christian Kanzow
Tag der mundlic˜ hen Prufung:˜Vorwort
Die vorliegende Arbeit wurde am Lehrstuhl 2 fur˜ Mathematik an der Universit˜at
Wurzburg˜ erstellt. Ein Forschungsschwerpunkt dieses Lehrstuhls ist die Entwicklung
vonOptimierungsalgorithmenaufMannigfaltigkeiten. PassenddazuwarderUrsprung
dieser Arbeit, n˜amlich das Studium von Verfahren zur Bestimmung von orthogonalen
Matrizen, welche vorgegebene symmetrische Matrizen diagonalisieren. Die besondere
Schwierigkeit lag hierbei in der Tatsache, dass man sich nicht auf konstante Matrizen
beschr˜ankte,sondernsymmetrischeMatrizenbetrachtete,diestetigdifierenzierbarvon
einem Parameter (der Zeit) abhingen. Fur˜ diese Problemstellung konnte man ein Ver-
fahren zur zeitvarianten Berechnung ("Tracking") der gesuchten orthogonalen Trans-
formation durch einen rein euklidischen Ansatz herleiten. Es stellte sich jedoch schnell
heraus, dass der zugrunde liegende Trackingalgorithmus noch Verbesserungspotential
besitzt. Zun˜achst sollte das Verfahren fur˜ Mannigfaltigkeiten verallgemeinert werden
um strukturierte Trackingprobleme intrinsisch, d.h. direkt auf der Mannigfaltigkeit,
behandeln zu k˜onnen. Weitere Motive fur˜ Erweiterungen und Modiflkationen der
Trackingtheoreme waren die betrachteten Anwendungen. Dies waren zumeist Opti-
mierungsprobleme auf Mannigfaltigkeiten, die bereits am Lehrstuhl behandelt wurden
und welche man darub˜ er hinaus in einem zeitvarianten Kontext untersuchen wollte.
Die Ausarbeitung dieser Ideen fuhrte˜ zu einigen Publikationen, die ich zusammen mit
Herrn Prof. Dr. Uwe Helmke verfasste. An dieser Stelle m˜ochte ich mich bei ihm
ausdruc˜ klichfur˜ seineUnterstutzung˜ bedanken. OhneseineErfahrung,seinGespur˜ fur˜
viel versprechende Untersuchungen, seine (mit-) anpackende und im positiven Sinne
fordernde Art, w˜are diese Arbeit nicht m˜oglich gewesen. Weiteren Dank verdienen
meine Kollegen und Freunde vom Lehrstuhl, bei denen man sich stets Unterstutzung˜
einholen konnte: Gunther Dirr, Jens Jordan, Martin Kleinsteuber und Christian Lage-
man sind hier in jedem Fall zu nennen. Besonderer Dank gilt auch Herrn Prof. Dr.
Malte Messmann vom Juliusspital Wurzburg,˜ der mich in den ersten drei Promo-
tionsjahren flnanziell komfortabel ausgestattet hat. Leider konnten wir nicht wie ur-
sprunglic˜ h geplant, ein interdisziplin˜ares medizinisch-mathematisches Thema zu einer
Dissertation ausarbeiten. Trotzdem bekam ich genugend˜ Freiheit, um dann ein rein
mathematisches Thema zu behandeln. Und schlie…lich bedanke ich mich bei meinen
Eltern, fur˜ ihre weit ub˜ er das normale Ma… hinausgehende Unterstutzung˜ w˜ahrend
meiner Studienzeit.
iiiPublikationsliste
Die folgenden Arbeiten habe ich im Rahmen meiner T˜atigkeit als wissenschaftlicher
Mitarbeiter am Lehrstuhl fur˜ Mathematik II ver˜ofientlicht.
† M. Baumann, U. Helmke. Diagonalization of time-varying symmetric matrices,
Proceedings of the International Conference on Computational Science ICCS,
2002.
† M.Baumann,U.Helmke. Singularvaluedecompositionoftime-varyingmatrices,
Future Generation Computer Systems 19(3):353-361, 2003.
† M. Baumann, U. Helmke. A path-following method for tracking of time-varying
essential matrices, Proceedings of the MTNS, CD-Rom, Leuven, 2004.
† M.Baumann, C.Lageman, U.Helmke. Newton-typealgorithmsfortime-varying
pose estimation, Proceedings of the ISSNIP, CD-Rom, Melbourne, 2004.
† M.Baumann, J. Manton, U.Helmke. Reliable TrackingAlgorithms forPrincipal
and Minor Eigenvector Computations, Proceedings of the 44th IEEE Conference
on Decision and Control, Sevilla, 2005.
† M. Baumann, U. Helmke. Riemannian subspace tracking algorithms on Grass-
mann manifolds, Proceedings of the 46th IEEE Conference on Decision and Con-
trol, New Orleans, 2007.
† M. Baumann, U. Helmke. A time-varying Newton algorithm for adaptive sub-
space tracking, Mathematics and Computers in Simulation , zur Ver˜ofientlichung
angenommen, 2008.
iiiivContents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Previous work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2 Time-varying Newton ow 10
2.1 Riemannian time-varying Newton ow . . . . . . . . . . . . . . . . . . 10
2.1.1 Preliminaries on Riemannian manifolds . . . . . . . . . . . . . . 10
2.1.2 The tracking algorithms . . . . . . . . . . . . . . . . . . . . . . 24
2.1.2.1 Time-varying Riemannian Newton algorithm . . . . . 26
@2.1.2.2 Approximations for g(t) . . . . . . . . . . . . . . . . 31
@t
2.1.3 Newton ows on Riemannian submanifolds . . . . . . . . . . . . 32
2.1.3.1 Embedding the tracking task in Euclidean space . . . . 35
2.2 Newton ows on Lie groups . . . . . . . . . . . . . . . . . . . . . . . . 44
2.3 Euclidean time-varying Newton ow. . . . . . . . . . . . . . . . . . . . 55
2.3.1 The tracking algorithms in Euclidean space . . . . . . . . . . . 55
2.3.2 Inexact time-varying Newton ow . . . . . . . . . . . . . . . . . 57
2.3.3 Underdetermined Newton ow . . . . . . . . . . . . . . . . . . . 63
3 Application I: Intrinsic Subspace Tracking 69
3.1 Time-varying Newton ow for principal subspace tracking . . . . . . . 69
3.2 Subspace tracking algorithms . . . . . . . . . . . . . . . . . . . . . . . 73
3.3 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4 Application II: Tracking Matrix Decompositions 90
4.1 Eigenvalue and singular value decomposition . . . . . . . . . . . . . . . 91
4.1.1 Diagonalization of symmetric matrices with distincteigenvalues 91
4.1.2 of with multipleeigenvalues100
4.1.3 Singular value decomposition . . . . . . . . . . . . . . . . . . . 110
4.1.4 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.2 Polar decomposition of time-varying matrices . . . . . . . . . . . . . . 121
4.2.1 SVD-based polar decomposition . . . . . . . . . . . . . . . . . . 121
4.2.2 Polar decomposition by square root tracking . . . . . . . . . . . 124
v4.2.3 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . 125
4.3 Minor and principal eigenvector tracking . . . . . . . . . . . . . . . . . 127
4.3.1 Minor eigenvector tracking . . . . . . . . . . . . . . . . . . . . . 130
4.3.1.1 Vectorizing the matrix difierential equation . . . . . . 130
4.3.1.2 Approximately solving the implicit difierential equation 132
4.3.2 Principal eigenvector tracking . . . . . . . . . . . . . . . . . . . 136
4.3.3 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . 136
5 Application III: Pose Estimation 141
5.1 Working in the ambient space . . . . . . . . . . . . . . . . . . . . . . . 144
5.2 Intrinsic pose estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 148
5.3 Further approaches for time-varying pose estimation . . . . . . . . . . . 154
5.3.1 Partially intrinsic method . . . . . . . . . . . . . . . . . . . . . 154
5.3.2 Parameterizationd. . . . . . . . . . . . . . . . . . . . . . 159
5.4 Numerical results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
6 Appendix 167
viChapter 1
Introduction
1.1 Motivation
Many optimization problems for a smooth cost function f : M ! R on a manifold
M can be solved by determining the zeros x of a vector fleld F : M ! TM on M;⁄
such as e.g. the gradient F of the cost function f. If F does not depend on addi-
tional parameters, numerous zero-flnding techniques are available for this purpose. It
is a natural generalization however, to consider time-dependent optimization problems
thatrequirethecomputationoftime-varyingzerosx (t)oftime-dependentvectorflelds⁄
F(x;t). Such parametric optimization problems arise in many flelds of applied mathe-
matics, in particular path-following in robotics [49], recursive eigenvalue and
singular value estimation in signal processing, cf. [58], [59], [72], as well as numerical
linear algebra and inverse eigenvalue problems in control theory cf. [53], [57] and [60].
In the literature, there are already some tracking algorithms for these tasks, but these
do not always adequately respect the manifold structure. Hence, available tracking
results can often be improved by implementing methods working directly on the mani-
fold. For this reason, we develop in this thesis zero-flnding techniques for time-varying
vector flelds on Riemannian manifolds M. Thus we consider a smooth parameterized
vector fleld
F :M£R!TM; (x;t)7!F(x;t)2T M; (1.1)x
on a Riemannian manifold M. Hence F can be regarded as a time-depending family
of vector flelds and the task is to determine a continuous curve x :R!M such that⁄
F(x (t);t)=0 (1.2)⁄
holds for all t2R. This will be achieved by studying an extension of the Newton ow
on manifolds. The discretization of the resulting ODE,