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

RTRMC is an algorithm developed by Nicolas Boumal (contact person) and Pierre-Antoine Absil at UCLouvain to solve low-rank matrix completion problems.

The associated paper is available here:

N. Boumal and P.-A. Absil, RTRMC : A Riemannian trust-region method for low-rank matrix completion, NIPS 2011,

with a corresponding BibTex entry.

An extended version of the paper, with more detailed mathematical developments and numerical experiments, is available too:

N. Boumal and P.-A. Absil, Low-rank matrix completion via preconditioned optimization on the Grassmann manifold, in Linear Algebra and its Applications, 2015.

This version includes a preconditioner for RTRMC and adds Riemannian conjugate gradients support, thanks to the Manopt toolbox.
As a consequence, the code changed significantly: please see below to download version 3.2 of RTRMC and RCGMC (released July 22, 2015).
This version of the algorithms is also described in Nicolas Boumal's PhD thesis.

The abstract of the extended paper reads:

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.

Here is the Matlab code for RTRMC v3.2 under BSD licence.
This version of the code was put online on July 22, 2015. It changed significantly since version 1.1 and now uses Manopt 2.0.
Changes since version 2: now bundled with Manopt 1.0.5 instead of 1.0.4, and the buildproblem function now allows the data I, J, X, C to be given in any order.
Changes since version 3: a bug prevented the code from working when the weights Cij were not all the same. This was corrected by patching spbuildmatrix.c. And moved to Manopt 2.0.

To install and use the software:
If this procedure fails (quite probably somewhere in the installrtrmc.m script), then either there is trouble with the C compiler Matlab tries to use, which you can check by typing 'mex -setup' at the Matlab prompt, or the installation script is incompatible with your OS (it was written for Windows users, but has been found to work as is on a MacOS and a Linux computer). If you need help, please feel free to contact us. If you successfully ran installrtrmc.m on your computer, we'd love to know about any, if any, difficulties you may have resolved.

If you get this error:
??? Error using ==> spbuildmatrix
dpotrf (in spbuildmatrix): a leading minor is not positive definite.
Error in ==> lsqfit>buildmatrix at 132
    Achol = spbuildmatrix(problem.mask, U, lambda^2);
Error in ==> lsqfit at 65
        compumem.Achol = buildmatrix(problem, U);
Error in ==> rtrmcobjective at 66
       [W, compumem] = lsqfit(problem, U, compumem);
then try to raise the value of lambda (the regularization parameter). This error triggers when the least-squares problem (the computation of WU) does not have a unique solution, so that one of the diagonal blocks of the large matrix A does not have a proper Cholesky factorization.

Raghunandan Keshavan, co-author of OptSpace, maintains an interesting web page listing matrix completion-related papers and software.
The blog Nuit-Blanche featured a post about RTRMC on Sept. 12, 2011. The Matrix Factorization Jungle is another list of related software.
Last update: July 22, 2015