Tracking on manifolds : quasi-Newton optimisation algorithms on manifolds

Abstract

In recent years, optimisation on manifolds has become a popular area of research. Applications in signal processing have been proposed as well. Optimisation methods on manifolds can reduce the dimension of the original problems compared to the problems in their ambient Euclidean space. Many traditional unconstrained optimisation algorithms such as the steepest descent algorithm, the Newton's method and the trust region algorithm have be extended to Riemannian manifolds or smooth manifolds. However, little work has been done in quasi-Newton algorithms on manifolds. In 1982, Gabay proposed a BFGS algorithm (which is a popular quasi-Newton algorithm) to Riemannian manifolds. The convergence proof was not completed. This thesis will continue his attempts on the proof of convergence results. A more challenging task will be brought to horizon on the completion of the Riemannian version of quasi-Newton algorithms. We will extend certain quasi-Newton algorithms to smooth manifolds. The essence of optimisation algorithms on smooth manifolds is the choice of local parameterisations. A local parameterisation is a diffeomorphism which maps a point on a manifold into a corresponding point in the Euclidean space within an open neighbourhood of that point. This idea is similar to the coordinate adapted quasi-Newton algorithms. Therefore, a thorough study on the coordinate adapted quasi-Newton algorithms will also be provided. The aims of this thesis are to" (a) provide an overview of the convergence properties of quasi-Newton algorithms in Euclidean space and compare the existing proof of convergence; (b) introduce the BFGS algorithm on Riemannian manifolds; then give a detailed global convergence proof and the convergence speed proof; (c)define the coordinate adapted quasi-Newton algorithms and prove the local convergence results including the convergence speed; (d)study quasi-Newton algorithms on smooth manifolds and discuss possible applications. Firstly, we will give an overview of the traditional quasi-Newton algorithms in Euclidean space. Derivations of various of quasi-Newton algorithms are given. There are two main types of convergence results in existing literature. The strong result shows the global Q-superlinear convergence but requires the uniform convexity of the cost function. The key idea of this technique is to use the trace and determinant of the updated matrices to control the evolution of the algorithm. A weaker result only shows the local Q-superlinear convergence. It uses a weighted Frobenius norm of the updated matrices to control the algorithm. Secondly, we will define the concept of the BFGS algorithm on Riemannian manifolds. Since Riemannian manifolds are equipped with a metric structure, we have rich properties defined on it. These properties allow us to apply similar skills for the global convergence once we define the convexity of a cost function on Riemannian manifolds. Detailed proof of Q-superlinear convergence rate is completed. Thirdly, we will define the coordinate adapted quasi-Newton algorithm which is novel in optimisation theory. The coordinate adapted quasi-Newton algorithm allows us to change coordinate systems in each step of iteration. The coordinate changes may give us greater freedom in defining the local cost functions which may have better convergence properties. Analysis on the local convergence is provided in this thesis. Fourthly, we will propose a modified BFGS algorithm on smooth manifolds. This algorithm has global convergence with uniform convexity for each local cost function. Preliminary analysis is conducted. Numerical results suggest the Q-superlinear convergence speed, but no proof is given. A possible application in joint diagonalisation problem is proposed as well.