Optimization Online


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

Nicolas Boumal (nicolasboumal***at***gmail.com)
P.-A. Absil (absil***at***inma.ucl.ac.be)

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.

Keywords: Low-rank matrix completion, optimization on manifolds, Grassmann manifold, preconditioned Riemannian trust-regions, preconditioned Riemannian conjugate gradient, second-order methods, fixed-rank geometry, RTRMC, RCGMC

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Nonlinear Optimization (Nonlinear Systems and Least-Squares )


Download: [PDF]

Entry Submitted: 09/26/2012
Entry Accepted: 09/26/2012
Entry Last Modified: 02/20/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society