A Riemannian geometry for low-rank matrix completion

Abstract

We propose a new Riemannian geometry for fixed-rank matrices that is specifically tailored to the low-rank matrix completion problem. Exploiting the degree of freedom of a quotient space, we tune the metric on our search space to the particular least square cost function. At one level, it illustrates in a novel way how to exploit the versatile framework of optimization on quotient manifold. At another level, our algorithm can be considered as an improved version of LMaFit, the state-of-the-art Gauss-Seidel algorithm. We develop necessary tools needed to perform both first-order and second-order optimization. In particular, we propose gradient descent schemes (steepest descent and conjugate gradient) and trust-region algorithms. We also show that, thanks to the simplicity of the cost function, it is numerically cheap to perform an exact linesearch given a search direction, which makes our algorithms competitive with the state-of-the-art on standard low-rank matrix completion instances.

Title modified, Typos removed. arXiv admin note: text overlap with arXiv:1209.0430

References in corpus (3)

• Guaranteed Rank Minimization via Singular Value Projection
• Low-rank optimization with trace norm penalty
• Fixed-rank matrix factorizations and Riemannian low-rank optimization

Cited by in corpus (17)

• Riemannian preconditioning
• Low-Rank Matrix Recovery with Scaled Subgradient Methods: Fast and Robust Convergence Without the Condition Number
• Guarantees of Riemannian Optimization for Low Rank Matrix Completion
• Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent
• Guarantees of Riemannian Optimization for Low Rank Matrix Recovery
• New Riemannian preconditioned algorithms for tensor completion via polyadic decomposition
• Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction: An Extended Version
• A Riemannian approach to low-rank algebraic Riccati equations
• Riemannian Perspective on Matrix Factorization
• Low-Rank Modeling and Its Applications in Image Analysis
• R3MC: A Riemannian three-factor algorithm for low-rank matrix completion
• A Sparse and Low-Rank Optimization Framework for Index Coding via Riemannian Optimization
• Scalable Nuclear-norm Minimization by Subspace Pursuit Proximal Riemannian Gradient
• Fast Optimization Algorithm on Riemannian Manifolds and Its Application in Low-Rank Representation
• Topological Interference Management with User Admission Control via Riemannian Optimization
• On Geometric Connections of Embedded and Quotient Geometries in Riemannian Fixed-rank Matrix Optimization
• On the analysis of optimization with fixed-rank matrices: a quotient geometric view