Low-rank matrix completion by Riemannian optimization---extended version
Preprint
Abstract
The matrix completion problem consists of finding or approximating a low-rank matrix based on a few samples of this matrix. We propose a new algorithm for matrix completion that minimizes the least-square distance on the sampling set over the Riemannian manifold of fixed-rank matrices. The algorithm is an adaptation of classical non-linear conjugate gradients, developed within the framework of retraction-based optimization on manifolds. We describe all the necessary objects from differential geometry necessary to perform optimization over this low-rank matrix manifold, seen as a submanifold embedded in the space of matrices. In particular, we describe how metric projection can be used as retraction and how vector transport lets us obtain the conjugate search directions. Finally, we prove convergence of a regularized version of our algorithm under the assumption that the restricted isometry property holds for incoherent matrices throughout the iterations. The numerical experiments indicate that our approach scales very well for large-scale problems and compares favorably with the state-of-the-art, while outperforming most existing solvers.Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- Fixed-rank matrix factorizations and Riemannian low-rank optimizationComputational Statistics, 2013
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithmMathematical Programming Computation, 2012
- On the low-rank approximation by the pivoted Cholesky decompositionApplied Numerical Mathematics, 2012
- Convergence of Fixed-Point Continuation Algorithms for Matrix Rank MinimizationFoundations of Computational Mathematics, 2011
- An implementable proximal point algorithmic framework for nuclear norm minimizationMathematical Programming, 2011
- Fixed point and Bregman iterative methods for matrix rank minimizationMathematical Programming, 2009
- Exact Matrix Completion via Convex OptimizationFoundations of Computational Mathematics, 2009
- Trust-Region Methods on Riemannian ManifoldsFoundations of Computational Mathematics, 2006
- A Newton-like method for solving rank constrained linear matrix inequalitiesAutomatica, 2006
- A nonlinear programming algorithm for solving semidefinite programs via low-rank factorizationMathematical Programming, 2003