Low-rank matrix completion via preconditioned optimization on the Grassmann manifold

Nicolas Boumal, P. A. Absil

Research output: Contribution to journalArticle

27 Scopus citations

Abstract

We address the numerical problem of recovering large matrices of low rank when most of the entries are unknown. We exploit the geometry of the low-rank constraint to recast the problem as an unconstrained optimization problem on a single Grassmann manifold. We then apply second-order Riemannian trust-region methods (RTRMC 2) and Riemannian conjugate gradient methods (RCGMC) to solve it. A preconditioner for the Hessian is introduced that helps control the conditioning of the problem and we detail preconditioned versions of Riemannian optimization algorithms. The cost of each iteration is linear in the number of known entries. The proposed methods are competitive with state-of-the-art algorithms on a wide range of problem instances. In particular, they perform well on rectangular matrices. We further note that second-order and preconditioned methods are well suited to solve badly conditioned matrix completion tasks.

Original languageEnglish (US)
Article number13116
Pages (from-to)200-239
Number of pages40
JournalLinear Algebra and Its Applications
Volume475
DOIs
StatePublished - Jun 2015

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics

Keywords

  • Fixed-rank geometry
  • Grassmann manifold
  • Low-rank matrix completion
  • Optimization on manifolds
  • Preconditioned Riemannian conjugate gradients
  • Preconditioned Riemannian trust-regions
  • RCGMC
  • RTRMC
  • Second-order methods

Fingerprint Dive into the research topics of 'Low-rank matrix completion via preconditioned optimization on the Grassmann manifold'. Together they form a unique fingerprint.

  • Cite this