Paper ID sheet UCL-INMA-2015.05

Title

A Riemannian rank-adaptive method for low-rank optimization

Authors

Guifang Zhou, Wen Huang, Kyle Gallivan, Paul Van Dooren, P.-A. Absil

Abstract

This paper presents an algorithm that solves optimization problems on a matrix manifold $\mathcal{M} \subseteq \mathbb{R}^{m \times n}$ with an additional rank inequality constraint. The algorithm resorts to well-known Riemannian optimization schemes on fixed-rank manifolds, combined with new mechanisms to increase or decrease the rank. The convergence of the algorithm is analyzed and a weighted low-rank approximation problem is used to illustrate the efficiency and effectiveness of the algorithm.

Key words

low-rank optimization; rank-constrained optimization; Riemannian manifold; fixed-rank manifold; low-rank approximation

Status

Accepted for publication in Neurocomputing, 2016

Download

• Publisher's version: doi:10.1016/j.neucom.2016.02.030
• Preprint
• Code (provided with no warranty, support, or any other form of responsibility)
  See also updated version below

Errata

The errata refers to the publisher's version.

• Algorithm 3, in the "Require" line and line 1: replace "X_0" by "X_{-1}". The sole purpose is to avoid the initial iterate being overwritten in the "for n" loop when n=0.
• Proof of Theorem 2, 10th line: replace "grad f(X_n)" by "grad f_r(X_n)".
• Proof of Theorem 2, displayed equation after "The contradiction argument is thus complete": replace the subscript "X_n" by "X_{n_j}".

Further information

• Updated code that complies with the first line of Algorithm 3 in the publisher's version.