Optimization Techniques on Riemannian Manifolds

By Steven Thomas Smith. arXiv.org, 2014

338 citations recorded by the source corpus.

The techniques and analysis presented in this paper provide new methods to solve optimization problems posed on Riemannian manifolds. A new point of view is offered for the solution of constrained optimization problems. Some classical optimization techniques on Euclidean space are generalized to Riemannian manifolds. Several algorithms are presented and their convergence properties are analyzed employing the Riemannian structure of the manifold. Specifically, two apparently new algorithms, which can be thought of as Newton's method and the conjugate gradient method on Riemannian manifolds, are presented and shown to possess, respectively, quadratic and superlinear convergence. Examples of each method on certain Riemannian manifolds are given with the results of numerical experiments. Rayleigh's quotient defined on the sphere is one example. It is shown that Newton's method applied to this function converges cubically, and that the Rayleigh quotient iteration is an efficient approximation of Newton's method. The Riemannian version of the conjugate gradient method applied to this function gives a new algorithm for finding the eigenvectors corresponding to the extreme eigenvalues of a symmetric matrix. Another example arises from extremizing the function $\mathop{\rm tr} {\Theta}^{\scriptscriptstyle\rm T}Q{\Theta}N$ on the special orthogonal group. In a similar example, it is shown that Newton's method applied to the sum of the squares of the off-diagonal entries of a symmetric matrix converges cubically.

Subfields: Applied Mathematics, Computational Theory and Mathematics, Numerical Analysis

View Paper: https://www.semanticscholar.org/paper/5df68e7e736d7bfad2217613a03a78c72ba3bcd1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation (2016, methodology): “The potential of optimization on manifolds and Pymanopt use-cases Much of the theory of how to adapt Euclidean optimization algorithms to (matrix) manifolds can be found in Smith (1994); Edelman et al. (1998); Absil et al. (2008). The approach of optimization on manifolds is superior to performing f”
On-Manifold Preintegration for Real-Time Visual--Inertial Odometry (2015, background): “A standard approach for optimization on manifold [45], [48], consists of defining a retraction Rx , which is a bijective map between an element δx of the tangent space (at x) and a neighborhood of x ∈M.”
A new, globally convergent Riemannian conjugate gradient method (2013, methodology): “As for the conjugate gradient method, Smith provided in [11] a conjugate gradient method on M along with other optimization algorithms on M .”
Riemannian Optimization on Tensor Products of Grassmann Manifolds: Applications to Generalized Rayleigh-Quotients (2010, methodology): “We refer to [29] for the generalization of the NCG method to a Riemannian manifold.”
A feasible method for optimization with orthogonality constraints (2012, methodology): “Newton’s methods, such as those in [2, 18, 40, 49, 50, 52], use the second-order information of the objective function to achieve super-linear convergence.”
Global rates of convergence for nonconvex optimization on manifolds (2016, positive): “…on manifolds is concerned with solving nonlinear and typically nonconvex computational problems of the form min x ∈M f ( x ) , (P) where M is a (smooth) Riemannian manifold and f : M → R is a (suﬃciently smooth) cost function (Gabay, 1982; Smith, 1994; Edelman et al., 1998; Absil et al., 2008).”
Optimization Methods on Riemannian Manifolds and Their Application to Shape Space (2012, methodology): “Smith proved quadratic convergence for the more general case of applying Newton’s method to find a zero of a one-form on a manifold with the Levi-Civita connection [21] (the method is stated for an unspecified affine connection in [4]), using geodesic steps.”
Projection-like Retractions on Matrix Manifolds (2012, background): “Following on the work of Luenberger [24] and Gabay [11], much of the early interest focused on manifold-based optimization methods that exploit the underlying geometry of those optimization problems by relying almost exclusively on mainstream differential-geometric concepts; major references include”