Optimization Algorithms on Matrix Manifolds

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. Contents......Page 8 List of Algorithms......Page 12 Foreword......Page 14 Notation Conventions......Page 16 1. Introduction......Page 18 2.1 A case study: the eigenvalue problem......Page 22 2.1.1 The eigenvalue problem as an optimization problem......Page 24 2.1.2 Some benefits of an optimization framework......Page 26 2.2.1 Singular value problem......Page 27 2.2.2 Matrix approximations......Page 29 2.2.3 Independent component analysis......Page 30 2.2.4 Pose estimation and motion recovery......Page 31 2.3 Notes and references......Page 33 3. Matrix Manifolds: First-Order Geometry......Page 34 3.1.1 Definitions: charts, atlases, manifolds......Page 35 3.1.2 The topology of a manifold*......Page 37 3.1.3 How to recognize a manifold......Page 38 3.1.5 The manifolds Rnxp and R*nxp......Page 39 3.1.6 Product manifolds......Page 40 3.2.1 Immersions and submersions......Page 41 3.3.1 General theory......Page 42 3.3.2 The Stiefel manifold......Page 43 3.4.1 Theory of quotient manifolds......Page 44 3.4.2 Functions on quotient manifolds......Page 46 3.4.4 The Grassmann manifold Grass(p, n)......Page 47 3.5 Tangent vectors and differential maps......Page 49 3.5.1 Tangent vectors......Page 50 3.5.2 Tangent vectors to a vector space......Page 52 3.5.4 Vector fields......Page 53 3.5.5 Tangent vectors as derivations*......Page 54 3.5.6 Differential of a mapping......Page 55 3.5.7 Tangent vectors to embedded submanifolds......Page 56 3.5.8 Tangent vectors to quotient manifolds......Page 59 3.6 Riemannian metric, distance, and gradients......Page 62 3.6.1 Riemannian submanifolds......Page 64 3.6.2 Riemannian quotient manifolds......Page 65 3.7 Notes and references......Page 68 4.1 Retractions......Page 71 4.1.1 Retractions on embedded submanifolds......Page 73 4.1.2 Retractions on quotient manifolds......Page 76 4.1.3 Retractions and local coordinates*......Page 78 4.2 Line-search methods......Page 79 4.3.1 Convergence on manifolds......Page 80 4.3.2 A topological curiosity*......Page 81 4.3.3 Convergence of line-search methods......Page 82 4.4 Stability of fixed points......Page 83 4.5.1 Order of convergence......Page 85 4.5.2 Rate of convergence of line-search methods*......Page 87 4.6 Rayleigh quotient minimization on the sphere......Page 90 4.6.2 Critical points of the Rayleigh quotient......Page 91 4.6.3 Armijo line search......Page 93 4.6.6 Links with the power method and inverse iteration......Page 95 4.8.1 Cost function and search direction......Page 97 4.8.2 Critical points......Page 98 4.9.1 Cost function and gradient calculation......Page 100 4.9.2 Line-search algorithm......Page 102 4.10 Notes and references......Page 103 5.1 Newton’s method in Rn......Page 108 5.2 Affine connections......Page 110 5.3.1 Symmetric connections......Page 113 5.3.2 Definition of the Riemannian connection......Page 114 5.3.3 Riemannian connection on Riemannian submanifolds......Page 115 5.3.4 Riemannian connection on quotient manifolds......Page 117 5.4 Geodesics, exponential mapping, and parallel translation......Page 118 5.5 Riemannian Hessian operator......Page 121 5.6 Second covariant derivative*......Page 125 5.7 Notes and references......Page 127 6.1 Newton’s method on manifolds......Page 128 6.2 Riemannian Newton method for real-valued functions......Page 130 6.3 Local convergence......Page 131 6.3.1 Calculus approach to local convergence analysis......Page 134 6.4.1 Rayleigh quotient on the sphere......Page 135 6.4.2 Rayleigh quotient on the Grassmann manifold......Page 137 6.4.3 Generalized eigenvalue problem......Page 138 6.4.4 The nonsymmetric eigenvalue problem......Page 142 6.4.5 Newton with subspace acceleration: Jacobi-Davidson......Page 143 6.5.1 Convergence analysis......Page 145 6.5.2 Numerical implementation......Page 146 6.6 Notes and references......Page 148 7. Trust-Region Methods......Page 153 7.1.2 Models in general Euclidean spaces......Page 154 7.1.3 Models on Riemannian manifolds......Page 155 7.2.2 Trust-region methods on Riemannian manifolds......Page 157 7.3 Computing a trust-region step......Page 158 7.3.1 Computing a nearly exact solution......Page 159 7.3.2 Improving on the Cauchy point......Page 160 7.4.1 Global convergence......Page 162 7.4.2 Local convergence......Page 169 7.4.3 Discussion......Page 175 7.5.1 Checklist......Page 176 7.5.2 Symmetric eigenvalue decomposition......Page 177 7.5.3 Computing an extreme eigenspace......Page 178 7.6 Notes and references......Page 182 8.1 Vector transport......Page 185 8.1.1 Vector transport and affine connections......Page 187 8.1.2 Vector transport by differentiated retraction......Page 189 8.1.4 Vector transport on quotient manifolds......Page 191 8.2 Approximate Newton methods......Page 192 8.2.1 Finite difference approximations......Page 193 8.2.2 Secant methods......Page 195 8.3 Conjugate gradients......Page 197 8.3.1 Application: Rayleigh quotient minimization......Page 200 8.4 Least-square methods......Page 201 8.4.1 Gauss-Newton methods......Page 203 8.4.2 Levenberg-Marquardt methods......Page 204 8.5 Notes and references......Page 205 A.1 Linear algebra......Page 206 A.2 Topology......Page 208 A.3 Functions......Page 210 A.4 Asymptotic notation......Page 211 A.5 Derivatives......Page 212 A.6 Taylor’s formula......Page 215 Bibliography......Page 218 C......Page 238 L......Page 239 Q......Page 240 Z......Page 241 Many problems in the sciences and engineering can be rephrased as optimisation 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