Brace, Ian (The Univ. of Melbourne), Manton, Jonathan (The Australian National Univ.)

An improved BFGS-on-Manifold algorithm for computing weighted low-rank approximations

Scheduled for presentation during the Mini-Symposium "Geometric Optimisation in Systems and Control II" (ThA07), Thursday, July 27, 2006, 12:05−12:30, Room H

17th International Symposium on Mathematical Theory of Networks and Systems, July 24-28, 2006, Kyoto, Japan

This information is tentative and subject to change. Compiled on May 19, 2024

Abstract

This paper studies the problem of computing numerically the best low rank appproximation of a given matrix, where the criteria for best is measured by a weighted (non-matrix) norm. Previously, it has been shown that the natural setting for this computation is on the Grassmann manifold, and steepest descent and Newton-type algorithms were derived.

This paper derives a new BFGS-on-manifold algorithm for optimising a cost function on a Grassmann manifold, and applies this algorithm to the weighted low rank approximation problem. The advantage of this algorithm over other algorithms (including conjugate gradient and Riemannian BFGS optimisation algorithms on manifolds) is the lower computational complexity without sacrificing the super-linear rate of convergence.