Low-Rank Matrix Completion by Riemannian Optimization

By Bart Vandereycken. 2012

588 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Mathematical Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Mathematical Physics

Citations in the corpus

A literature survey of low‐rank tensor approximation techniques (2013, neutral): “Examples include nonlinear conjugate gradient or Newton-like methods on manifolds of low-rank matrices [35,191,198,257,258] or low-rank tensors [52,53,131,132,255], see also Section 3.4.”
Global rates of convergence for nonconvex optimization on manifolds (2016, unknown): “For ﬁxed-rank matrices for example, Vandereycken (2013, § 4.1) obtains convergence results assuming a kind of coercivity on the cost function: for any sequence of rank-k matrices ( X i ) i =1 , 2 ,... such that the ﬁrst singular value σ 1 ( X i ) → ∞ or the k th singular value σ k ( X i ) → 0, it…”
Scaled Gradients on Grassmann Manifolds for Matrix Completion (2012, background): “This problem has attracted much attention recently [8, 14, 13, 18, 21] because of its broad applications, e.g., in recommender systems, structure from motion, and multitask learning (see e.g. [19, 9, 2]).”
On critical points of quadratic low-rank matrix optimization problems (2020, methodology): “In addition careful implementations using retractions and low-rank factorization have similar cost per iteration as algorithms based on bilinear factorizations; see, e.g., Shalit et al. (2012), Vandereycken (2013), Vandereycken & Vandewalle (2010).”
First-order Methods for Geodesically Convex Optimization (2016, background): “There exist several nonconvex problems where Riemannian optimization has proved quite useful, e.g., low-rank matrix and tensor factorization (Vandereycken, 2013; Ishteva et al., 2011; Mishra et al., 2013); dictionary learning (Sun et al., 2015; Harandi et al., 2012); optimization under…”
Pymanopt: A Python Toolbox for Optimization on Manifolds using Automatic Differentiation (2016, methodology): “…applications of optimization on manifolds include matrix completion tasks (Vandereycken, 2013; Boumal and Absil, 2015), robust PCA (Podosinnikova et al., 2014), dimension reduction for independent component analysis (ICA) (Theis et al., 2009), kernel ICA (Shen et al., 2007) and similarity…”
Low-rank methods for high-dimensional approximation and model order reduction (2015, unknown): “hich allows the use of more or less standard optimization algorithms (e.g. Newton, steepest descent, block coordinate descent), possibly exploiting the 22 manifold structure of P1 × ...× PM (see e.g. [35, 86, 84]). Alternating minimization algorithms (or block coordinate descent algorithms) transfor”
Low-rank tensor completion by Riemannian optimization (2014, methodology): “A similar approach has been considered in [19, 21, 30] for the matrix case, where it was shown to be competitive to other state-ofthe-art approaches to matrix completion.”
Manopt, a matlab toolbox for optimization on manifolds (2013, background): “Vandereycken (2013) proposes an embedded geometry for M and exploits Riemannian optimization on that manifold to address the low-rank matrix completion problem.”
Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “Other gradient descent approaches on manifolds include [100–106].”