Optimization algorithms on matrix manifolds [electronic resource] / P.-A. Absil, R. Mahony, R. Sepulchre.

ISBN:

9781400830244

Titre:

Auteur:

Absil, P.-A.

Auteur personnel:

Absil, P.-A.

Informations de publication:

Description physique:

1 online resource (xiv, 224 pages) : illustrations

Contenu:

Introduction -- Motivation and applications -- Matrix manifolds : first-order geometry -- Line-search algorithms on manifolds -- Matrix manifolds : second-order geometry -- Newton's method -- Trust-region methods -- A constellation of superlinear algorithms.

Note locale:

eBooks on EBSCOhost

Terme sujet:

Mathematical optimization.

Matrices.

Algorithms.

Auteur ajouté:

Mahony, R. (Robert), 1967-

Sepulchre, R. (Rodolphe), 1967-

Format:

Ressources électroniques

Accès électronique:

Click here to view

Date de publication:

2008

WAIT_PUBINFO:

Disponible:*

Numéro de rayon	Type de documentation	Copier	Emplacement en rayon	Statut
518.1 22	1:E-BOOK	1	1:ONLINE	Recherche en cours... Inconnu

Relié avec ces titres

Commandé

Résumé

Many problems in the sciences and engineering can be rephrased as optimization problems on matrix search spaces endowed with a so-called manifold structure. This book shows how to exploit the special structure of such problems to develop efficient numerical algorithms. It places careful emphasis on both the numerical formulation of the algorithm and its differential geometric abstraction--illustrating how good algorithms draw equally from the insights of differential geometry, optimization, and numerical analysis. Two more theoretical chapters provide readers with the background in differential geometry necessary to algorithmic development. In the other chapters, several well-known optimization methods such as steepest descent and conjugate gradients are generalized to abstract manifolds. The book provides a generic development of each of these methods, building upon the material of the geometric chapters. It then guides readers through the calculations that turn these geometrically formulated methods into concrete numerical algorithms. The state-of-the-art algorithms given as examples are competitive with the best existing algorithms for a selection of eigenspace problems in numerical linear algebra.

Optimization Algorithms on Matrix Manifolds offers techniques with broad applications in linear algebra, signal processing, data mining, computer vision, and statistical analysis. It can serve as a graduate-level textbook and will be of interest to applied mathematicians, engineers, and computer scientists.

Notes de l'auteur

P.-A. Absil is associate professor of mathematical engineering at the Université Catholique de Louvain in Belgium. R. Mahony is reader in engineering at the Australian National University. R. Sepulchre is professor of electrical engineering and computer science at the University of Liège in Belgium.

Table des matières

List of Algorithms	p. xi
Foreword, by Paul Van Dooren	p. xiii
Notation Conventions	p. xv
Chapter 1 Introduction	p. 1
Chapter 2 Motivation and Applications	p. 5
2.1 A case study: the eigenvalue problem	p. 5
2.1.1 The eigenvalue problem as an optimization problem	p. 7
2.1.2 Some benefits of an optimization framework	p. 9
2.2 Research problems	p. 10
2.2.1 Singular value problem	p. 10
2.2.2 Matrix approximations	p. 12
2.2.3 Independent component analysis	p. 13
2.2.4 Pose estimation and motion recovery	p. 14
2.3 Notes and references	p. 16
Chapter 3 Matrix Manifolds: First-Order Geometry	p. 17
3.1 Manifolds	p. 18
3.1.1 Definitions: charts, atlases, manifolds	p. 18
3.1.2 The topology of a manifold*	p. 20
3.1.3 How to recognize a manifold	p. 21
3.1.4 Vector spaces as manifolds	p. 22
3.1.5 The manifolds R n x p and R n x p	p. 22
3.1.6 Product manifolds	p. 23
3.2 Differentiable functions	p. 24
3.2.1 Immersions and submersions	p. 24
3.3 Embedded submanifolds	p. 25
3.3.1 General theory	p. 25
3.3.2 The Stiefel manifold	p. 26
3.4 Quotient manifolds	p. 27
3.4.1 Theory of quotient manifolds	p. 27
3.4.2 Functions on quotient manifolds	p. 29
3.4.3 The real projective space RP n x 1	p. 30
3.4.4 The Grassmann manifold Grass(p, n)	p. 30
3.5 Tangent vectors and differential maps	p. 32
3.5.1 Tangent vectors	p. 33
3.5.2 Tangent vectors to a vector space	p. 35
3.5.3 Tangent bundle	p. 36
3.5.4 Vector fields	p. 36
3.5.5 Tangent vectors as derivations?	p. 37
3.5.6 Differential of a mapping	p. 38
3.5.7 Tangent vectors to embedded submanifolds	p. 39
3.5.8 Tangent vectors to quotient manifolds	p. 42
3.6 Riemannian metric, distance, and gradients	p. 45
3.6.1 Riemannian submanifolds	p. 47
3.6.2 Riemannian quotient manifolds	p. 48
3.7 Notes and references	p. 51
Chapter 4 Line-Search Algorithms on Manifolds	p. 54
4.1 Retractions	p. 54
4.1.1 Retractions on embedded submanifolds	p. 56
4.1.2 Retractions on quotient manifolds	p. 59
4.1.3 Retractions and local coordinates*	p. 61
4.2 Line-search methods	p. 62
4.3 Convergence analysis	p. 63
4.3.1 Convergence on manifolds	p. 63
4.3.2 A topological curiosity*	p. 64
4.3.3 Convergence of line-search methods	p. 65
4.4 Stability of fixed points	p. 66
4.5 Speed of convergence	p. 68
4.5.1 Order of convergence	p. 68
4.5.2 Rate of convergence of line-search methods*	p. 70
4.6 Rayleigh quotient minimization on the sphere	p. 73
4.6.1 Cost function and gradient calculation	p. 74
4.6.2 Critical points of the Rayleigh quotient	p. 74
4.6.3 Armijo line search	p. 76
4.6.4 Exact line search	p. 78
4.6.5 Accelerated line search: locally optimal conjugate gradient	p. 78
4.6.6 Links with the power method and inverse iteration	p. 78
4.7 Refining eigenvector estimates	p. 80
4.8 Brockett cost function on the Stiefel manifold	p. 80
4.8.1 Cost function and search direction	p. 80
4.8.2 Critical points	p. 81
4.9 Rayleigh quotient minimization on the Grassmann manifold	p. 83
4.9.1 Cost function and gradient calculation	p. 83
4.9.2 Line-search algorithm	p. 85
4.10 Notes and references	p. 86
Chapter 5 Matrix Manifolds: Second-Order Geometry	p. 91
5.1 Newton's method in R n	p. 91
5.2 Affine connections	p. 93
5.3 Riemannian connection	p. 96
5.3.1 Symmetric connections	p. 96
5.3.2 Definition of the Riemannian connection	p. 97
5.3.3 Riemannian connection on Riemannian submanifolds	p. 98
5.3.4 Riemannian connection on quotient manifolds	p. 100
5.4 Geodesics, exponential mapping, and parallel translation	p. 101
5.5 Riemannian Hessian operator	p. 104
5.6 Second covariant derivative*	p. 108
5.7 Notes and references	p. 110
Chapter 6 Newton's Method	p. 111
6.1 Newton's method on manifolds	p. 111
6.2 Riemannian Newton method for real-valued functions	p. 113
6.3 Local convergence	p. 114
6.3.1 Calculus approach to local convergence analysis	p. 117
6.4 Rayleigh quotient algorithms	p. 118
6.4.1 Rayleigh quotient on the sphere	p. 118
6.4.2 Rayleigh quotient on the Grassmann manifold	p. 120
6.4.3 Generalized eigenvalue problem	p. 121
6.4.4 The nonsymmetric eigenvalue problem	p. 125
6.4.5 Newton with subspace acceleration: Jacobi-Davidson	p. 126
6.5 Analysis of Rayleigh quotient algorithms	p. 128
6.5.1 Convergence analysis	p. 128
6.5.2 Numerical implementation	p. 129
6.6 Notes and references	p. 131
Chapter 7 Trust-Region Methods	p. 136
7.1 Models	p. 137
7.1.1 Models in R n	p. 137
7.1.2 Models in general Euclidean spaces	p. 137
7.1.3 Models on Riemannian manifolds	p. 138
7.2 Trust-region methods	p. 140
7.2.1 Trust-region methods in R n	p. 140
7.2.2 Trust-region methods on Riemannian manifolds	p. 140
7.3 Computing a trust-region step	p. 141
7.3.1 Computing a nearly exact solution	p. 142
7.3.2 Improving on the Cauchy point	p. 143
7.4 Convergence analysis	p. 145
7.4.1 Global convergence	p. 145
7.4.2 Local convergence	p. 152
7.4.3 Discussion	p. 158
7.5 Applications	p. 159
7.5.1 Checklist	p. 159
7.5.2 Symmetric eigenvalue decomposition	p. 160
7.5.3 Computing an extreme eigenspace	p. 161
7.6 Notes and references	p. 165
Chapter 8 A Constellation of Superlinear Algorithms	p. 168
8.1 Vector transport	p. 168
8.1.1 Vector transport and affine connections	p. 170
8.1.2 Vector transport by differentiated retraction	p. 172
8.1.3 Vector transport on Riemannian submanifolds	p. 174
8.1.4 Vector transport on quotient manifolds	p. 174
8.2 Approximate Newton methods	p. 175
8.2.1 Finite difference approximations	p. 176
8.2.2 Secant methods	p. 178
8.3 Conjugate gradients	p. 180
8.3.1 Application: Rayleigh quotient minimization	p. 183
8.4 Least-square methods	p. 184
8.4.1 Gauss-Newton methods	p. 186
8.4.2 Levenberg-Marquardt methods	p. 187
8.5 Notes and references	p. 188
A Elements of Linear Algebra, Topology, and Calculus	p. 189
A.1 Linear algebra	p. 189
A.2 Topology	p. 191
A.3 Functions	p. 193
A.4 Asymptotic notation	p. 194
A.5 Derivatives	p. 195
A.6 Taylor's formula	p. 198
Bibliography	p. 201
Index	p. 221